和电脑下围棋

wq1977

今天在网上找围棋游戏，找到了gnugo，遵循GPL协议的围棋游戏,支持人机对战.gnugo的版本在不断的更新，电脑的水平也在不断的增强，我在高中的时候有一段时间曾经很喜欢下围棋，还买了教学书，记得教学的书总是从最基本的东西讲起，第一页总是告诉你什么叫气，怎么样数气,慢慢涉及到打劫，局部的战争，一些小技巧，学的时候总是很认真，也很开心，但是一旦上了棋盘，面对着一望无际的棋盘，总是觉得好象掉进了一望无际的沙漠,不知道该怎样下手，前面学的那些东西，好象一点用处也派不上了。在我的眼里，围棋就象以前文人的诗词，优雅，美妙，但是遥不可及

我是从这里下载gnugo的最新稳定版本3.4的，或者你也可以访问它的官方网站http://www.gnu.org/software/gnugo/devel.html随时检查更新。下载下来一个大概两兆的文件，是所有的源代码，通过三步(./configure && make && make install)走进行配置，编译和安装,一切顺利的话你就可以在命令行输入gnugo运行程序了,当然这时候你运行的只是一个ASCII(文本)模式的游戏,像上面抓图中左边的样子。如果你觉得丑，可以下载一个围棋程序的前端，围棋程序有很多前端程序，有java版本的，也有X11版本的，上面图中显示的是一个X11版本的前端程序：cgoban,在http://www.igoweb.org/~wms/comp/cgoban/index.html下载cgoban的X11版本，下载以后同样通过三步进行安装，在最后一步make install之前确定Makefile中的安装路径是有效的,如果你的Makefile中的安装路径还是@PREFIX@，可以把它修改成/usr/loca/bin

在gnugo的INSTALL文档或者README文档中详细介绍了通过cgoban运行gnugo的方法，只需要通过几步的设置就可以了，然后你就可以开始和gnugo一较高下了，在游戏过程中，你可以随时将当前的状态存盘，以便以后继续比赛，非常方便，试一试吧！

sjinny

呵呵，又现身了呀，最近在做什么？

hotboy1000

楼主不说了在下围棋了吗？怎么楼上的还问？

wq1977

呵呵,在研究wxwindows

sjinny

晕，楼主不会一直下棋的呀~

wq1977, GameSrv现在怎么样了？邮件列表里都没消息了……

starfish

电脑围棋的水平还是太差了
以我这种业余水平
让他九子都能大胜

事实上，围棋比国际象棋难得多
我估计50年内电脑围棋不可能达到人类的水平。

Veldrin

楼上的太低估计算机发展的速度了
我看10年内人脑就不是电脑围棋的对手。

sejishikong

以我对电脑和围棋的了解，10年内电脑战胜人脑是不可能的（像我这样的臭棋除外），围棋毕竟比其它棋类的复杂得太多了。

Veldrin

以我专业的知识（人工智能），除非10年后围棋不再流行，否则不可能下不过人。——当然，顶级的大师应该还是可以相抗衡的，类似于现在的vs 深蓝。

樱家冢

围棋需要的运算量跟象棋根本不在一个数量级，电脑还有的发展了，即使按照摩尔定律，50年以内也不可能。

Veldrin

lol

围棋需要的不是也不应当是穷举型的算法，这点和象棋不一样。要是穷举谁都算的出来——3的361次方，别说50年内，就算发展到宇宙毁灭也不可能有这么快的。围棋的算法应当是学习性质的，主要应当模拟人类判断和学习能力。

你觉得让机器人达到和人流畅的交谈容易，还是下围棋容易？嘿嘿

Veldrin

不要把人脑的能力想得太神秘了，单论计算能力，人脑远不如现在的计算机。

starfish

TO: Veldrin
并不是我低估了电脑的发展速度
要知道，有些问题不是凭借高速的CPU就能解决的。

