博弈程序的当前发展水平 - 体坛动力 - 轩辕春秋文化论坛 20周年


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#1

发表于 2005-1-28 20:39 资料主页个人空间短消息只看该作者

1。国际象棋：
“决定性的比赛是第二局，它在我的记忆中留下了伤痕。。。我们看到远远超出我们最疯狂想象的事情，计算机能够预见它的决策中的长期棋局序列。机器拒绝走一步有决定性短期优势的棋--显示了非常类似于人类对危险的感觉。（卡斯帕罗夫  1997）

当时深蓝的算法是使用调换表的标准叠代深入ALPHA-BETA搜索，平均每秒搜索12.6亿个节点，峰值33亿个节点，每步最多生成300亿个棋局，常规搜索深度是14层，有必要时可以达到40层

深蓝的成功使人们有了这么一个想法：博弈水平的提高来自更强大的硬件。但搜索扩展和评价函数也是至关重要的。最近的一些算法改进使在标准微机上的程序可以赢得1992年来的每届计算机国际象棋冠军赛。

最近的主要赛事是程序FRITZ挑战克拉姆尼克。比赛共8局，双方战平。不过程序FRITZ运行在一台普通微机上。克拉姆尼克的评价是：“现在很明显顶级的程序和世界冠军几乎可以平起平坐了”。（这样的程序我也想要，这样就可以纵横联众了。。。  ）

2：西洋跳棋

1952年开始，ARTHUR SAMUEL开发了一个会通过自己大量下棋学习评价函数的西洋跳棋程序。程序仅用了几天时间水平就超过ARTHUR SAMUEL本人  1962年它利用对方的失误击败“蒙目西洋跳棋”冠军ROBERT NEALY。

很少有人试图做得更好，直到JONATHAN SCHAEFFER（AE表示A上面有两点，偶不是德语键盘，打不出来  ）和他的同事门开发了使用ALPHA-BETA搜索的CHINOOK。CHINOOK使用了提前计算好的4440亿个不多于8个子的棋局数据库，使它走残局没有缺陷。很快，CHINOOK遇到了麻烦，MARION TINSLEY。MARION TINSLEY是40多年的世界冠军，在所有的比赛中只输过三盘（世界上居然有这样的流氓  他的垄断地位超过MICHAEL SCHUMACHER）在一次与CHINOOK对弈中，MARION TINSLEY遭遇到了职业生涯的第四败和第五败，但还是以20.5比18.5赢得了整个比赛（这丫太强劲了  ）

1994年世界冠军赛中，MARION TINSLEY和CHIROOK继续对垒，不过MARION TINSLEY以健康原因退出，于是CHIROOK正式成为世界冠军

3：奥塞罗（翻转棋，黑白棋）

可能奥塞罗作为计算机游戏更加流行。它每步只有5~15个合法行棋，搜索空间很小。1997年，LOGISTELLO的程序（BURO2002<-这里可能U上少两点，翻译成中文就是“办公室2002”）以6：0草割世界冠军TAKESHI MURAKAMI。目前一般都承认人类在翻转棋方面无法和计算机抗衡

4：西洋双陆棋

这是一种需要骰子的游戏，GERRY TESAURO把SAMUEL的强化学习方法和神经网络技术结合，经过上百万次的自我下棋  ，GERRY TESAURO的程序TD-GAMMON稳居世界前三

5：围棋

这不用说了吧，太惨淡了。

6：桥牌

桥牌是一种不完整信息的游戏，包括信息搜集，交流，欺骗和权衡概率。
1997年的世界冠军程序BRIDGE BARON还包含了飞牌，挤牌等高级思想。

2000年的计算机冠军GIB虽然在信息推理上有欠缺，但它可以准确解决每一副牌。在1998年参加人类标准桥牌冠军赛（只涉及主打。由计算机发牌，每个牌手主打相同的牌，以考察选手的功力）。在35名选手中，偶们可爱的程序排名第12。

补充：

做西洋跳棋的SCHAEFFER相信，如果有足够的计算能力，残局库足够大（4440亿还嫌不够  ），使得前向搜索从初始棋局能达到已经解决的棋局，西洋跳棋可以完全解决。

这种彻底的分析对于3*3井字棋可以手工完成  对于QUBIC（4*4*4井子棋），五字棋（GO-MOKU）和九人莫里斯游戏（NINE MAN’S MORRIS）的分析也已经由计算机完成

