围棋AI到底有多难？ 是不是最难写的AI我不知道 不过从1969年有人写出围棋程式之後到现在 依然距离职业围棋手有约3~4子的差距 跟顶尖的围棋手的差距可就更大了。 这还是最近5年左右有人发现蒙地卡罗演算法 可以应用到围棋上的成果 不然如果使用传统的暴力法或比较Pattern法 也许50年以上也无法下赢人类。 很多人提到围棋是属於公开化资讯的比赛,规则又很简单 听起来AI应该不难写才是，理论上超级电脑越来越快 将来可预期的某一天大概轻易KO这个问题。 但围棋难的地方不在规则，在於提子(吃子),又可以打劫 (棋盘同个位置有重复落子的可能性) 让他的计算量大幅提昇, 甚至超过 10^600种变化(有争议,也有人认为更多) 这个计算数量基本上比宇宙中原子的总和还要多 想要算出必胜下法可说绝无可能。 围棋有趣的地方在於你问那些棋手为何要下这里, 常常获得的答案也是说 这是靠「感觉」而不是计算 给十个人来看这手棋，十一个人的看法都不一样。 甚至有时看似坏棋，到尾盘时又意外变成好棋。 也有故意将子送给对方以为是来送死，其实是陷阱等等方法 这些都是由於变化量实在太大，人脑也算不清楚的原因。 但人脑最强的地方,刚好在於对未知的"答案"可以靠过去的经验 做某种程度的"预测"跟推估，即使是没看过的情况也可以做出"大概方向正确" 的判断(虽然这判断也是见仁见智)，而电脑并没有这种能力。 在这种既不能用暴力法求解的情况下，电脑就失去了优势， 过去传统围棋程式的写法只能靠历史棋谱取出的pattern 或人类一些"经典"下法的pattern来"教"电脑怎样下较好，例如早期的世界冠军 GNU GO就是这样写的，这种电脑围棋软体的特色就是下棋方法跟人类很像。 但这样的软体需要依靠程式设计师很会下围棋才行，还必须想出个逻辑给电脑 实际上人类无法也很难把自我的模糊判断逻辑写出来， 所以电脑围棋的棋力一直都很挣扎。 即使後来有发明类神经演算法,基因演算法等 但因为变化量实在太大，也很难藉由大量的棋谱训练让电脑归纳出下围棋的逻辑 基於以上几点理由在2000年左右时，对於围棋AI可以下赢电脑这件事 所有人都很悲观。 直到最近五年终於有一个革命性的演算法 -蒙地卡罗演算法被发明应用在围棋让电脑围棋AI突飞猛进， 目前已经变成主流的围棋演算法(没有之一) 简单介绍一下蒙地卡罗演算法，其实发明的来由也挺有趣的 这演算法本来是使用在赌场来模拟哪台吃角子老虎比较容易 赢钱。有很多种应用，现在则是被发现可以拿来模拟围棋。 原理其实很简单 就是对手下完每一步後用电脑随便乱下到终局看谁赢 再倒推当时下哪手赢棋的机率较高，说穿了也是某种暴力法 (本来是用在赌博机,去玩几道看看机台看营收,再推估哪台 机台之後赢钱机率较高)。这种演算法好处是程式人员 不用太懂围棋，一切回归数学跟演算法，但一样相当吃系统资源。 而这类演算法的围棋程式有个特色是下棋不太像是人类 常常使用不可思议的手段(正常人类不会有的思维)来跟人类对奕 这也正是围棋令人着迷之处，也许我们从小也是被老师或书籍 教导围棋，所谓的经验法则也是前人遗传下来的，这种演算法 反而没有这种包袱，只要可以赢棋就好，故可以下出人世间惊世骇俗的手段 或许我们人类所找出的"合理"的下法也只是众多下法的一小部分而已呢！ 当然啦，这个演算法虽然是围棋AI的明日之星，常有佳作 但围棋一盘棋双方可以下出几百手，不是几手棋就可以决定胜负, 目前棋力上还是无法跟顶尖棋手对抗,仍有待程式设计师持续努力。 在这里提供个连结是目前围棋 世界冠军ZEN的程式人员的访谈笔记，简体的,有兴趣的人可以去看看。 http://9songs.cn/thread-1104-1-1.html 目前开源的围棋AI程式最有名的就是GNU GO 每一版本的程式都可以下载来看，我有实际下载过 在linux comiler可以跑，有兴趣也可以去抓来看XD 最新开发中的程式好像也有写基本的蒙地卡罗演算法。 这个AI的难度，人类差不多也要学半年以上才有可能可以下赢他 算是挺厉害的程式了啦！当然目前在世界围棋程式排行榜 应该已经落到十名以外了，但想要学棋类游戏AI的还是很有参考价值。 GNU GO开发首页 http://www.gnu.org/software/gnugo/gnugo.html 另外还有一个对岸的围棋AI论坛，里面也有一些有价值的程式资讯可以参考 http://www.computergo.net/forum/index.php ※ 引述《yoco315 (眠月)》之铭言： : ※ 引述《LaPass (LaPass)》之铭言： : : 总而言之，在围棋中要面对的是很模糊的计算 : : 这跟SLG跟其他棋类是很明显的差异 : 其实我也觉得这是一个很常见的误解耶。 : 我先讲结论：一般战棋类的 SLG 复杂度比围棋高。 : 这好像很难想像，但是原因其实是因为一般人根本没「想」过这个问题。 : 小弟试问一个问题：有人认真的去分析过一般 SLG 的复杂度吗？ : 比方说魔唤精灵、风色幻想、或是星海争霸？甚至一般 RPG 的战斗？ : 不要误会，我不是说围棋简单， : 围棋很难，我是说那些游戏更难。 : 围棋的难因为有被展现跟强调出来，所以大家都知道围棋很难。 : 因为围棋是一个有长久历史跟大量人类在从事，而且已经职业化的活动。 : 广为人知，也有很多研究者在做这个题目，所以人们注意到他很难， : 不过这不代表他最难。 : 别的不说，光是 partial observe 在 AI 就是一个让难度翻好几翻的因素。 : 围棋的玩家可以看到全部的盘面(full observe)， : 但是绝大部分 full observe 的 AI，到了 partial observe 就根本不能用， : 看不到的东西，你连 search 都没办法，这才是真的模糊运算 :( : 又或是「混乱」，这种状态的转移带有随机性的， : 还要导入 Markov Decision Process 才能分析。 : "Partial observe" 加上 "Markov Decision Process" 这两个东西放在一起， : 念 AI 的看到都会吓到闪尿 Q_Q 不知道的可以 google 一下 "POMDP" 看一下。 : 假设未来有一天，电脑的计算力强到可以在围棋上打赢人类， : 那个时候大家会发现在很多别的游戏上面，AI 跟人差很多， : 才会注意到原来很多别的游戏都比围棋难。 -- 快乐的时光,总是过得特别快, 等到想珍惜时,却已经变成回忆 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 118.169.43.171