0x00 前言

很早之前學(xué)習(xí)flutter時(shí)曾寫過(guò)一個(gè)五子棋游戲，但是當(dāng)時(shí)只是基于棋子估值算法實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的AI，總感覺(jué)不夠智能，由于算法一直是我的劣勢(shì)，且還一直固執(zhí)的認(rèn)為一切脫離業(yè)務(wù)談算法皆為虛妄，所以就萌生了使用一種人工智能算法去重寫五子棋AI機(jī)器，也算是將其應(yīng)用到了實(shí)際業(yè)務(wù)中，畢竟能解決實(shí)際問(wèn)題的算法才是好算法。

0x01 已有的AI實(shí)現(xiàn)原理

雖然本文說(shuō)的是基于alpha-beta剪枝算法AI，但是在此之前還需要先補(bǔ)一些五子棋AI的基礎(chǔ)知識(shí)，才好繼續(xù)探討下去。
那么，試想這么一個(gè)場(chǎng)景，當(dāng)你落完一子之后，此時(shí)輪到AI落子，但是棋盤上有那么多空位，究竟應(yīng)該落子到哪里？這就引出了第一個(gè)問(wèn)題：
如何評(píng)估一個(gè)位置的好壞？
這句話雖然看起來(lái)像是個(gè)判斷句（一個(gè)位置不是好就是壞？）但它絕不是判斷句，棋盤上的空位置很多，如果我們能對(duì)棋盤上每一個(gè)空位置都進(jìn)行打分，然后以分?jǐn)?shù)高低排序，即每個(gè)位置都對(duì)應(yīng)一個(gè)分值，其中分值最大的就是當(dāng)前可落子的最好位置了。
那么接下來(lái)的問(wèn)題就很具體了
設(shè)計(jì)一個(gè)可以給每個(gè)空位置打分的方法
首先，如果棋盤是空的，那么你落子在棋盤的邊上和落子在棋盤的中間顯然效果是不同的，這說(shuō)明棋子有一個(gè)位置得分，且越靠近中心位置越高，就像是一個(gè)圓錐，中心區(qū)域是最高的，那么就很容易可以想到計(jì)算這個(gè)位置得分的函數(shù)其實(shí)就是圓錐方程的變種
棋子位置評(píng)分表達(dá)式：(x-7.5)^2+ (y-7.5)^2 - z = 0

棋子位置評(píng)分函數(shù)

(注：這個(gè)圖可以在 https://www.geogebra.org/calculator 生成)
其次，當(dāng)一個(gè)位置相鄰的位置也存在自己的棋子時(shí)候，可以組成不同的形式，比如：當(dāng)有兩個(gè)棋子時(shí)，可以構(gòu)成以下幾種形式，具體有如下：

活二

跳活二

死二

低級(jí)死二

當(dāng)有三子時(shí)，可以構(gòu)成如下形式：

活三

跳活三

死三

低級(jí)死三

當(dāng)有四子時(shí)，可以構(gòu)成如下形式：

活四

跳活四(一跳三或三跳一)

跳活四(二跳二)

死四

低級(jí)死四

當(dāng)有五子連珠時(shí)，已經(jīng)不需要考慮其他，因?yàn)橐呀?jīng)獲勝，游戲結(jié)束了，所以，所有的中間態(tài)棋型也就上述幾種了，哦，對(duì)了，上面只是拿豎直方向舉例，實(shí)際情況還需要加上水平、左斜、右斜三個(gè)方向，但是形勢(shì)是一樣的。
有了上述的幾種基本組合形態(tài)，我們就可以給一個(gè)棋子的組合打分了，只需要檢測(cè)其周圍，看它能構(gòu)成那種形勢(shì)，然后加上這個(gè)形勢(shì)的分值既可。經(jīng)過(guò)多次的實(shí)驗(yàn)與調(diào)整，我得出一套打分標(biāo)注，基于這個(gè)打分標(biāo)準(zhǔn)做出的AI智能程度還不錯(cuò)，可以參考一下：

  static const int WIN = 10000;

  static const int DEEP_DEATH2  = 2;
  static const int LOWER_DEATH2 = 4;

  static const int DEEP_DEATH3  = 3;
  static const int LOWER_DEATH3 = 6;

  static const int DEEP_DEATH4  = 4;
  static const int LOWER_DEATH4 = 32;

  static const int ALIVE2       = 10;
  static const int JUMP_ALIVE2  = 2;
  static const int ALIVE3       = 100;
  static const int JUMP_ALIVE3  = 10;
  static const int ALIVE4       = 5000;
  static const int JUMP_ALIVE4  = 90;

