m**********w
发帖数: 4161 | 1 特约记者李浩然报道
国际象棋、围棋和象棋的计算机对弈软件展开竞争的第15届计算机奥林匹克运动会2010
年秋在日本举行，日前，日本石川县能美市北陆尖端科学技术大学院大学已经在承办比
赛协议上签字。通常认为，电脑对弈软件最发达的是国际象棋领域，“更深的蓝”曾打
败了国象第一高手卡斯帕罗夫，但2009年计算机奥运会上，日本研制的围棋软件获得冠
军，值得期待。
被称为历史上最强的围棋对弈软件“天顶的围棋”被装载在思考引擎“Zen”上，09年5
月在西班牙举行的计算机奥运会上获得冠军，拥有业余3段-4段的棋力。
“天顶的围棋”软件比以前的对弈软件更加强大的秘诀在于“蒙特卡洛法”。蒙特卡洛
方法或称计算机随机模拟方法，是一种基于“随机数”的计算方法，这一方法源于美国
在一战中研制原子弹的“曼哈顿计划”。频率决定概率，围棋对弈软件将最常见的对弈
定式及棋形输入其中，从而达到较短时间提高棋力的功效。
计算机对弈软件十年来进步飞速，1997年IBM公司开发了国际象棋软件“更深的蓝”，
以2 胜1败3和打败了棋王卡斯帕罗夫。日本象棋(将棋)方面，2007年3月21日，在世界
最强的象棋电脑软件“Bona |
m**********w
发帖数: 4161 | 2 记者对蒙特卡洛一无所知啊。
冷剑来点评点评。
2010
年5
【在 m**********w 的大作中提到】
: 特约记者李浩然报道
: 国际象棋、围棋和象棋的计算机对弈软件展开竞争的第15届计算机奥林匹克运动会2010
: 年秋在日本举行，日前，日本石川县能美市北陆尖端科学技术大学院大学已经在承办比
: 赛协议上签字。通常认为，电脑对弈软件最发达的是国际象棋领域，“更深的蓝”曾打
: 败了国象第一高手卡斯帕罗夫，但2009年计算机奥运会上，日本研制的围棋软件获得冠
: 军，值得期待。
: 被称为历史上最强的围棋对弈软件“天顶的围棋”被装载在思考引擎“Zen”上，09年5
: 月在西班牙举行的计算机奥运会上获得冠军，拥有业余3段-4段的棋力。
: “天顶的围棋”软件比以前的对弈软件更加强大的秘诀在于“蒙特卡洛法”。蒙特卡洛
: 方法或称计算机随机模拟方法，是一种基于“随机数”的计算方法，这一方法源于美国
|
G*****o
发帖数: 315 | 3 记者对蒙特卡洛一无所知 很正常啊。
我比较奇怪的是蒙特卡洛算法已经存在很多年了。并且被广泛用在很多领域。直到最近
才有人把它用到
电脑围棋上。虽然是一个很有历史的算法，现在对蒙特卡洛的研究还很活跃。
我们最近设计了一个新的蒙特卡洛的算法并且检测了它在一个有二十年历史的问题上的
表现。我们的方
法比以前所有的方法都明显好。
我也是看到这篇文章之后才有点动心。现在太忙，没时间自己写code。
和manyfaces下了几盘以后，觉得以现在的发展速度，电脑围棋十年内应该赶不上职业
。对棋的强弱和
形式的判断是一个难题。
【在 m**********w 的大作中提到】
: 记者对蒙特卡洛一无所知啊。
: 冷剑来点评点评。
:
: 2010
: 年5
|
r****y
发帖数: 26819 | 4 蒙特卡罗对西方人最有刺激，他们不用自己懂围棋战术，而且能利用并行计算，所以程序
一下子有了很大进步。
但是蒙特卡罗还是不会算清死活题。所以，本质上没什么大进展。
只是在9X9的棋盘上进步很大，能跟高手下一下了。
2010
年5
【在 m**********w 的大作中提到】
: 特约记者李浩然报道
: 国际象棋、围棋和象棋的计算机对弈软件展开竞争的第15届计算机奥林匹克运动会2010
: 年秋在日本举行，日前，日本石川县能美市北陆尖端科学技术大学院大学已经在承办比
: 赛协议上签字。通常认为，电脑对弈软件最发达的是国际象棋领域，“更深的蓝”曾打
: 败了国象第一高手卡斯帕罗夫，但2009年计算机奥运会上，日本研制的围棋软件获得冠
: 军，值得期待。
: 被称为历史上最强的围棋对弈软件“天顶的围棋”被装载在思考引擎“Zen”上，09年5
: 月在西班牙举行的计算机奥运会上获得冠军，拥有业余3段-4段的棋力。
: “天顶的围棋”软件比以前的对弈软件更加强大的秘诀在于“蒙特卡洛法”。蒙特卡洛
: 方法或称计算机随机模拟方法，是一种基于“随机数”的计算方法，这一方法源于美国
|
r****y
发帖数: 26819 | 5 我半年前把蒙特卡罗用于围棋的paper都找来通读了一遍，也没时间做。
【在 G*****o 的大作中提到】
: 记者对蒙特卡洛一无所知 很正常啊。
: 我比较奇怪的是蒙特卡洛算法已经存在很多年了。并且被广泛用在很多领域。直到最近
: 才有人把它用到
: 电脑围棋上。虽然是一个很有历史的算法，现在对蒙特卡洛的研究还很活跃。
: 我们最近设计了一个新的蒙特卡洛的算法并且检测了它在一个有二十年历史的问题上的
: 表现。我们的方
: 法比以前所有的方法都明显好。
: 我也是看到这篇文章之后才有点动心。现在太忙，没时间自己写code。
: 和manyfaces下了几盘以后，觉得以现在的发展速度，电脑围棋十年内应该赶不上职业
: 。对棋的强弱和
|
G*****o
发帖数: 315 | 6 能把paper给我发过来研究研究吗？谢谢。
【在 r****y 的大作中提到】
: 我半年前把蒙特卡罗用于围棋的paper都找来通读了一遍，也没时间做。
|
k*******u
发帖数: 266 | 7 同问同问
【在 G*****o 的大作中提到】
: 能把paper给我发过来研究研究吗？谢谢。
|
r****y
发帖数: 26819 | 8 http://www.megaupload.com/?d=H71BRD2K
【在 G*****o 的大作中提到】
: 能把paper给我发过来研究研究吗？谢谢。
|
r****y
发帖数: 26819 | 9 我当时拿到的都上传了。这些在欧洲的作者都很不错，找他们要paper都给，还主动
update。不过最近我不打算做了。
【在 k*******u 的大作中提到】
: 同问同问
|
d**h
发帖数: 364 | 10 死活题可以局部搜索来解决啊,这方面程序比人强.
程序
【在 r****y 的大作中提到】
: 蒙特卡罗对西方人最有刺激，他们不用自己懂围棋战术，而且能利用并行计算，所以程序
: 一下子有了很大进步。
: 但是蒙特卡罗还是不会算清死活题。所以，本质上没什么大进展。
: 只是在9X9的棋盘上进步很大，能跟高手下一下了。
:
: 2010
: 年5
|
|
|
r****y
发帖数: 26819 | 11 我的直觉也是这么想的，但好像还没有一个程序能完全解决局部封闭死活，目前为止，
人还是比程序厉害得多。要是谁来做，不妨从这个开始下手，如果有所成，倒回去再
借用现成的开源部分，估计比较厉害。
【在 d**h 的大作中提到】
: 死活题可以局部搜索来解决啊,这方面程序比人强.
:
: 程序
|
m**********w
发帖数: 4161 | 12 金柜角能搞定就行啊。
【在 r****y 的大作中提到】
: 我的直觉也是这么想的，但好像还没有一个程序能完全解决局部封闭死活，目前为止，
: 人还是比程序厉害得多。要是谁来做，不妨从这个开始下手，如果有所成，倒回去再
: 借用现成的开源部分，估计比较厉害。
|
a*****g
发帖数: 19398 | |
G*****o
发帖数: 315 | |
d***a
发帖数: 13752 | 15 如果是4x4局面，我可以写一个程序来算。5x5的局面，计算量恐怕就
会过大。当然，这是就我的水平而言。
【在 r****y 的大作中提到】
: 我的直觉也是这么想的，但好像还没有一个程序能完全解决局部封闭死活，目前为止，
: 人还是比程序厉害得多。要是谁来做，不妨从这个开始下手，如果有所成，倒回去再
: 借用现成的开源部分，估计比较厉害。
|
d***a
发帖数: 13752 | 16 我想到了一个brute force的办法，可以完整解决5x5封闭
局面死活，但需要大量的存储容量。但这个办法对于6x6
的封闭局面无能为力，除非现在的计算机速度和存储容量
提高一万七千倍。:-)
我对计算机围棋水平的提高不看好，很有可能在实际中无
法超过最好的人类棋手。 |
a*****g
发帖数: 19398 | 17 (5x5)! = 1.55E+25
强攻也许有希望
【在 d***a 的大作中提到】
: 我想到了一个brute force的办法，可以完整解决5x5封闭
: 局面死活，但需要大量的存储容量。但这个办法对于6x6
: 的封闭局面无能为力，除非现在的计算机速度和存储容量
: 提高一万七千倍。:-)
: 我对计算机围棋水平的提高不看好，很有可能在实际中无
: 法超过最好的人类棋手。
|
j***i
发帖数: 4975 | 18 这个将棋软件怎么在残局败掉了？还是在优势的情况下
2010
年5
【在 m**********w 的大作中提到】
: 特约记者李浩然报道
: 国际象棋、围棋和象棋的计算机对弈软件展开竞争的第15届计算机奥林匹克运动会2010
: 年秋在日本举行，日前，日本石川县能美市北陆尖端科学技术大学院大学已经在承办比
: 赛协议上签字。通常认为，电脑对弈软件最发达的是国际象棋领域，“更深的蓝”曾打
: 败了国象第一高手卡斯帕罗夫，但2009年计算机奥运会上，日本研制的围棋软件获得冠
: 军，值得期待。
: 被称为历史上最强的围棋对弈软件“天顶的围棋”被装载在思考引擎“Zen”上，09年5
: 月在西班牙举行的计算机奥运会上获得冠军，拥有业余3段-4段的棋力。
: “天顶的围棋”软件比以前的对弈软件更加强大的秘诀在于“蒙特卡洛法”。蒙特卡洛
: 方法或称计算机随机模拟方法，是一种基于“随机数”的计算方法，这一方法源于美国
|
r******y
发帖数: 3838 | 19 有业余初段以上的谱吗。看过一个，但没激烈的战斗，不能说明什么。 |
r****y
发帖数: 26819 | 20 mogo 9X9对周俊勋的谱很容易google到
【在 r******y 的大作中提到】
: 有业余初段以上的谱吗。看过一个，但没激烈的战斗，不能说明什么。
|
|
|
B****n
发帖数: 11290 | 21 將棋我不懂 不過我看過電腦下象棋 那個程序的水平很高 可是到了殘局階段就走一些
連我這種低水平的也看出來是爛棋 最後在中局佔優的情況被頂和了
那棋有作者的自述講解 他說傳統認為電腦象棋的殘局特別強 這不全對 他說電腦的戰
術方面很強 比方說得子 攻殺 各樣的戰術手段既豐富 算得也快又準 但是對於戰略性
的殘局就比人腦差不少 尤其是那種不是很具體知道要幹什麼 需要靠對殘局棋型有深刻
經驗和理解 調整型 或是制定長期方向的 這種電腦特別差 我對照他講的這種觀念看了
一下實戰 覺得他說的挺有道理的
【在 j***i 的大作中提到】
: 这个将棋软件怎么在残局败掉了？还是在优势的情况下
:
: 2010
: 年5
|
m*d
发帖数: 103 | 22 不太懂，为什么要蒙特卡洛？不是把所有可能遍历一遍吗。 |
N***b
发帖数: 268 | 23 蒙特卡罗是用重要抽样，随机马科夫过程，施加转换概率，不必遍历，比较适合围棋，
不过最大的障碍是能搞定多大区域，遗传算法，神经网络，这些
东西和围棋早就有人搞，主要是日本人,成果未曾耳闻
【在 m*d 的大作中提到】
: 不太懂，为什么要蒙特卡洛？不是把所有可能遍历一遍吗。
|
s*****e
发帖数: 16824 | 24 不可能把所有可能遍历一遍，搜索空间太大了，所以才需要用蒙特卡洛作采样。
【在 m*d 的大作中提到】
: 不太懂，为什么要蒙特卡洛？不是把所有可能遍历一遍吗。
|
d***a
发帖数: 13752 | 25 我不知道这个将棋程序有没有使用残局库。国际象棋程序普遍
使用残局库，如果局面进入了这个残局库的范围，人类棋手就再
也不能超过电脑，因为电脑精确知道每一局面下的正确走法。
但在这个残局库范围之外，电脑就不如人类大师级棋手，因为人
类棋手可以使用残局理论来指导计算，电脑算不了那么远。
国际象棋程序现在知道所有六子残局的完美走法，就是说盘上最
多有六个子，如王后兵对王双车。有一些七子残局的局面也知道。
【在 B****n 的大作中提到】
: 將棋我不懂 不過我看過電腦下象棋 那個程序的水平很高 可是到了殘局階段就走一些
: 連我這種低水平的也看出來是爛棋 最後在中局佔優的情況被頂和了
: 那棋有作者的自述講解 他說傳統認為電腦象棋的殘局特別強 這不全對 他說電腦的戰
: 術方面很強 比方說得子 攻殺 各樣的戰術手段既豐富 算得也快又準 但是對於戰略性
: 的殘局就比人腦差不少 尤其是那種不是很具體知道要幹什麼 需要靠對殘局棋型有深刻
: 經驗和理解 調整型 或是制定長期方向的 這種電腦特別差 我對照他講的這種觀念看了
: 一下實戰 覺得他說的挺有道理的
|
O****X
发帖数: 24292 | 26 你的象棋水平是多少？
我老嚼着你可能水平太差，而看不懂人家的棋
现在算机的象棋残局水平已经很高了，国内搞的人机合一，就是让人看虚路，而残局这
些都靠软件计算验证，这样已经可以和吕钦银川这样的特大打平了
【在 B****n 的大作中提到】
: 將棋我不懂 不過我看過電腦下象棋 那個程序的水平很高 可是到了殘局階段就走一些
: 連我這種低水平的也看出來是爛棋 最後在中局佔優的情況被頂和了
: 那棋有作者的自述講解 他說傳統認為電腦象棋的殘局特別強 這不全對 他說電腦的戰
: 術方面很強 比方說得子 攻殺 各樣的戰術手段既豐富 算得也快又準 但是對於戰略性
: 的殘局就比人腦差不少 尤其是那種不是很具體知道要幹什麼 需要靠對殘局棋型有深刻
: 經驗和理解 調整型 或是制定長期方向的 這種電腦特別差 我對照他講的這種觀念看了
: 一下實戰 覺得他說的挺有道理的
|
B****n
发帖数: 11290 | 27 我的水平是差阿 不過差不差原本就是相對的 我更不會對一個根本不了解的人說他水平
差阿 呵呵
象棋能夠和許銀川這種頂級的特級大師差不多也就是這兩三年的事情
【在 O****X 的大作中提到】
: 你的象棋水平是多少？
: 我老嚼着你可能水平太差，而看不懂人家的棋
: 现在算机的象棋残局水平已经很高了，国内搞的人机合一，就是让人看虚路，而残局这
: 些都靠软件计算验证，这样已经可以和吕钦银川这样的特大打平了
|
O****X
发帖数: 24292 | 28 将族的残局水平已经狠强了，我见过国家大师拿将族练习残棋的
【在 B****n 的大作中提到】
: 我的水平是差阿 不過差不差原本就是相對的 我更不會對一個根本不了解的人說他水平
: 差阿 呵呵
: 象棋能夠和許銀川這種頂級的特級大師差不多也就是這兩三年的事情
|
w****i
发帖数: 964 | 29 即使是用蒙特卡洛法，不减枝的话sample的那点样本根本无法代表指数增长的变化
，再多cpu都没用，MOGO的减枝是搜索上一步3x3范围，加上一些打吃破眼的人为规则，
有明显的缺陷，也是限制其水平的主要因素。这个银星围棋估计是在减枝上改善了一些
，日本人很善于干这种fine tune的活。蒙特卡洛法只是一种模糊搜索法，在某些方面
比传统的搜索效率高，但是仍然无法绕开减枝问题，电脑围棋的真正瓶颈还是在于高效
准确的减枝算法，也许让程序自己学习怎样减枝是一个方向。 |
R*******n
发帖数: 428 | |
|
|
n****g
发帖数: 14743 | |
d***a
发帖数: 13752 | 32 写得很好。不过，围棋过于依赖于Moore's Law是不行的。
Moore's Law六十年的发展，处理复杂度的提高相当于从
5x5棋盘复杂度发展到8x8的棋盘复杂度。Moore's Law
已经提出了五十年，再发展十年没有问题，但之后就很
难说了。
【在 R*******n 的大作中提到】
: 人机对话 http://www.mitbbs.com/article_t/Go/31166952.html
|
g*****g
发帖数: 34805 | 33 围棋的复杂度大约10^170次方，国象大约10^50，
如果纯粹靠速度搜索，没有算法改进，要10^120，
相当于2^400次方，就算计算能力每年加倍，要
400年。
事实上计算能力无法每年加倍，但算法可以改进。
所以我估计要100年左右才行。
【在 d***a 的大作中提到】
: 写得很好。不过，围棋过于依赖于Moore's Law是不行的。
: Moore's Law六十年的发展，处理复杂度的提高相当于从
: 5x5棋盘复杂度发展到8x8的棋盘复杂度。Moore's Law
: 已经提出了五十年，再发展十年没有问题，但之后就很
: 难说了。
|
j***i
发帖数: 4975 | 34 原来如此
不过本来到了残局
局面简化后
正是计算能力发挥作用的地方啊。。。
神奇神奇
【在 B****n 的大作中提到】
: 將棋我不懂 不過我看過電腦下象棋 那個程序的水平很高 可是到了殘局階段就走一些
: 連我這種低水平的也看出來是爛棋 最後在中局佔優的情況被頂和了
: 那棋有作者的自述講解 他說傳統認為電腦象棋的殘局特別強 這不全對 他說電腦的戰
: 術方面很強 比方說得子 攻殺 各樣的戰術手段既豐富 算得也快又準 但是對於戰略性
: 的殘局就比人腦差不少 尤其是那種不是很具體知道要幹什麼 需要靠對殘局棋型有深刻
: 經驗和理解 調整型 或是制定長期方向的 這種電腦特別差 我對照他講的這種觀念看了
: 一下實戰 覺得他說的挺有道理的
|
r****y
发帖数: 26819 | 35 常规做法是这样的，博弈树内的节点用exploration/exploitation折衷，博弈树外的节点
用蒙特卡罗仿真。
【在 w****i 的大作中提到】
: 即使是用蒙特卡洛法，不减枝的话sample的那点样本根本无法代表指数增长的变化
: ，再多cpu都没用，MOGO的减枝是搜索上一步3x3范围，加上一些打吃破眼的人为规则，
: 有明显的缺陷，也是限制其水平的主要因素。这个银星围棋估计是在减枝上改善了一些
: ，日本人很善于干这种fine tune的活。蒙特卡洛法只是一种模糊搜索法，在某些方面
: 比传统的搜索效率高，但是仍然无法绕开减枝问题，电脑围棋的真正瓶颈还是在于高效
: 准确的减枝算法，也许让程序自己学习怎样减枝是一个方向。
|
r******y
发帖数: 3838 | 36 要看其他计算方式如量子计算什么时候能突破。如果能算尽，能让9段几个子？
【在 g*****g 的大作中提到】
: 围棋的复杂度大约10^170次方，国象大约10^50，
: 如果纯粹靠速度搜索，没有算法改进，要10^120，
: 相当于2^400次方，就算计算能力每年加倍，要
: 400年。
: 事实上计算能力无法每年加倍，但算法可以改进。
: 所以我估计要100年左右才行。
|
w****i
发帖数: 964 | 37 right, the problem with current MC approach is in the simulation rule, which
can't avoid the pruning problem,
which is what I meant.
BTW, I can't download the papers you uploaded, could you share them again?
节点
【在 r****y 的大作中提到】
: 常规做法是这样的，博弈树内的节点用exploration/exploitation折衷，博弈树外的节点
: 用蒙特卡罗仿真。
|
r****y
发帖数: 26819 | 38 我刚试了一下，还可以下载
如果还是不行，给我留email信箱
which
【在 w****i 的大作中提到】
: right, the problem with current MC approach is in the simulation rule, which
: can't avoid the pruning problem,
: which is what I meant.
: BTW, I can't download the papers you uploaded, could you share them again?
:
: 节点
|