计算机计算一个问题的时候
所需的时间是和其输入规模有关的
例如用同样的程序对100个数排序所花的时间肯定比对1000个数花的时间少，
因此衡量程序效率的时间复杂度就应该是关于输入规模 n 的函数 f(n)
所谓多项式算法，就是指算法的时间复杂度 f(n) 是 n 的多项式函数，
例如 f(n) = n^100 + 30*n^99+1
所谓指数算法，就是指算法的时间复杂度 f(n) 是 n 的指数函数，
例如 f(n) = 2^n

如果某个程序的时间复杂度是关于输入的多项式函数
那么通过CPU速度的提高可以显著地减少程序执行所花的时间。
但是，如果某个程序的时间复杂度是关于输入的指数函数，
CPU速度的提高在大多数情况下几乎不能减少程序执行所花的时间。

例如，若时间复杂度是指数函数： f(n) = 2^n
假设现在的CPU速度是每秒 10^10 次运算，现在速度提高了10000 倍，每秒 10^14 次运算
原来执行该程序花的时间是t1= 2^n / 10^10，现在是t2= 2^n / 10^14
当 n = 100 的时候， 虽然 t2/t1 = 1/10000，但 t2 = 2^100 / 10^14  仍然是个巨大的天文数字，这么长的时间算到宇宙毁灭也算不完。
且 (t1 - t2)/t1 约等于 0, 也就是说时间减少的百分比几乎没有改变。

因此 CPU速度的提高对于指数时间复杂度的程序几乎没有什么作用。


现在的电脑再怎么发展都摆脱不了图灵机(Turing Machine)的计算模型
而在图灵机的计算模型上
有一类问题称为NP问题
该类问题目前还没有找到多项式算法
并且人们普遍相信，
之所以我们找不到多项式算法，
并不是我们不够聪明，
而是问题本身具有某种固有属性造成的。
(BTW: 我们目前还没有办法从理论上证明对于NP问题多项式算法不存在，这个难题就是所谓的P ?= NP问题，乃是当前数学世界难题之一)
很遗憾的是，
广义上的博弈问题，包括围棋，
都属于NP问题。
(事实上围棋属于PSPACE完全问题，是NP问题中最难的一类)
以我的专业知识而言，
我相信对于围棋游戏不存在多项式算法(虽然还没有被证明)。

顺便说一下
电脑绝对不是万能的
也不可能超越人脑
有很多问题是电脑永远不可能解决而人能解决的
因为这些问题需要人的创造性思维
电脑的程序都是用有限的规则描述的机械算法
很多实际问题不存在一个机械的算法。
这样的问题在计算理论中称为 不可计算问题 (uncomputable problem)
最经典的一个不可计算问题就是所谓的图灵停机问题(halting problem)，
该问题和Hilbert第十问题相关。

停机问题，简单来说，
就是判断一个程序在某个输入下是否停机，
或者换句话说，判断这个程序在某个输入时是否会陷入死循环。

这个问题让人来作并不困难，
但是图灵在1936年就证明了不存在一个计算机程序能解决这个问题(其实他证明的是图灵机不可能解决此问题，但现在的计算机都是一种广义上的图灵机)。


由此可见电脑不可能超越人脑，
除非改进现有的体系，
然而根据Church-turing Thesis，
无论什么样的机械设备在计算能力上都不可能比现在的计算机更强大，
所以很有可能人脑是不可能被机器超越的，
虽然这个目前还没办法证明。

现在炒得很热的 DNA计算机，量子计算机，光计算机什么的，
本质上还是没能突破图灵机，
换汤不换药而已
(量子计算机比较特殊，从计算效率上来说他可能比现有的计算机高效的多，但目前为止这也只是一种可能)


不好意思，一时职业病发作，多说了几句。

starfish

TO: Veldrin
人脑只是在计算速度上不如计算机而已
单就计算能力而言
人脑的计算能力比计算机强太多了
很多不可计算问题人脑可以轻易解决。

Veldrin