寫到這兒，我們第一版的AI就已經(jīng)呼之欲出了，只需要遍歷當(dāng)前棋盤上的空位置，然后逐個(gè)計(jì)算該空位的得分(位置分+組合分)，然后取分?jǐn)?shù)最高的點(diǎn)落子。
嗯，如果你按照這個(gè)思路去寫一個(gè)AI的話，那么你就可以得到一個(gè)人工智障AI，它只會(huì)自顧自的落子，壓根就不會(huì)管對(duì)手的落子，為啥呢，因?yàn)槲覀冎挥?jì)算了自己的最優(yōu)位置，沒(méi)有考慮對(duì)手的位置，所以它只會(huì)進(jìn)攻，不會(huì)防守。
為了能讓它提升點(diǎn)智商，我們還需要計(jì)算對(duì)手的最優(yōu)位置，原理同上，然后再?zèng)Q定是防守還是進(jìn)攻，這樣就不會(huì)出現(xiàn)自顧自的落子的問(wèn)題了，經(jīng)過(guò)我的多次測(cè)試經(jīng)驗(yàn)，發(fā)現(xiàn)當(dāng) 對(duì)手的最優(yōu)位置得分 / 我方最優(yōu)位置得分 > 1.2 時(shí)適合防守，反之適合進(jìn)攻，代碼如下：

  Offset bestPosition(BufferMap<Offset> ourPositions , BufferMap<Offset> enemyPositions){
    Offset position;
    double maxScore = 0 ;
    ///魔法值 1.2 , 0.7 
    if(enemyPositions.maxKey() / ourPositions.maxKey() > 1.2){
      for (int key in enemyPositions.keySet){
        int attackScore = chessmanGrade(enemyPositions[key]);
        double score = key * 1.0 + attackScore * 0.7;
        if(score >= maxScore){
          maxScore = score ;
          position = enemyPositions[key];
        }
      }
    }else{
      for (int key in ourPositions.keySet){
        int defenseScore = chessmanGrade(ourPositions[key]);
        double score = key * 1.0 + defenseScore * 0.7;
        if(score >= maxScore){
          maxScore = score ;
          position = ourPositions[key];
        }
      }
    }
    return position;
  }

到這兒，一個(gè)簡(jiǎn)單的AI就已經(jīng)完成了，它可以在你無(wú)聊的時(shí)候陪你玩幾局了。不過(guò)要是你棋藝高超，它可能就很難贏你了，畢竟它只會(huì)看一步棋，也就是永遠(yuǎn)只會(huì)選擇下一步最優(yōu)的位置，對(duì)于能一次預(yù)測(cè)后面幾步的你，它就顯得很稚嫩了。那么如何能讓它也能夠一次看多步棋呢，這就終于說(shuō)到正題了，使用alpha-beta剪枝算法可以讓它快速搜索以預(yù)測(cè)到后幾步，從而在當(dāng)前選擇最優(yōu)的落子位置。

0x02 Max-Min算法搜索博弈樹(shù)

我們?cè)谇懊娴臅r(shí)候已經(jīng)得到一個(gè)可以按照分值排序的可落子位置列表，那么我們可以嘗試把這個(gè)列表的每一個(gè)位置都落子一次試試，然后我們假設(shè)對(duì)手的落子總是會(huì)取我們得分中最低的一種情況，然后又是我們落子，我們落子的時(shí)候肯定會(huì)選擇使我們得分最大的一種情況，以此往復(fù)，就可以得到一顆博弈樹(shù)了，最終我們選擇那個(gè)使我們得分最大的情況去落子就可以實(shí)現(xiàn)我們?cè)趲撞街蟮梅肿畲蟮哪繕?biāo)，有點(diǎn)難以理解，畫個(gè)圖說(shuō)吧。

博弈樹(shù)