不过哪里能下载我就不知道了

[广告] 真诚支持说岳，携手共创辉煌


	斜出正入


	白衣伯爵中大夫

组别	白衣卿相
级别	安西将军
好贴	2
功绩	230
帖子	3092
编号	742
注册	2003-9-13

#2

发表于 2005-1-28 21:46 资料文集短消息只看该作者

呵呵，在棋类游戏上，人类迟早会被电脑横扫。但是正如汽车跑得比人快，奥运会照样有赛跑一样，人VS人的棋类竞赛依然会继续。网上例外，现在已经是到处软件横行，到那时候就不用玩了。象网络台球，原先挺红火的，瞄准器一出来，还玩个P~最惨是象我这样的，玩游戏从来不认真，平时臭杆一堆，偶然精神来了弄几盘一杆清台的，还要被怀疑用外挂不过也有一两年没玩网游了，不知道现在情形怎么样？

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#3

发表于 2005-1-28 21:58 资料主页个人空间短消息只看该作者

QUOTE:

原帖由斜出正入于2005-01-28, 21:46:53发表
呵呵，在棋类游戏上，人类迟早会被电脑横扫。但是正如汽车跑得比人快，奥运会照样有赛跑一样，人VS人的棋类竞赛依然会继续。网上例外，现在已经是到处软件横行，到那时候就不用玩了。象网络台球，原先挺红火的，瞄准器一出来，还玩个P~最惨是象我这样的，玩游戏从来不认真，平时臭杆一堆，偶然精神来了弄几盘一杆清台的，还要被怀疑用外挂不过也有一两年没玩网游了，不知道现在情形怎么样？

人和电脑玩的历史也不长。不过电脑程序比较叼~~专找世界冠军玩

要是偶能弄到上面程序之一，偶就天下无敌了

置于台球，还好吧~~
网上台球毕竟和现实台球不一样的。

小角度进球，开球进球，翻连N次袋在现实台球里不现实，但游戏里偶也能轻松做到。偶现在还偶尔玩玩联众台球，尽量不要和那些胜率离谱的人来就是了。

关于网络，说不定也是程序VS程序

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	Maxwell


	代王监管使枢密直学士山南西道节度使 ★

组别	诸侯
级别	征东将军
好贴	4
功绩	1845
帖子	5801
编号	622
注册	2004-7-7

#4

发表于 2005-1-28 21:58 资料文集短消息只看该作者

呵呵，围棋的应该仔细讲讲，好像现在跟业余棋手下还是有余了。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#5

发表于 2005-1-28 22:04 资料主页个人空间短消息只看该作者

围棋和其它棋不一样（同样比较复杂的还有将棋，将棋吃掉的子是可以随时放回棋盘的），围棋的数据库有多大？
ALPHA—BETE搜索能搜索围棋吗？国际象棋平均一步35个分支电脑才勉强。

现在的方法不能很好地解决围棋，但人们能做的只是改进现在的方法，加强剪枝，所以没什么可说的。

[广告] 真诚支持说岳，携手共创辉煌


	斜出正入


	白衣伯爵中大夫

组别	白衣卿相
级别	安西将军
好贴	2
功绩	230
帖子	3092
编号	742
注册	2003-9-13

#6

发表于 2005-1-28 22:11 资料文集短消息只看该作者

QUOTE:

原帖由天痕于2005-01-28, 22:04:44发表
围棋和其它棋不一样（同样比较复杂的还有将棋，将棋吃掉的子是可以随时放回棋盘的），围棋的数据库有多大？
ALPHA—BETE搜索能搜索围棋吗？国际象棋平均一步35个分支电脑才勉强。

现在的方法不能很好地解决围棋，但人们能做的只是改进现在的方法，加强剪枝，所以没什么可说的。

围棋程序比较弱，以前有个好象叫go什么的？大家都是以吃光它的子为乐

[广告] 真诚支持说岳，携手共创辉煌


	马岱


	衡山郡王知枢密院事

组别	经略使
级别	大将军
好贴	31
功绩	2443
帖子	19416
编号	10
注册	2003-8-20
来自	深圳

#7

发表于 2005-1-28 22:30 资料主页文集短消息只看该作者

围棋不光是数据库的问题，围棋的很多原理不是用逻辑能解释通的，围棋的大局观和空间观，计算机现在还不能深刻理解。

