来自 科技中心 2019-05-02 23:51 的文章
当前位置: 美洲杯冠军竞猜 > 科技中心 > 正文

React的井字过三关(3)

几年前,果壳网小编曾经自己动手写过一个和人下井字棋的电脑程序,运行之后却发现电脑先走时总爱把第一步棋下在角上;检查程序代码许久后才意识到,电脑程序可能并没有问题。人们往往有一个定势思维,认为由于从正中央出发能够得到的连线最多,因此最优策略必然是先占住正中央这块宝地。然而,经验是一回事,实际上就是另一回事了——这个电脑程序看似很没头脑地往角里下棋,但几乎总是在赢。

一. 是开头都会说的原理

但凡懂一点围棋的人都知道“大场”这个概念,可以浅显地把它理解为布局时棋盘上各处的要点。棋谚“金角银边草肚皮”,就很好地说明了大场具有的特征:价值高。

比如没其他子的情况下,先手占星角位,这手棋价值大约是20目。第一手下在顶角,价值可能就1-2目。那就如果第一手占天元,价值...就不好说了。

一个棋类游戏AI实现的难度在于,每手棋的价值其实都是人类经验性的总结。算法无论是穷举或进化,都是人在教机器下棋。人的水平高,机器就学得快。反之亦然。

回到九宫格的井字棋,由于场地条件限制,极大地简化了ai的实现过程。穷举就可是最现实的办法。人只需要根据经验定义每种情况下点位的价值。教会它计算每手棋的价值,再根据价值排序,找出价值最高的一个就可以了。

只考虑一条线路上的情况,当场面出现己方的二子连线时,无疑最佳落子点是这条线的第三点(一着取胜),这手棋对于取胜来说,必然是无价的。但机器不懂人类的价值观,我们就假定这手棋的价值是10000吧。如果这条线路上对方出现二子连线,此时场面最有价值的点位就是封堵对方二子连线的位置,这手棋价值也很重要,但不能超过己方二子连线的价值,可算作1000。同理,当这条线路上,只有你的一个子,你下这手棋可以获得在这条线上的先手优势,有价值,但是比前两种情况都低,算作100。如果你下一手棋,线路上只有对方的一个子。你落子于此,既不能一步取胜,也不能封堵对方的二子连线,且不能在这条线上获得先手优势,那就是废着,昏着(如同围棋中在自己的地盘里填子一样)——尽管我们那么评价它,但这在实战中还是可能出现的,所以它的权重就是-10。

其它情况有没有考虑到呢?有比如线路一个子都没有的情况,先手肯定有一点点优势。但是在井字棋的布局里还不够不典型。就定义为0吧——这里又有坑了。

实际上的情况是,一手棋包含了2-4条线路。综合各条线路的判断下来。累加的权重就是这手棋的价值。


后手还是先占角!

美洲杯冠军竞猜 1

作为后行者,你遇到的往往是“先走中间”的经典开局。此时,千万别忘了,先占角仍然是一条金科玉律。如果你不慎走了某条边的位置,对方可就赢定了!对方可以向上面的第一幅图那样,在正右方下子应对,逼迫你把下一步棋落在正左方。此时,对方便可占据右上方的位置,同时产生出两条仅差一子的连线。右边三幅图则显示,如果你在角上应对,最终总会是一盘和棋。

反过来,先手第一步走中间,棋盘上剩下的八个位置中有四个位置都是会导致对方必败的陷阱,因此先手第一步走中间后,获胜的机会也并不小。井字棋可以算是决策树最简单的游戏之一了。在历史上,对井字棋的类似分析很大程度上启发了人们对组合游戏的认识,在博弈论中起着举足轻重的作用。

二. AI结构

先在外部js上定义一个ai函数;再把这个ai.js引入到header中。回到组件的页面。在Game组件的渲染方法return前写console.log(ai(lastHistory.squares))

好了,可以想象一下,的井字棋应用之前有了一个history状态。只要在电脑走棋的时候,把这个history状态发送给AI,AI遍历状态,自动找出最佳的落子点,并返回给状态。

  • 判断哪些位置能走

    function ai(arr,turnToX){

    var loacation=arr.map(function(item,index){
        if(item===null){
            return index;
        }
    }).filter(function(item){
        return item!==undefined;
    });
    ...  
    

    }

通过这一步,得到一个数组。这个数组代表哪些地方(一维坐标)是可以走的。

  • 确定电脑应该扮演的角色,这样才能分析——把turnToX状态传进来

    var player=turnToX?'X':'O';

  • 计算能走的点位价值,sort排序返回点位。

之前所谓的ai算法实现的大坑,其实也就是这么回事。


井字棋可能是最简单的棋类游戏了,它简单到了成年人之间玩几乎总是平局的地步。因此,这个游戏貌似最多只能哄哄小孩子。不过,对井字棋游戏中所有可能的情况进行一番细致的分析,你会发现一个你或许不会料到的惊人结论——先手的最优策略不是稳坐正中央,而是先占一个角!

美洲杯冠军竞猜,AI结构后续

    // ai函数
    var oCalc={};
    for(var i=0;i<arr.length;i  ){
        for(j=0;j<loacation.length;j  ){
            var index=loacation[j];
            switch(index){
                case 0:
                case 2:
                case 6:
                case 8:
                  oCalc['loacation' index]=judgeConner(index);
                  break;
                case 1:
                case 3:
                case 5:
                case 7:
                  oCalc['loacation' index.toString()]=judgeSide(index);
                  break;
                case 4:
                  oCalc['loacation' index.toString()]=judgeCenter(index);
                  break;
            }
        }
    }

角位是2,4,6,8。边位是1,3,5,7。中心位置为4。根据不同的情况返回不同的位置到对象oCalc中。(作为测试,可以把oCalc作为ai函数的return值)。

  • 角位,需要判定的有3条线路(横竖斜)
  • 边位,需要判断2条线路(横竖)
  • 中心位置需要判断4条线路:(横竖撇捺)

接下来就是在各个函数里var一个value,一个个对arr进行判定。

当然,有稍微简化一点的办法:意识到很多判断是重复的,比如说边角判断,线路判断2,5,8其实就是棋盘被“推倒之后的”0,1,2。根据这个思想可以定义a,b两个值,当判断的边角是0时,a=1,b=2。当判断的边角是2时,a=5,b=8。同理,当判断的边角是8时,a=7,b=6...如此往复。

美洲杯冠军竞猜 2


无独有偶,国外著名的 Geek 漫画 xkcd 最近画了一幅井字棋最优策略完全图,同样给出了这个违反直觉的结论:第一步走在角上才是最佳的策略。

这是React井字棋项目的最后一篇笔记,记述AI实现。

本文由美洲杯冠军竞猜发布于科技中心,转载请注明出处:React的井字过三关(3)

关键词: