1前几天关于围棋的问题,有人已经证明了可能存在必胜的解法,不过... pdwolf 2004-06-21 08:15:51

这几天复习的时候查到这个资料:
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

219*19的小棋盘研究透了,就改下21*21! 电子赵括 2004-06-21 18:54:57
围棋之所以从小棋盘演化到现在的19*19的大棋盘,原因众说纷纭.其中小棋盘变化少,容易被研究透是很流行的说法之一.19*19被研究透彻,把棋盘变大两路,恐怕又要让计算机"头疼"一段时间了.

凭感觉,至少对于人脑,21*21的围棋将很大程度上不同于现在的19*19.三连星中国流等布局将因为空隙变大而失去相应的威力.多两路,有机会真想下下看.

3这是数学家玩的花活：证明必胜解法的存在性，不等于找到了必胜解法， 林小筑 2004-06-21 21:04:22
更不等于研究透了。好比一个黑箱子，颠一颠有响动的话，可以断定里面有东西，但具体是什么东西，就不知道了。

而且，前面说过了，如果不贴目的话，先手必胜没什么奇怪的（假设双方都绝顶聪明不失误的话）。不过，这个研究也有一个好处，说不定能就此找出贴目的理论最佳值。据我所知，现在的贴目来源于经验，没有理论根据。不过，我觉得最好的下法还是中国古法：连下2*n番棋，先手各半，最后算总目数，这样最公平。

围棋的扩展倒是很有趣。以前有人提出过，不仅仅是扩大棋盘，还可以改变棋盘形状，比如正方体的六个面连起来算一个棋盘，这样，就没有“边”的概念了。还可以下立体的围棋，在三维情况下，每个子有六口气。晕吧？这个估计是超出人类智能了。而且吃子好像有点难。

4如果是这样，虚竹就只有当小和尚的命了。梦姑也真的就名副其实了，呵呵 jlanu 2004-06-21 22:13:59
棋盘变立体，棋手是不是都要在棋盘里走来走去的啊？

2我觉得这个倒也不是特别奇怪 林小筑 2004-06-21 09:11:44
不知道那个证明者有无把贴目考虑进去。如果没有的话，先手理论上会胜，这个恐怕大家都有概念吧，至少19*19是个奇数。所以这个有人证明出来不是特别令人惊奇。狼兄是否有准确的source？我也想看看。

3我是在一篇台湾数学教授的讲义上找到的 pdwolf 2004-06-22 06:18:41
那本书见过,不过没借来看过,数学模型和实际操作是两回事,就拿已经研究得很透彻的bus crew问题来说,数学模型早就在那里了,但是一具体拿到现实中,排个100多辆bus的轮班表还是不容易,现实中的非线性事件太多了.

以我个人的看法,如果这个10~600的证明是证全了,那所有写围棋程序的都可以收工了,这个运算量不是任何已知的硬件可以承受的,一盘棋还没收官,宇宙已经玩完了. 如果还有提高,我想方向应该是如何使搜索更有效率,或者用神经网络,进化算法之类的非线型模式

2那得多少太deep deep blue啊？ 寒冬雪 2004-06-21 09:08:03
呵呵，看来学围棋的真不是普通人，要计算机赢李昌镐估计得等他50岁以后了。

3以前听说过中山大学有搞围棋程序的。程序比赛里是头几个 铁手 2004-06-21 19:11:31
只是忘了和人对杀的效果如何。印象中要比人差很多。但是已经可以在计算机程序围棋比赛中牛牛的了。

4前一段时间见网上说“手谈”是国人写的最强的人机对弈软件， 朔雷 2004-06-23 06:28:33
不过在日本棋室见与几个号称robot(应该是程序) 的家伙下过，觉得我们的手谈还是要逊色一些。

5去年世锦赛，手谈是世界第四 你克我服 2004-06-23 08:00:57
第一是朝鲜人写的计算引擎：KCC围棋，在日本商品化后叫做《银星围棋》，现在最新版本是 4

第二是日本人写的计算引擎：最高峰，在日本商品化后也叫做《最高峰》，现在最新版本是 3

第三是英国人写的计算引擎：go++ (从前叫go 4++)，在日本商品化后叫做《最强围棋》，现在最新版本是 2004

第四是中国人写的计算引擎：goemate（从前叫做 手谈 ），在日本商品化后叫做《手谈围棋》，现在最新版本是 5

这四个是日本棋院认证达到初段水平的

日本每年都有一个岐阜世界围棋挑战赛，这时候世界最强的程序都会来参加，算是当今水平最高的吧
相比较有名的《the many face of go》啦，GNU Go啦，中国的乌鹭小组啦，都会来参赛的。
今年应该也快了

BTW: 上面前四名的程序，第三第四俺手头就有（各买了一份），在日本的谁想要而且不怕盗版犯法的，偷偷跟我说一声了.....

6问一下,速度怎么样? 电子赵括 2004-06-23 20:27:41
我手头也曾经有国一个围棋软件,共分20个等级.1级最弱,无聊;20级最强,慢得无法忍受.当时我最习惯和15-18级下,从来没有赢过100目以下,吃光过它两回.

如果有机会,到真想看看现在的电脑围棋是个什么水平.

7速度是没问题的.... 你克我服 2004-06-23 20:51:59
西西河要是有FTP服务器，我倒可以上传一份

6不会吧，初段没这么惨吧。 朔雷 2004-06-23 08:23:53

7谁知道你看到的那个robot是啥版本的呢？呵呵 你克我服 2004-06-23 08:41:13
我看，现在的《手谈5》，也就有四五级的水平

不过这就够让人满意的了
俺身边的一个弟兄有业余三段以上的实力，让《手谈5》到7子，就让不动了.....

4这个事情很奇怪。前几年一直有世界比赛，风声很大的。这两年没消息了， 林小筑 2004-06-21 20:46:41
问google也不知道。