[广告] 真诚支持说岳，携手共创辉煌


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#8

发表于 2005-1-28 22:35 资料主页个人空间短消息只看该作者

QUOTE:

原帖由马岱于2005-01-28, 22:30:01发表
围棋不光是数据库的问题，围棋的很多原理不是用逻辑能解释通的，围棋的大局观和空间观，计算机现在还不能深刻理解。

电脑下棋本来就不是逻辑

QUOTE:

“决定性的比赛是第二局，它在我的记忆中留下了伤痕。。。我们看到远远超出我们最疯狂想象的事情，计算机能够预见它的决策中的长期棋局序列。机器拒绝走一步有决定性短期优势的棋--显示了非常类似于人类对危险的感觉。（卡斯帕罗夫 1997）

所谓的空间观大局观都是评价函数的一部分，这个只是搜索水平的体现~~

[广告] 《精忠报国岳飞传完整版》火热发布


	斜出正入


	白衣伯爵中大夫

组别	白衣卿相
级别	安西将军
好贴	2
功绩	230
帖子	3092
编号	742
注册	2003-9-13

#9

发表于 2005-1-28 22:41 资料文集短消息只看该作者

QUOTE:

原帖由天痕于2005-01-28, 22:35:59发表
电脑下棋本来就不是逻辑

所谓的空间观大局观都是评价函数的一部分，这个只是搜索水平的体现~~

是的，计算机干的就是暴力搜索，到达一定极限（层数）以后，如果没有明显结果（胜、负），接下来就交给评价函数了。评价函数的运算结果，就决定了电脑的“大局观”。

[广告] 真诚支持说岳，携手共创辉煌


	马岱


	衡山郡王知枢密院事

组别	经略使
级别	大将军
好贴	31
功绩	2443
帖子	19416
编号	10
注册	2003-8-20
来自	深圳

#10

发表于 2005-1-28 22:43 资料主页文集短消息只看该作者

问题是围棋很多步数都是，要到以后才看出好坏来，这对电脑很要命。

[广告] 真诚支持说岳，携手共创辉煌


	首席屠宰官 (鲁吹一号)


	隐鲁郡王 ★

组别	轩辕公主
级别	大将军
好贴	2
功绩	172
帖子	11073
编号	12
注册	2003-8-19

#11

发表于 2005-1-28 22:58 资料个人空间短消息只看该作者

如果下17格围棋，电脑可能有聂棋圣的水平了

[广告] 《精忠报国岳飞传完整版》火热发布


	气流


	上郡公枢密直学士

组别	翰林学士
级别	征东将军
好贴	2
功绩	949
帖子	5449
编号	131
注册	2003-8-25

#12

发表于 2005-1-29 00:19 资料文集短消息只看该作者

QUOTE:

原帖由天痕于2005-01-28, 21:58:21发表
要是偶能弄到上面程序之一，偶就天下无敌了

用不着“上面程序之一”。网上下棋的人，极少有能打败ChessMaster7000的。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	斜出正入


	白衣伯爵中大夫

组别	白衣卿相
级别	安西将军
好贴	2
功绩	230
帖子	3092
编号	742
注册	2003-9-13

#13

发表于 2005-1-29 13:30 资料文集短消息只看该作者

电脑的长处是计算，弱点是只会计算，哈哈~
比如下面这个小杀局，中等水平的人类棋手解它基本上不会有啥问题，这个问题分解一下就变得简单了。电脑（目前）却是要傻呵呵的从头算到尾的，曾经试用过一个号称拥有“大师”级棋力的软件，搜索深度设定15层，我执黑跟它来回纠缠了十几个回合，结果它还是没搞定，嘿嘿！不知道现在的软件是不是强一点了（曾几何时，电脑连海底捞月都做不出来呢）？谁有的话可以试一试，贴个测试报告上来，破掉了奖励100通宝

图片附件: 未命名.jpg (2005-1-29 13:30, 14.65 K)

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	斜出正入


	白衣伯爵中大夫

组别	白衣卿相
级别	安西将军
好贴	2
功绩	230
帖子	3092
编号	742
注册	2003-9-13

#14

发表于 2005-1-30 22:05 资料文集短消息只看该作者

没有能破的吗还是嫌奖金太少？
追加100，一共200，不能再多了，俺可是穷苦百姓来的，比不得贪官污吏啊~

[广告] 真诚支持说岳，携手共创辉煌