在這顆博弈樹(shù)中，假設(shè)我們當(dāng)前有兩種走法，分別是：B、C；
而如果我們走了B走法，則對(duì)方會(huì)有E、D兩種走法；
當(dāng)對(duì)方走法為E時(shí)，我們又有J、K兩種走法；
而J走法對(duì)應(yīng)的對(duì)方又有U、V、W、X、Y 等5種走法；
假設(shè)此時(shí)游戲已經(jīng)分出了勝負(fù)或者我們就此打住，不再繼續(xù)往下推演，我們就到達(dá)了這顆博弈樹(shù)的葉子節(jié)點(diǎn)，此時(shí)我們可以就當(dāng)前棋局形式進(jìn)行打分，如圖所示，假設(shè)我們最后打分為：
U：24分、V：2分、W：10分、X：10分、Y：7分
由于它的父節(jié)點(diǎn)是對(duì)手的回合，因此對(duì)手肯定會(huì)選擇我們這些得分中最小的那個(gè)，即V節(jié)點(diǎn)2分，同理可得K節(jié)點(diǎn)為6分；
繼續(xù)往回推演：由于J、K節(jié)點(diǎn)的父節(jié)點(diǎn)E為我方回合，因此我們選擇這兩個(gè)中最大的值，即E節(jié)點(diǎn)值為6；
以此類推，則可以得出最終得分為2，最優(yōu)路徑為圖中紅線路徑。
理論梳理完畢，轉(zhuǎn)化為算法則是：

1、節(jié)點(diǎn)遍歷的順序是從下往上、從左往右
2、如果當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則評(píng)估棋局形勢(shì)
3、若當(dāng)前節(jié)點(diǎn)為對(duì)手回合（MIN節(jié)點(diǎn)），則其值取子節(jié)點(diǎn)中值最小的
4、若當(dāng)前節(jié)點(diǎn)為我方回合（MAX節(jié)點(diǎn)），則其值取子節(jié)點(diǎn)中值最大的

 /// 極大值極小值算法
  num maxMinSearch(ChessNode root){
    if(root.childrenNode.isEmpty){
      return root.value;
    }
    List<ChessNode> children = root.childrenNode;
    if(root.type == ChildType.MIN){
      for(ChessNode node in children){
        if(maxMinSearch(node) < root.maxValue){
          //當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)為MIN節(jié)點(diǎn)，也就是取所有子節(jié)點(diǎn)值中最小的值，
          //換句話說(shuō)：這個(gè)父節(jié)點(diǎn)產(chǎn)生的最大值不會(huì)高于所有子節(jié)點(diǎn)中的最小值，因此更新父節(jié)點(diǎn)的maxValue
          root.maxValue = node.value;
          root.value = node.value;
          root.checked = node.current;
        }else{
          // 當(dāng)前節(jié)點(diǎn)的值大于了父節(jié)點(diǎn)的最大值，由于父節(jié)點(diǎn)是MIN節(jié)點(diǎn)，因此不會(huì)取該值
          // 換句話說(shuō)：當(dāng)前為對(duì)手回合，對(duì)手已經(jīng)有了一個(gè)可以讓我方收益更低的選擇，因此對(duì)手不會(huì)考慮一個(gè)比讓我們當(dāng)前收益更高的選擇
          continue;
        }
      }
    }else{//beta
      for(ChessNode node in children){
        if(maxMinSearch(node) > root.minValue){
          // 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)為MAX節(jié)點(diǎn)，也就是取所有子節(jié)點(diǎn)中最大的值
          // 換句話說(shuō)：這個(gè)父節(jié)點(diǎn)所產(chǎn)生的最小值不會(huì)低于所有子節(jié)點(diǎn)中的最大值，因此更新父節(jié)點(diǎn)的minValue
          root.minValue = node.value;
          root.value = node.value;
          root.checked = node.current;
        }else{
          // 當(dāng)前節(jié)點(diǎn)的值小于父節(jié)點(diǎn)的最小值，由于父節(jié)點(diǎn)值MAX節(jié)點(diǎn)，因此不會(huì)取該值
          // 換句話說(shuō)：當(dāng)前為自己回合，已經(jīng)有了一個(gè)可以使我方收益更高的選擇，那么就不會(huì)再考慮比這個(gè)收益更低的選擇了
          continue;
        }
      }
    }
    return root.value;
  }

