标题: 【转贴】围棋与计算机 [打印本页]
作者:
武骧金星 时间: 2007-9-15 11:57 标题: 【转贴】围棋与计算机
一 从地球到月球
从电脑诞生之日起，人们对于电脑就充满了幻想。尤其是在人工智能上，对于电脑超过人脑，有人兴奋，有人担忧，但曾经几乎所有人都认为这会是真的。尤其当“深蓝”击败卡斯帕罗夫之后，人们已经开始担忧，电脑超过人脑，会不会就发生在明天？
但这种担忧实在是来的太早了。
本世纪七八十年代,对人工智能学家们来说，就象是无忧无虑的童年。他们雄心勃勃，甚至排出了电脑替代人脑的时间表。在表中，现在，就已经应该是电脑超过人脑的日子了。现在，“深蓝”确实战胜了卡斯帕罗夫，但人工智能学家们的时间表早已被抛到了脑后。有人甚至打了这样一个比喻来说明人工智能上所取得的成就：人们想登上月球，他们造了一个梯子，用这个梯子爬上了一棵树，然后自豪地宣称：“现在，我们已向月球前进了一大步！”
现在，电脑已经渗入到了我们生活的各个方面，在生产和生活中，我们已经有些难以想象脱离电脑的状况了，如果说这些形形色色的电脑只不过是花里胡哨的各种梯子，似乎实在是说不过去。
我们先看看梯子是怎么回事吧。
梯子的发明人是图灵博士。图灵在考虑可计算的机器的性质时，首先是设想一个人在计算，他把这个人的计算行为抽象成了这样一台机器：有一条无穷长的纸带子，一个有很多状态的机器在纸带上左右滑动，并且可以根据所读到的内容改变自己的状态或者改写纸带的内容。这就是大名鼎鼎的图灵机了。当前的所有计算机，在理论上都是可以被图灵机模拟的。
请注意图灵机有一个重要的能力：改写纸带的能力。如果没有这个能力，那这台机器叫做有穷自动机。它和图灵机间的计算能力差着三个档次呢。（注意：在一条无穷长的纸带上读东西，在另一条纸带上写东西的机器也是有穷自动机）。
判断这些东西的计算能力用的是这些机器所能接受的语言的概念 。这个语言虽然是抽象的语言，但也和我们平时所说的语言差不多，你只要理解成这机器能听懂什么话也就差不太多了。乔姆斯基把语言分成了0， 1，2 ， 3四个等级，0 级能力最强，3 级最差。这四个等级之间有着难以逾越的鸿沟。
这里的 3级语言也叫做正规语言，就是有穷自动机能听懂的， 2级语言叫做上下文无关语言，意思是一个词，不用管它的上下文，就可以听懂了。1 级语言就是上下文相关的了，也就是说机器还得揣摩这话前后的意思。零级语言就是图灵机可以接受的语言了。
我们用数数的本事就可以体会1，2，3 型语言的能力差别了。
对于数数，有这么一个笑话：两个贵族比赛，看谁说出的数更大，第一个人绞尽脑汁，冥思苦想十几分钟后说：3， 轮到第二个人，他想了很久很久，最后说：你赢了。
数到 3 的本事哪型语言都会，我这里说的数数本事是从一数起，只要不老死，数多少个都行。3 型语言，也就是正规语言，是不会数数的。 2 型语言（上下文无关语言）会数数，但同时数两个数就不会了。1 型语言就是数多少个数都行的了。而 0型语言的能力又比 1型语言强的多。也就是说，图灵机看上去简单，实际上是还是很牛的。
但是图灵自己就发现了图灵机也有不照的时候了，这就是图灵机的停机问题。我们可以这样说明图灵机的停机问题：假设当图灵机听懂了一句话，它就不再琢磨这句话了，现在我给图灵机一句话，问它“你听的懂吗？”如果它听的懂，它会回答“是”，但如果它听不懂，很可能它永远也不会知道自己听不懂。
作者:
武骧金星 时间: 2007-9-15 11:59
二 有穷与无穷
用天梯登上月球的想法,现代人也许会觉得荒谬,但在古人眼里,未必如此.梯子可以上树,可以上房,可以上城,甚至可以上山,为什么不能上天呢?
因为做梯子的原材料数量不够,强度不够,天梯也没有可搭的地方,等等等等,但古人都不清楚,他们根本不知道地球和月球之间有多远.
国际象棋八八六十四见方的棋盘，围棋纵横361交叉点的棋秤，它们的变化从理论上说是有限的，因此，理论上，这些问题都是图灵机可解决的。但是，就在我们理论上严谨地一步步得出结论时，我们早已不知不觉地越过了在实际计算意义上有穷与无穷的界限。
以围棋为例，围棋有多少种变化？在此，有两种估计方法，一是：假设不会出现大家都被提光再从头再来的情况，那么，第一步有361种选择，第二步有360种选择，以后的情况大致如此，我们就以361为界，那么变化数是361!，约为10的768次方。另一种估计方法大概是宋朝的沈括老先生首先使用的：棋盘上每个点有黑，白，空三种状态，所以围棋变化数是3的361次方，约为10的172次方，用沈老先生的说法，就是“连书‘万’字四十三”。这虽然也很大，但比起前面的估计值来，小的实在是太多了。如果这种估计正确，那电脑下围棋无疑轻松了许多。
不幸的是，沈老先生的估计方法是错误的。他只考虑了这种种状态，却没有考虑这些状态间的相互关系。就比如数学中的图，沈老先生只考虑了顶点的总数，却忘了把连接顶点的边算进去了。
如果我们不考虑边，就考虑这“连书‘万’字四十三”的状态，如果我可以对于每个状态都精确地算出价值的话，那么电脑只需要查价值表就可以确定该怎样下棋了，这样，电脑需要储存的变化数也就是“连书‘万’字四十三”，但问题是，这些价值是怎么算出来的？总不会看到一个状态之后就能猜出它的价值吧。因此，假设有一个电脑围棋机器，虽然在执行的时候他可以只考虑不同状态
的价值，但为了造这台机器，我们还得把所有这些状态的关系都考虑进去。
按照第一种估计方法得到的10的768次方又是个什么概念呢？宇宙中所有基本粒子的总数，据估计，为10的80次方，如果没有一些简化计算的措施，这比宇宙中粒子总数还要大数不清倍的数字对我们来说，又和无穷有什么区别？ （ 这意味着把已知全部宇宙的物质做成内存，每个原子，干脆，每个夸克存储一种状态，都是远远不够的——nn_1997 ）
其实,连第一种估计方法都是错误的.围棋真正的变化数,连10的(3的361次方)次方都挡不住,大学学历的人都清楚,一旦出现指数天梯,那这个数字有多大已经是不可想象的了.
这一点并不能说明围棋不是图灵机实际可解的. 不过 至少告诉我们,遍历的方法是不可行的 .所以,我们暂时把围棋的状态当作无穷来看.
在这里,我们用准无穷来称呼到达实际不可计算程度的状态数.
人们在谈到围棋与国际象棋的比较时，总说围棋的变化远多于国际象棋。但如果把这作为电脑下围棋远难于下国际象棋的原因是不充分的，并不是状态越多的东西越复杂，况且国际象棋的变化同样也是天文数字 。
但是，如果把国际象棋的棋盘放大，棋子增多，使它的变化从绝对数值上来说接近甚至超过围棋，国际象棋还是只能给人以国际象棋的感觉而不是围棋的感觉。因为， 它们的“语法”有着本质的不同 。
现在，我们考虑这样一个问题：国际象棋和围棋走子后棋局状态的变化，分别需要判断几个位置上的状况？
国际象棋当我落下一子时,只要考虑落子点的状态就可以了,如果这里有我自己的子,这步落子无效,如果这里有敌人的子,敌子被我吃掉,如果这里空白,那么仅仅是棋子的移位.象王车易位,吃过路兵等情况,我们可以把它看作可以遍历的特例而暂时不予考虑.
让我们回想一下乔姆斯基四级语言中的2级:上下文无关语言.当排除了特殊情况之后,我们可以认为,既然国际象棋棋局某格的状态变化与周围无关,那么,它应当是可以被能听懂(专业上叫接受)2级语言的机器听懂的.我们可以把国际象棋理解成一个上下文无关语言.
回到围棋,当我们落下一子时,棋盘会变成什么样?如果周围全是敌子,有些敌子没了气,那敌子全部拿走,如果周围有自己的子,敌子没被拿走,自己的子反而没了气,那就是自填死.
听起来好象也很简单,但棋盘的变化是需要看周围的情况而决定的,如果只看落子点的状态,那我们什么结论也得不到.也就是说,围棋不能用上下文无关语言来等价,至少也得用上下文有关语言,就是会数很多数的1级语言.
在考虑围棋变化数的时候,劫可是不能不提.有人说"劫乃围棋精华",可对于1型语言来说,劫实在是要命的东西.1型语言的基本要求是它的语言产生式左边不长于右边,但对于劫来说,并非如此.有了劫,就意味着1型语言也接受不了围棋了.
更要命的还在后面.象三劫循环,四劫循环,长生劫等等,在现在的围棋规则中,都简单地判为"无胜负",其实,如果用"全局同型禁止再现",都可以从理论上解决,并且也不如人们想象中的那么复杂(以后我可能会另写文章介绍多劫循环的规律).全局同型禁止再现也很圆满地解释了劫.但是,全局同型禁止再现对于用图灵机模拟围棋,可以说是致命的一击.因为,这意味着这台图灵机得把以前的所有状态都存储起来,而具有无限种状态数的机器不是图灵机.
国际象棋一盘棋结束,有三种状态,将死对方,被对方将死,和棋,和棋除了双方自愿外,还有逼和,三次同型和,以及六十步子数不变和等等,这意味着国际象棋在这些都是可以直接检验的,其步数不会超过32*60步.可围棋就不一样了,"全局同型禁止再现",这意味着理论上围棋可以下3的361次方数量级这么多手!这是准无穷
了.即使没有这一规则,围棋可走的步数依然是准无穷.
而围棋的胜负又非要看整个棋盘的状态才能决定,也就是说,就算没有"全局同型禁止再现"这一规则,我们可以用图灵机来接受围棋,但判断每一步的好坏必须追溯到这一局棋的终点,这意味着这台图灵机要判断它不同情况下停机时的状态!而这是图灵机所无能为力的.
这里的状态是理论状态,它和我们实际计算时会选择的状态还不一样,围棋实际对局也很少超过361手,但 这已经启示我们,既然国际象棋与围棋在复杂程度上差了3个档次 ,（ 通过乔姆斯基语言理论的论证是否严格？如果真是如此，那无疑是非常精彩的论证——nn_1997 ）我们能够解决国际象棋问题的算法能用来对付围棋吗?
顺便把第三部分也贴出来吧。这部分有点单纯科普的意思，没什么独到见解，所以我不喜欢，打算对这段进行大幅删减，再合并更多关于优化和寻路的内容作为第三部分，着重推出第四部分《混沌边缘》和第五部分《感觉与计算之间》
作者:
武骧金星 时间: 2007-9-15 12:00
三 迷宫之路
从理论上来说,围棋的每一步都会有一个或几个最佳选择,如果我们真的可以遍历围棋的所有变化并加以比较的话,我们是可以找到这些最佳下法,只是这种遍历是实际上不可实现的.
寻找围棋最佳下法的过程就象是在走一个庞大的迷宫,迷宫中有无数的分支岔路,有些通向死路,有些通向幻象,还有一些路则仅仅是自己转圈.置身于这个庞大的迷宫中,当我们知道凭一生的时间也只能走过这一迷宫的微不足道的一小部分时,我们自然会停下来,看看这迷宫之路中有没有什么规律.
我们先对问题进行简化,抛开全局同型禁止再现,也不考虑把三劫,四劫,长生劫等等情况.这样在走迷宫时不必判断是否会出现回路(就是绕了一圈又回来了),对于这种无回路的迷宫,最简单的走法是死贴一边走(比如,一直贴左边或者一直贴右边),这就是一种遍历搜索,术语叫深度优先遍历搜索(因为它每次都要走到头再转回来走下一条).
按上章的计算,深度优先遍历搜索走完这个迷宫大概需要10^(3^361)步.
所以,我们别无选择,只有换种办法来走迷宫,我们所选的办法又怎样才能达到我们的要求呢?
我们这里所谈论的迷宫的走法,也就是解决一个问题的算法,一般用是用复杂度的阶数来衡量算法复杂度好坏的.首先,一个问题有它自己的尺度,比如国际象棋是64格棋盘,我们可以把国际象棋问题的尺度定为64,围棋361个交叉点,我们可以把围棋问题的尺度定为361.如果你愿意把它们的尺度分别定为8,19也可以,但考虑问题时显然不如64和361来的自然.
解决一个问题的算法的复杂度是根据问题的尺度与计算步数的函数来定义的,设n为问题的尺度,如果一个算法需要n步.我们就说它的复杂度是n,如果一个算法需要2^n步(n个2连乘),我们说它的复杂度是2^n. 对于两种算法来说,只要他们的复杂度函数的比值不大于一个常数,我们就称它们为同阶的.也就是说,一个需要步数为1000n的算法与一个需要步数为n的算法是同阶的.因为我的机器只要能把速度提高一千倍,第一个算法就能达到第二个算法原先的速度.但一个步数为n^2的算法就比一个步数为1000n的算法复杂度高,因为不论你的机器有多快,对于尺度很大的问题,总还是第一个算法复杂.
因此,我们就用O(n),o(n^2),...,o(2^n),... 来表示与步数为n,n^2,...,2^n,...的算法同阶的算法的复杂程度.请注意这里的2^n,一个2^n步数的算法(其实是任何x^n(x>1)步数的算法)比任何一个多项式步数的算法(就是O(n), O(n^2)...这类算法)都来的复杂. 比如说,一个算法的步数约为2^n,第二个为n^10,当n取64的时候(国际象棋尺度),前者需要1.84*10^19步,而后者需要1.15*10^18步,第一个比第二个要多花十多倍步数,如果问题尺度是361(围棋尺度),后者需要3.76*10^25步,而则前者需要4.69*10^108步,这次前者比后者复杂了一千亿亿亿亿亿亿亿亿亿亿倍.
如果说一个问题可以找到复杂度为多项式的算法,我们称它属于P类问题,我们需要的就是复杂度为多项式的算法,也就是说,如果围棋是P类问题,我们就认为它可解.而如果我们只能找到指数等级的算法(O(2^n)..等等),我们就认为它不可解.
而 围棋的遍历需要的步数,是指数复杂度问题的排序问题,它比指数复杂度的问题还要复杂的多 .
在人们试图用计算机解决的各种问题中,有一大类问题,包括货郎问题,背包问题等等,总计数百个之多,被人们称为NP问题.之所以说它们是一类是因为人们已经证明了只要其中一个问题可计算(就是有多项式算法),其他的问题就都可以计算,
但现在, 比起找这些问题的多项式算法,人们倒宁愿去证明它们不存在多项式算法.
围棋是NP问题吗?不知道,好象不是,但既然NP问题都有指数复杂度的解法,而围棋连指数复杂度的解法都找不到,看起来,围棋似乎比NP问题还要复杂的多 .
不过,解决一个问题,找不到最好的方法,退而求其次也不失为一种明智的选择.人们对很多NP问题的态度就是:找不到最好的答案,比较好的答案也不错."深蓝"会输给卡斯帕罗夫一局,也说明"深蓝"找到的并非最佳下法,但它已经可以在总成绩上战胜卡斯帕罗夫了.
在各种搜索算法中,有一个A*搜索算法,也叫做最佳搜索算法,它是对于问题的各种情况设定一个估值函数,假设我们选择的是值最小的道路,在搜索迷宫的时候,A*算法根据估值函数判断下一步应选择的道路,并不停地用走过的实际路线的价
值加上下一点的估值函数作为新的估值.当新的估值小于以前所做的另一条路线的估值的时候,改换到另一路线中重新进行估值和搜索,这倒有点象人下棋时的判断:看看这样走行不行,看到大概不行时,就换个办法再看看.
理论上,如果估值函数永远小于实际路线的价值,那么,A*算法总可以找到最优解.但这样太困难.我们还可以有这样的想法:如果A*算法的估值函数可以做到差不离的话,也许我们就可以找到一个比较好的走法.比如,如果A*算法能够把下一手的选择点降到平均6步,计算一路变化所需的步数降到平均20步,那么总的计算量就变成了6^20=3.66*10^15,这就已经接近于计算机可接受的计算量了.
作者曾经设想过一个围棋AI模型:把所有的棋子以连在一起的一块为基本单位,而后再根据棋子的形状,眼位情况,赋与它强度,影响力等属性,用力学模型来分析全局势力范围,并据此选择下一手的大致位置.实际上这就是对A*算法估值函数的一种设想.
看起来,我们只要找到一个好的方法,把一个个围棋局面量化成适当的值,再根据这些值进行A*搜索,就可以找到相当不错的走法.
唯一的问题是: 存在可行的量化方法吗?
作者:
武骧金星 时间: 2007-9-15 12:13
……总算贴完了……
我以前看过一份讲人工智能的文章……其中心思想有以下一些：
1，电脑之所以不如人脑，原因不在于什么思考方式啊，学习能力啊，而是在于复杂性——最精密的集成电路也远不及神经元网络。
2，我们很难做出与人脑同样复杂的电脑，但我们可以做出一种电脑——这种电脑有能力制造比自己更“复杂”一点点的电脑。（但是问题在于，我们自己好像没有办法做出比我们自己更复杂一点的东西耶~）
作者:
fantasydog 时间: 2007-9-15 12:48
真正意义上的人工智能是Socrates, Plato, Aristotle师徒三人所提出的，基于哲学，心理学等。AI的目标是使得人工智能模拟人类思维。
现在的电子计算机仅仅是实现的工具，但是并不理想。图灵机的计算模式是针对1+1=2这类问题，这只不过是人类思维方式的一种。对其他问题的思维，图灵机就很无能为力了，比如图形的识别。
基于当前电子计算机去研发人工智能，大体上类似于用马车跑到月球上去，累到死也成功不了。
作者:
baby5213344 时间: 2007-9-20 22:05
原帖由 武?鹦荹/i] 于 2007-9-15 12:13 发表
1，电脑之所以不如人脑，原因不在于什么思考方式啊，学习能力啊，而是在于复杂性——最精密的集成电路也远不及神经元网络 ...
这个有办法，我说说别笑啊。
人脑是造不出和自己一样的电脑，但是却造出了不怕累的电脑。
人脑是最精密的仪器，那为什么算不过电脑？是因为生理问题限制了人脑的运作要休息，还有惰性和不必要的情感。如果驱除这些“杂质”那人脑绝对能造出智能电脑，或者自身已经进化成了只能电脑
作者:
黑传说 时间: 2010-6-2 12:27
应该还是有可能搞定的，这要从围棋本身规则入手：抢地，这非常像文明等游戏里面的开荒。
一开始棋盘是空荡荡的，当第一子下去的时候，此时整个棋盘的主人是该子，下一个子就会把这个子的地盘分区1/2,接下来以此类推，假设每一步都不是相互争斗的话，那么就是无限的1/2分下去，这样围棋的基本套路就可以表现出来了。
接下来就要处理争斗问题了：子的生存需要有“气”，那么可以从其四周判断，如果四周都是同类，那么需要再把同类的四周进行穷举，看看同类四周是不是也有气或者同类，以此类推，如果最终找不到足够的两气，那么判定这片子处于死亡边缘。
既然能够判定何为不利状态了，那么就可以根据这个来设定规则了：凡是有可能让该子陷入孤立无援状态的下法，都会被判定为较差下法，反之，则为较好下法，在穷举了众多较好下法然后排除掉众多较差下法之后，基本就可以让电脑自动计算出怎么去下子了。
作者:
dimeterio 时间: 2010-6-2 13:02
研究計算機圍棋的人，都應該去拜讀一下已故圍棋名家章照原先生的一篇著作，講的是他對千古無同局的看法。
章先生認為，隨著圍棋本身的不斷發展，出現同局的日子越來越臨近。章先生的主要看法是，雖然理論上圍棋的變化可能性有361*360*359……那麼多，但是從圍棋本身的技術而言，合理的著手並不多，佈局階段合理的選點最多就10來個，中盤戰鬥選點就更少，如果是對殺等局部戰鬥，很可能2、30手棋一本道，完全沒有變化。所以圍棋的變化雖然多，但是在職業棋手的比賽中出現的“合理變化”應該是有窮的，而且這個數字並不會很大。
所以把圍棋變化無窮作為設計電腦對弈程序的先決條件，本身就是錯誤的。
作者:
KYOKO 时间: 2010-6-2 13:22
最高级的计算机下国际象棋确实能和最高级的人抗衡了，围棋行吗？
作者:
黑传说 时间: 2010-6-2 13:41 标题: 回复 #8 dimeterio 的帖子
没错，以穷举的方式来对应变化，会和现在的杀软一样，需要不断更新，但如果以特定简化通用规则呢？如我楼上所说的“找气”，或许会是个好的解决方法。
我有空的时候会再研究一下的。
作者:
颖颖 时间: 2010-6-2 13:57 标题: 回复 #8 dimeterio 的帖子
我认为电脑围棋下不过人的最关键原因，是在 AI 围棋上的投资，远远小于在 AI 西洋棋上的投资。换句话说，没有足够的人拿钱砸，肯定是搞不出来能战胜李世石的围棋软件的。
作者:
黑传说 时间: 2010-6-2 14:10 标题: 回复 #11 颖颖 的帖子
哈哈，开句玩笑，你砸钱我来搞如何？不用多，几千万应该就能砸了李世石——硬件方面的要求应该没必要像深蓝那么大的投资，主要是智力方面的。即使是设计得再烂的围棋ia，用全球所有计算机的计算能力来和李pk，赢面还是比较大的。
靠钱就能搞定的问题，就不是什么难题了。
现在是连最起码的模拟围棋都没找到好方法呢。
[ 本帖最后由 黑传说 于 2010-6-2 14:16 编辑 ]
作者:
dimeterio 时间: 2010-6-2 14:39 标题: 回复 #12 黑传说 的帖子
按照章先生的觀點，電腦擊敗李世石比較容易，擊敗我比較難，因為我到處亂下，哈哈哈哈……
作者:
颖颖 时间: 2010-6-2 14:53 标题: 回复 #12 黑传说 的帖子
我什么时候说过靠钱就能搞定？
作者:
黑传说 时间: 2010-6-2 15:09 标题: 回复 #13 dimeterio 的帖子
围棋ai不是根据对方的走法来下的，而是根据自己的设定来下，也就是；你下你的，我下我的，除非碰撞到了，否则不会对你的乱下有任何反应。
to 颖颖：
对不起，我极端化了你的观点。
作者:
muzhi 时间: 2010-6-2 17:11
现在最好的围棋AI是在依据概率模型的搜索中加入大量启发式信息（比如局部模式的匹配等）做的
已经有和低段位职业棋手过招的水平，击败一般人没有问题
进一步上升的困难主要在于搜索复杂度
即使全世界的计算机都跑起来，计算资源也只是线性的，追不上指数增长的复杂度
围棋和国际象棋的最大区别是复杂度
这两块的研究是同一个领域，有些研究者就是两头都做
至于乱下，早就没有围棋AI离了棋谱变白痴了...
我们实验室有个小伙来我们实验室之前就是做围棋AI研究的...
有兴趣的人可以去IEEE Xplore之类的地方搜些论文看...
--------------------------------------------------------------
纠正：不是低段位职业棋手，是低段位业余棋手
[ 本帖最后由 muzhi 于 2010-6-2 23:01 编辑 ]
作者:
黑传说 时间: 2010-6-2 17:47 标题: 回复 #16 muzhi 的帖子
所以说不能沿用现在的思路继续搞下去啊。
也是我上面说可以根据围棋特定特点来搞这个的原因，有需要重新根据其特点来破解原来非常容易出现的指数级增长复杂度问题。
作者:
南帝孟获 时间: 2010-6-2 17:51
想下好围棋得锻炼两点：1.计算力；2.判断力
即使可以精确地计算，但是无法判断形成这个局面的优劣，同样是不行的。
人脑在围棋方面的强大在于其归纳力和判断力的强大，从而弥补了人脑在计算力上的不足，同时提高了人脑计算的效率。
作者:
muzhi 时间: 2010-6-2 20:30 标题: 回复 #17 黑传说 的帖子
欢迎加入人工智能研究者的行列
你提的这个事情，有多少人想做在做却做不出来
你要是解决了这个问题，自然是在学术界为中国扬名的一件大事
作者:
颖颖 时间: 2010-6-2 21:06
原帖由 muzhi 于 2010-6-2 17:11 发表
现在最好的围棋AI是在依据概率模型的搜索中加入大量启发式信息（比如局部模式的匹配等）做的
已经有和低段位职业棋手过招的水平，击败一般人没有问题
进一步上升的困难主要在于搜索复杂度
即使全世界的计算机 ...
哪里有这样的 AI ？给我 send 一份好咩？
作者:
dimeterio 时间: 2010-6-2 22:07
同求
作者:
黑传说 时间: 2010-6-2 22:23 标题: 回复 #20 颖颖 的帖子
gnu go，但棋力实在太臭，呵呵。
围棋和象棋AI方式应该不是一种类型的，当然，也可以是同样一种，但这样可能吃力不讨好而已，类似fantasydog所说的骑马车跑去月球一样。
围棋可能可以更低层实现（当然，需要硬件的配合），比如黑白空分别用1 -1 0来替代，棋盘就是19个19位数（把零的进阶算上，应该是18进制，恰好可以兼容2进制），那么只要知道最终的绝对值最大，该方就是取胜的一方。同时，可以利用目前比较成熟的CPU分布式计算底层控制模式来近乎模拟其所谓的AI。
[ 本帖最后由 黑传说 于 2010-6-2 23:11 编辑 ]
作者:
muzhi 时间: 2010-6-2 22:38
产品我不知道...我说的只是领域内研究现状...
哪天去问问实验室那小伙去...
另外发现我之前一个理解错误，是业余段不是职业段
根据wiki，“現在は日本棋院からアマ初段を認定されているプログラムが4つある（手談対局4、最高峰3、最強の囲碁2003、銀星囲碁3）。”
就是说这四个被日本棋院认定有业余初段棋力，不过也说跟现在初段的人下还是很难赢。
至于研究上，近年的优秀AI有和王铭琬对局并被评价为有业余三四段棋力的。
参见 http://ja.wikipedia.org/wiki/%E3 ... F%E5%9B%B2%E7%A2%81
[ 本帖最后由 muzhi 于 2010-6-2 22:59 编辑 ]
作者:
muzhi 时间: 2010-6-2 22:55
原帖由 黑传说 于 2010-6-2 22:23 发表
gnu go，但棋力实在太臭，呵呵。
围棋和象棋AI方式应该不是一种类型的，当然，也可以是同样一种，但这样可能吃力不讨好而已。
围棋可能可以更低层实现（当然，需要硬件的配合），比如黑白空分别用1 -1 0来替代，棋盘就是19个19位数（把零的进阶算上，应该是18进制，恰好可以兼容2进制），那么只要知道最终的绝对值最大，该方就是取胜的一方。同时，可以利用目前比较成熟的CPU分布式计算底层控制模式来近乎模拟其所谓的AI。
没法说你这个设想管不管用
因为你的说明和当前科技界通用的语言不兼容，我理解不了...
18进制是哪儿来的？0的进阶是什么？跟2进制怎么兼容的？1，-1，0不是三进制么？什么是最终的绝对值？
你说的“CPU分布式计算”指的什么？“底层控制模式”又指的什么？
现在对弈AI研究中的基本思想还是game tree
作者:
黑传说 时间: 2010-6-2 23:04 标题: 回复 #24 muzhi 的帖子
9个二进制可以转化为18进制啊，不是兼容了么？这样可以利用三进制的优势，同时也可以不用担心和现在计算机的兼容问题。
以我楼上所说的占地，围棋最终结果是计算双方所占点的多少，而如果表现在我所说的这里，就是1和-1数量对比，而我这里恰好把其转为为18进制，那么就类似于对比两个数的绝对值大小了，而且这样每个数都还可以直接还原为棋盘上的棋局。
分布式计算/底层控制模式没接触过么？主要表现为对多核cpu的管理模式，原来只用于服务器的，现在普通pc也开始使用了啊。
你说的gametree效果楼上已经有些简单分析了。
[ 本帖最后由 黑传说 于 2010-6-2 23:13 编辑 ]
作者:
dimeterio 时间: 2010-6-2 23:06 标题: 回复 #23 muzhi 的帖子
王銘琬から9路盤黒番コミ2目半で勝利した——九路盘太简单了，穷举法肯定搞定。和19路盘差太多。
アマ初段——业余初段，鄙人让三子的水平
同年8月には情報処理学会のイベント「第7回情報科学技術フォーラム」でトッププロの王銘琬九段と対局し、19路盤の8子局で中押し勝ち——19路盘要王銘琬让8子……
作者:
muzhi 时间: 2010-6-2 23:12 标题: 回复 #26 dimeterio 的帖子
你的围棋水平佩服，你也超出普通人了...
"九路盘穷举搞定"？照样需要足够的剪枝，你可以写一下试试看...
不整天做高计算复杂度的算法大概不会对组合爆炸有直接的体会
19路盘被九段让8子不错了吧...
作者:
muzhi 时间: 2010-6-2 23:23
原帖由 黑传说 于 2010-6-2 23:04 发表
9个二进制可以转化为18进制啊，不是兼容了么？这样可以利用三进制的优势，同时也可以不用担心和现在计算机的兼容问题。
以我楼上所说的占地，围棋最终结果是计算双方所占点的多少，而如果表现在我所说的这里，就是1和-1数量对比，而我这里恰好把其转为为18进制，那么就类似于对比两个数的绝对值大小了。
分布式计算/底层控制模式没接触过么？主要表现为对多核cpu的管理模式，原来只用于服务器的，现在普通pc也开始使用了啊。
看不懂9个2进制怎么转了18进制，只见过4位二进制转16进制的，又怎么扯上了三进制，或许你说的“进制”跟一般数论里说的不是一件事...
2x9=18，看了半天猜测你是在做数目/数子，这个可以作为game tree的叶，但是跟降低复杂度和下一步走哪儿什么关系？
不从算法上降低复杂度，即使你把宇宙中全部原子变成量子计算机一起算，也不够啊...
几十年前单纯的game tree不够用就是定论了，虽然没出现更有效的模型，却有了很多有效的剪枝方法
无论分布还是并行，都是线性地增加计算资源
[ 本帖最后由 muzhi 于 2010-6-2 23:29 编辑 ]
作者:
黑传说 时间: 2010-6-3 08:45 标题: 回复 #28 muzhi 的帖子
在我所说的分布/并行，目的并非是为了增加计算资源，而是模拟围棋下子。
至于降低复杂度和下一步怎么走，你再看看7楼的描述，是不是还是和gametree一样？
作者:
muzhi 时间: 2010-6-3 10:42 标题: 回复 #29 黑传说 的帖子
好吧...我理解不了你这么高深的内容...
祝你成功吧...
作者:
黑传说 时间: 2010-6-3 13:45 标题: 回复 #30 muzhi 的帖子
呵呵，我也仅仅是根据我在其他领域的经验提的思路设想，并没有开始进入研究，现在仅仅是猜测。
还要再过一阵子吧，或许我能腾出大片空闲时间来的时候，会根据这个思路去折腾折腾看的。
| 欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |