主题：前几天关于围棋的问题,有人已经证明了可能存在必胜的解法,不过... -- pdwolf
家园 前几天关于围棋的问题,有人已经证明了可能存在必胜的解法,不过... 这几天复习的时候查到这个资料:
Robertson,E. and Munro, I. 〈NP-completeness, puzzles, and games〉 Utilifas Math., 1978, 99-116.
这本书里证明了围棋是PSPACE-hard问题,PSPACE-complete中的计算量已经是指数上升了,PSAPCE-hard就更大了,近年的计算表明围棋必胜法的记忆量在10~600,而我们已知的宇宙原子数才10~75
家园 19*19的小棋盘研究透了,就改下21*21! 围棋之所以从小棋盘演化到现在的19*19的大棋盘,原因众说纷纭.其中小棋盘变化少,容易被研究透是很流行的说法之一.19*19被研究透彻,把棋盘变大两路,恐怕又要让计算机"头疼"一段时间了.
凭感觉,至少对于人脑,21*21的围棋将很大程度上不同于现在的19*19.三连星中国流等布局将因为空隙变大而失去相应的威力.多两路,有机会真想下下看.
家园 这是数学家玩的花活：证明必胜解法的存在性，不等于找到了必胜解法， 更不等于研究透了。好比一个黑箱子，颠一颠有响动的话，可以断定里面有东西，但具体是什么东西，就不知道了。
而且，前面说过了，如果不贴目的话，先手必胜没什么奇怪的（假设双方都绝顶聪明不失误的话）。不过，这个研究也有一个好处，说不定能就此找出贴目的理论最佳值。据我所知，现在的贴目来源于经验，没有理论根据。不过，我觉得最好的下法还是中国古法：连下2*n番棋，先手各半，最后算总目数，这样最公平。
围棋的扩展倒是很有趣。以前有人提出过，不仅仅是扩大棋盘，还可以改变棋盘形状，比如正方体的六个面连起来算一个棋盘，这样，就没有“边”的概念了。还可以下立体的围棋，在三维情况下，每个子有六口气。晕吧？
这个估计是超出人类智能了。而且吃子好像有点难。家园 如果是这样，虚竹就只有当小和尚的命了。梦姑也真的就名副其实了，呵呵 棋盘变立体，棋手是不是都要在棋盘里走来走去的啊？
家园 我觉得这个倒也不是特别奇怪 不知道那个证明者有无把贴目考虑进去。如果没有的话，先手理论上会胜，这个恐怕大家都有概念吧，至少19*19是个奇数。所以这个有人证明出来不是特别令人惊奇。狼兄是否有准确的source？我也想看看。
家园 我是在一篇台湾数学教授的讲义上找到的 那本书见过,不过没借来看过,数学模型和实际操作是两回事,就拿已经研究得很透彻的bus crew问题来说,数学模型早就在那里了,但是一具体拿到现实中,排个100多辆bus的轮班表还是不容易,现实中的非线性事件太多了.
以我个人的看法,如果这个10~600的证明是证全了,那所有写围棋程序的都可以收工了,这个运算量不是任何已知的硬件可以承受的,一盘棋还没收官,宇宙已经玩完了. 如果还有提高,我想方向应该是如何使搜索更有效率,或者用神经网络,进化算法之类的非线型模式
家园 那得多少太deep deep blue啊？ 呵呵，看来学围棋的真不是普通人，要计算机赢李昌镐估计得等他50岁以后了。
家园 以前听说过中山大学有搞围棋程序的。程序比赛里是头几个 只是忘了和人对杀的效果如何。印象中要比人差很多。但是已经可以在计算机程序围棋比赛中牛牛的了。
家园 前一段时间见网上说“手谈”是国人写的最强的人机对弈软件， 不过在日本棋室见与几个号称robot(应该是程序) 的家伙下过，觉得我们的手谈还是要逊色一些。
家园 去年世锦赛，手谈是世界第四 第一是朝鲜人写的计算引擎：KCC围棋，在日本商品化后叫做《银星围棋》，现在最新版本是 4
第二是日本人写的计算引擎：最高峰，在日本商品化后也叫做《最高峰》，现在最新版本是 3
第三是英国人写的计算引擎：go++ (从前叫go 4++)，在日本商品化后叫做《最强围棋》，现在最新版本是 2004
第四是中国人写的计算引擎：goemate（从前叫做 手谈 ），在日本商品化后叫做《手谈围棋》，现在最新版本是 5
这四个是日本棋院认证达到初段水平的
日本每年都有一个岐阜世界围棋挑战赛，这时候世界最强的程序都会来参加，算是当今水平最高的吧
相比较有名的《the many face of go》啦，GNU Go啦，中国的乌鹭小组啦，都会来参赛的。
今年应该也快了
BTW: 上面前四名的程序，第三第四俺手头就有（各买了一份），在日本的谁想要而且不怕盗版犯法的，偷偷跟我说一声了.....
家园 这个事情很奇怪。前几年一直有世界比赛，风声很大的。这两年没消息了， 问google也不知道。