通過(guò)這個(gè)算法，我們就可以計(jì)算出下一步落子何處在接下來(lái)的幾步中都是對(duì)我們最有利的解法。
但是有一個(gè)問(wèn)題，這種算法會(huì)遍歷每一個(gè)節(jié)點(diǎn)，隨著博弈樹(shù)的層數(shù)增加，要搜索的節(jié)點(diǎn)成指數(shù)式增長(zhǎng)；要解決這個(gè)問(wèn)題，我們就需要引入一個(gè)可以提升搜索效率的算法

0x03 Alpha-Beta剪枝算法搜索博弈樹(shù)

我們?cè)诨剡^(guò)頭來(lái)看上圖，在執(zhí)行到 J->V 的搜素后，我們發(fā)現(xiàn)J的最大值不會(huì)超過(guò)2（J為對(duì)手回合，對(duì)手會(huì)選擇我方得分最小的路徑），但是J的父節(jié)點(diǎn)E為我方回合，我方會(huì)選擇最大的值，通過(guò) E->K 的搜索可知：E最小不會(huì)低于6。既然已經(jīng)有了一個(gè)不低于6的選擇，那我們壓根兒就沒(méi)必要再去看一個(gè)不高于2的選擇中到底還有些什么選擇了，因?yàn)槲覀円褂螒蚋诩悍?，所以不?huì)選擇J節(jié)點(diǎn)這條路徑，那么 W、X、Y節(jié)點(diǎn)就沒(méi)有再遍歷的必要了（beta剪枝）
相似的，我們?cè)倏?G -> M 節(jié)點(diǎn)：
當(dāng)我們計(jì)算完M節(jié)點(diǎn)的值，發(fā)現(xiàn)M節(jié)點(diǎn)值為9，而M節(jié)點(diǎn)G的父節(jié)點(diǎn)是我方回合，我方會(huì)選擇最大的值，故這個(gè)值不會(huì)低于9，但是G的父節(jié)點(diǎn)C為對(duì)手回合，此時(shí)它已經(jīng)有一個(gè)1的值，它會(huì)選擇最小值，1 < 9 ,因此它不會(huì)選擇9這個(gè)值，也就是C節(jié)點(diǎn)不會(huì)選擇G節(jié)點(diǎn)，那么G節(jié)點(diǎn)就被廢棄了，它下的所有節(jié)點(diǎn)都沒(méi)有再遍歷的必要了（alpha剪枝）

經(jīng)過(guò)alpha-beta剪枝后的博弈樹(shù)

這樣就可以大大縮減所要搜索的節(jié)點(diǎn)數(shù)量，轉(zhuǎn)換為算法則是：

 /// alpha-beta 剪枝算法
  num alphaBetaSearch(ChessNode current){
    count++;
    if(current.childrenNode.isEmpty){
      return current.value;
    }

    //該枝已被剪掉
    if(current.parentNode!=null && !current.parentNode.childrenNode.contains(current)){
      ChessNode parent = current.parentNode;
      return parent.type == ChildType.MAX ? parent.minValue : parent.maxValue;
    }

    List<ChessNode> children = current.childrenNode;
    if(current.type == ChildType.MIN){
      num parentMin = current.parentNode?.minValue ?? double.negativeInfinity;
      int index = 0;
      for (ChessNode node in children) {
        index ++;
        //當(dāng)前節(jié)點(diǎn)node的父節(jié)點(diǎn)(current)為MIN節(jié)點(diǎn)，也就是取所有子節(jié)點(diǎn)值中最小的值，
        //換句話說(shuō)：這個(gè)節(jié)點(diǎn)(node)產(chǎn)生的最大值不會(huì)高于所有子節(jié)點(diǎn)中的最小值，因此取兩者間的最小值
        num newCurrentMax = math.min(current.maxValue, alphaBetaSearch(node));//K

        //current節(jié)點(diǎn)的值不能比current.parentNode的最小值還小，
        //若不符合這個(gè)條件則current節(jié)點(diǎn)沒(méi)有繼續(xù)搜索下去的必要
        //alpha剪枝
        if (newCurrentMax <= parentMin) { //V->J
          current.childrenNode = current.childrenNode.sublist(0, index);
          return parentMin;
        }

        //因?yàn)楫?dāng)前節(jié)點(diǎn)為MIN節(jié)點(diǎn)，如果發(fā)現(xiàn)一個(gè)比當(dāng)前最大值還小的值，則更新當(dāng)前節(jié)點(diǎn)的最大值為這個(gè)新值
        if (newCurrentMax < current.maxValue) {//A1->K
          current.maxValue = newCurrentMax;
          current.value = node.value;
          current.checked = node.current;
        }
      }
      //當(dāng)遍歷完成當(dāng)前節(jié)點(diǎn)后，如果發(fā)現(xiàn)父節(jié)點(diǎn)的最小值小于當(dāng)前節(jié)點(diǎn)的最大值，則更新父節(jié)點(diǎn)的最小值
      if(current.maxValue > parentMin){//K->E
        current.parentNode?.minValue = current.maxValue;
        current.parentNode?.value = current.value;
        current.parentNode?.checked = current.current;
      }
      return current.maxValue;
    }else{//beta(MAX節(jié)點(diǎn))
      num parentMax = current.parentNode?.maxValue ?? double.infinity;
      int index = 0;
      for(ChessNode node in children) {
       index ++;
       //當(dāng)前節(jié)點(diǎn)(node)的父節(jié)點(diǎn)(current)為MAX節(jié)點(diǎn)，也就是取所有子節(jié)點(diǎn)中最大的值
       //換句話說(shuō)：這個(gè)父節(jié)點(diǎn)(current)所產(chǎn)生的最小值不會(huì)低于所有子節(jié)點(diǎn)中的最大值，因此取兩者間的最大值
       num newCurrentMin = math.max(current.minValue, alphaBetaSearch(node));

       //current節(jié)點(diǎn)的父節(jié)點(diǎn)為MIN節(jié)點(diǎn)，如果current節(jié)點(diǎn)值的下界(current.minValue)比父節(jié)點(diǎn)(current.parentNode)的值的上界還大的話，
       //則父節(jié)點(diǎn)(current.parentNode)不會(huì)取當(dāng)前節(jié)點(diǎn)current路徑，故無(wú)需在搜索
       //beta剪枝
       if(parentMax < newCurrentMin){//M->G
         current.childrenNode = current.childrenNode.sublist(0,index);
         return parentMax;
       }

       //因?yàn)楫?dāng)前節(jié)點(diǎn)為MAX節(jié)點(diǎn)，如果發(fā)現(xiàn)一個(gè)比當(dāng)前最小值還大的新值，則更新當(dāng)前節(jié)點(diǎn)的最小值為這個(gè)新值
       if(newCurrentMin > current.minValue){
         current.minValue = newCurrentMin;
         current.value = node.value;
         current.checked = node.current;
       }
      }
      //當(dāng)遍歷完成當(dāng)前節(jié)點(diǎn)后，如果發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)的最小值比父節(jié)點(diǎn)的最大值還小的話，則更新父節(jié)點(diǎn)的最大值
      if(current.minValue < parentMax){//D->B
        current.parentNode?.maxValue = current.minValue;
        current.parentNode?.value = current.value;
        current.parentNode?.checked = current.current;
      }
      return current.minValue;
    }
  }

0x04 成果體驗(yàn)

最后附上截圖、git庫(kù)地址和apk包(iOS包由于簽名問(wèn)題可以自行clone代碼后打包)

游戲截圖

黑子為普通AI，白子為智能AI
git庫(kù)：
https://github.com/zhangguoning/gobang
APK體驗(yàn)：
app下載1（GitHub）
app下載2（碼云，備用下載地址）

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

基于alpha-beta剪枝算法的Flutter五子棋游戲AI實(shí)現(xiàn)

基于alpha-beta剪枝算法的Flutter五子棋游戲AI實(shí)現(xiàn)

0x00 前言

0x01 已有的AI實(shí)現(xiàn)原理

0x02 Max-Min算法搜索博弈樹(shù)

0x03 Alpha-Beta剪枝算法搜索博弈樹(shù)

0x04 成果體驗(yàn)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

基于alpha-beta剪枝算法的Flutter五子棋游戲AI實(shí)現(xiàn)

0x00 前言

0x01 已有的AI實(shí)現(xiàn)原理

0x02 Max-Min算法搜索博弈樹(shù)

0x03 Alpha-Beta剪枝算法搜索博弈樹(shù)

0x04 成果體驗(yàn)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av