用Python写一个中国象棋AI？-Python-Tutorial-php.cn

我本人是大二学生，对编程比较感兴趣，现在正在学习python语言，如今正在做中国象棋的项目，我已经做出了能下棋的一步，现在在对人机对战方面很感兴趣，不知道从哪里入手，有没有大神对中国象棋AI有简单的认识吗？介绍点资料或者是代码给我参考一下。多谢！
回复内容：

我只讲一下棋类AI一般的实现方法（或者叫传统的实现方法）：
我在这里贴了一个实现棋类软件AI的简单代码（C语言）：

本人原创四人象棋，大家有什么补充的吗？ - 知乎用户的回答

这是一个我自己设计的象棋，中国象棋的迷你版——小象棋。

该代码包含了实现棋类软件AI的基本思想，你把它改为中国象棋的规则就可以了。
写一个象棋类AI主要包含以下四步：

第一步：局面表示 -- 构成可下棋的基本元素
第二步：走法生成 -- 实现下棋的规则
第三步：局面评估 -- 量化一个局面的双方优劣势
第四步：局面搜索 -- 让电脑具备思考的能力

===========================严重分割线===================================
===========================严重分割线===================================

除了刚才上面那个小象棋。

我再举个例子：六子冲棋

六子冲棋规则参考维基百科：六子沖棋

====================重要补充插入START==================
刚才看了一下维基百科描写的规则和我们这边民间流传的规则略有不同，
以下程序是根据我们当地民间规则实现的，请参考：六子冲_百度百科
====================重要补充插入 E N D ==================

这个例子具体说明如何通过上述四步实现一个棋类AI。

不废话，直接上原创的完整代码，注释已经很详细。（C语言）
<code class="language-c"><span class="cm">/*************************************************************</span>
<span class="cm">* = 民间六子棋(六子冲)人机博弈引擎实现与教程 =</span>
<span class="cm">* </span>
<span class="cm">*              www.leilei.name </span>
<span class="cm">* </span>
<span class="cm">*       by LeiLei 2010.3.2 - 2010.3.5</span>
<span class="cm">* </span>
<span class="cm">* </span>
<span class="cm">* 本教程主要讲解六子冲棋的博弈引擎实现，不讲解界面实现部分。</span>
<span class="cm">* 本教程共分四节讲解：</span>
<span class="cm">*  </span>
<span class="cm">* 第一节：局面表示 -- 构成可下棋的基本元素 </span>
<span class="cm">* 第二节：走法生成 -- 实现下棋的规则 </span>
<span class="cm">* 第三节：局面评估 -- 量化一个局面的双方优劣势 </span>
<span class="cm">* 第四节：局面搜索 -- 让电脑具备思考的能力 </span>
<span class="cm">* </span>
<span class="cm">* 本教程主要以便于理解为目标，不追求代码技巧，希望对写代码实践</span>
<span class="cm">* 较少的你，会有所帮助。</span>
<span class="cm">*/</span>

<span class="cm">/*************************************************************</span>
<span class="cm">* = 附：六子冲介绍 =</span>
<span class="cm">*  </span>
<span class="cm">*     六子冲是流传于中国民间的一类棋类游戏。由于这个游戏对环境的</span>
<span class="cm">* 要求不高,孩子们大都是在光滑的地面或石板上画上方格，以石子或木</span>
<span class="cm">* 棍、草节等为棋子，并有简单的比赛规则:</span>
<span class="cm">* </span>
<span class="cm">*     纵横各四条直线组成一个正方形棋盘，直线相交的地方为落子点。</span>
<span class="cm">* 开局时放子处为上下左右边线上的落子点，且不同方的子不可交叉放置。</span>
<span class="cm">* 游戏双方着二色棋子各6个在一 个“九宫”型棋盘上进行对抗因为游戏双</span>
<span class="cm">* 方各着6个棋子，故名“六子冲”。　棋子只能停留在棋盘上的落子点，棋</span>
<span class="cm">* 子只能在线上移动，棋子只能移动一步(即相邻落子点)，每回合只能移</span>
<span class="cm">* 动1个棋子。消灭对方棋子的方法只有一条，也很简单。那就是：二子打</span>
<span class="cm">* 一子。即在棋盘上攻击方的2个棋子(2子必须相连并主动移动其中的1个)</span>
<span class="cm">* 与被攻方的1个棋子皆处在一条直线上并相邻时，被攻方的这个棋子就被</span>
<span class="cm">* 消灭。重复上面的步骤，保护自己的棋子并消灭对方的棋子，直到最后</span>
<span class="cm">* 胜利。</span>
<span class="cm">* </span>
<span class="cm">* 开始：双方棋子数均为六颗，分列棋盘四周，见图片“六子冲开始时”。</span>
<span class="cm">* </span>
<span class="cm">* 吃子：行棋一方若将两颗棋子移至一排，且一头挨着对方的一颗棋时，</span>
<span class="cm">*       则可吃子，见图片“吃子”。</span>
<span class="cm">* </span>
<span class="cm">* 注意：</span>
<span class="cm">* 　　1.行棋一方若将三颗棋子移至一排，不可吃子，见图1。</span>
<span class="cm">* 　　2.行棋一方若将两颗棋子移至一排，但一头挨着对方的两颗棋，不可</span>
<span class="cm">*       子吃，见图2。</span>
<span class="cm">* 　　3.行棋一方若将两颗棋子移至一排，但两头分别挨着对方的一颗棋，</span>
<span class="cm">*       不可吃子，见图3。</span>
<span class="cm">* 　　4.行棋一方若将两颗棋子移至一排，且一头挨着对方的一颗棋时，但</span>
<span class="cm">*       对方的该颗棋后有我方棋，不可吃子见图4。</span>
<span class="cm">* </span>
<span class="cm">* 流传:</span>
<span class="cm">* 　　    有好多民间代代相承的传统儿戏，在六七十年代仍十分盛行，80年</span>
<span class="cm">*     代后逐渐衰落。80年代以后，由于社会生活和居住环境的变化，孩子们</span>
<span class="cm">*     聚在一起玩耍的机会较少，又有新兴的各类现代化的高档玩具流行，这</span>
<span class="cm">*     样的游戏则逐渐鲜为人知了。</span>
<span class="cm">* 　　    六子冲就是其中最有代表性的一项游戏.也是当年的小孩子因陋就</span>
<span class="cm">*     简玩的一种棋类游戏。据传，六子冲游戏源自中国古代战争的士兵阵</span>
<span class="cm">*     型训练，后逐渐演变为一种棋类游戏。六子冲规则简单，上手容易，但</span>
<span class="cm">*     变化无穷，是一种让人玩起来就欲罢不能的智力对抗游戏。六子冲游戏</span>
<span class="cm">*     在上世纪主要流行于中国四川一带。</span>
<span class="cm">* 　　    在中国山区农村流传甚广，，由于规则简单，工具可信手拈来，是</span>
<span class="cm">*     我国乡间常见的棋类游戏。在商洛镇安，涪城等地农村流行。</span>
<span class="cm">*     顾问：姜年檑</span>
<span class="cm">*    (以上文字摘自百度百科，参见原文请访问：</span>
<span class="cm">*                           http://baike.baidu.com/view/2472074.htm)</span>
<span class="cm">* </span>
<span class="cm">*/</span>

<span class="cp">#include <stdio.h></stdio.h></span>

<span class="cm">/*************************************************************</span>
<span class="cm">* = 第一节  局面表示 =</span>
<span class="cm">*</span>
<span class="cm">* 1.1 棋子表示</span>
<span class="cm">* </span>
<span class="cm">* 棋子可以随便用个数字表示，可以把它定义为常量，</span>
<span class="cm">* 但是有时候为了方便运算和转换，也应该精心挑选用哪些数字表示棋子。</span>
<span class="cm">* 这里演示就随便选两个数字。</span>
<span class="cm">* </span>
<span class="cm">* (1)需要定义用来表示棋子的常量</span>
<span class="cm">* </span>
<span class="cm">* 如下所示： </span>
<span class="cm">*/</span>

<span class="cp">#define  STONE     3 </span><span class="c1">//定义常量 石头(白色棋子)</span>
<span class="cp">#define  LEAF      7 </span><span class="c1">//         树叶(黑色棋子)</span>
<span class="cp">#define  WHITE     0 </span><span class="c1">//         白方用0表示</span>
<span class="cp">#define  BLACK     1 </span><span class="c1">//         黑方用1表示</span>
<span class="cp">#define  NOPIECE   0 </span><span class="c1">//         无棋子用0</span>

<span class="cm">/*</span>
<span class="cm">* 1.2 棋盘表示</span>
<span class="cm">*</span>
<span class="cm">* 我们可以用数组来表示棋盘 </span>
<span class="cm">* 用4*4的二维数组就可以表示这个游戏的棋盘结构和棋子在棋盘上的分布了。如下(简单吧)： </span>
<span class="cm">* int board[4][4] = { // 对应坐标：</span>
<span class="cm">*   3, 3, 3, 3,       // (0,0), (1,0), (2,0), (3,0),</span>
<span class="cm">*   3, 0, 0, 3,       // (0,1), (1,1), (2,1), (3,1),</span>
<span class="cm">*   7, 0, 0, 7,       // (0,2), (1,2), (2,2), (3,2), </span>
<span class="cm">*   7, 7, 7, 7        // (0,3), (1,3), (2,3), (3,3),</span>
<span class="cm">* };</span>
<span class="cm">* </span>
<span class="cm">* 数组下标构成的坐标表示棋子在棋盘上的位置。</span>
<span class="cm">* 可以用0表示棋盘上无棋子。 </span>
<span class="cm">* 我们可以用4*4的数组表示棋盘，但是为了运算方便，这里我们采用8*8的一维数组来装棋盘，效果更好。</span>
<span class="cm">* 我们可以把棋盘放在数组的中央。</span>
<span class="cm">* 然后我们用一个8*8的inBoard数组来标识棋盘在数组中的位置。</span>
<span class="cm">* 棋子在棋盘上的位置，我们直接用数组下标表示。</span>
<span class="cm">* </span>
<span class="cm">* 所以，</span>
<span class="cm">* (1)我们需要一个用来表示棋盘的数组 </span>
<span class="cm">* (2)我们用一个数组来标识棋盘在数组中的位置(用来判断棋子是否在棋盘上) </span>
<span class="cm">* (3)写几个函数来转换坐标。</span>
<span class="cm">* </span>
<span class="cm">* 如下所示：</span>
<span class="cm">*/</span>

<span class="c1">//棋盘数组(带开局棋子位置)</span>
<span class="kt">int</span> <span class="n">board</span><span class="p">[</span><span class="mi">64</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span>
<span class="p">};</span>

<span class="c1">//用来标记棋子是否在棋盘上的数组</span>
<span class="k">static</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">inBoard</span><span class="p">[</span><span class="mi">64</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span>
  <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span>
<span class="p">};</span>

<span class="c1">//根据棋盘的特征，我们写三个可以转换和取得棋盘坐标的函数//////////////////////////</span>

<span class="c1">//由棋盘数组下标获得棋子X坐标</span>
<span class="kt">int</span> <span class="nf">getXFromLocation</span><span class="p">(</span><span class="kt">int</span> <span class="n">location</span><span class="p">){</span>
  <span class="k">return</span> <span class="p">(</span><span class="n">location</span> <span class="o">&</span> <span class="mi">7</span><span class="p">)</span> <span class="o">-</span> <span class="mi">2</span><span class="p">;</span>
<span class="p">}</span> 

<span class="c1">//由棋盘数组下标获得棋子Y坐标</span>
<span class="kt">int</span> <span class="nf">getYFromLocation</span><span class="p">(</span><span class="kt">int</span> <span class="n">location</span><span class="p">){</span>
  <span class="k">return</span> <span class="p">(</span><span class="n">location</span> <span class="o">>></span> <span class="mi">3</span><span class="p">)</span> <span class="o">-</span> <span class="mi">2</span><span class="p">;</span>
<span class="p">}</span> 

<span class="c1">//由棋子X坐标，Y坐标获得棋盘数组下标</span>
<span class="kt">int</span> <span class="nf">getLocationFromXY</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="kt">int</span> <span class="n">y</span><span class="p">){</span>
  <span class="k">return</span> <span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="mi">2</span><span class="p">)</span> <span class="o">+</span> <span class="p">(</span><span class="n">y</span> <span class="o">+</span> <span class="mi">2</span> <span class="o"> <span class="mi">3</span><span class="p">);</span>
<span class="p">}</span>

<span class="cm">/*</span>
<span class="cm">* 1.3 当前走棋方表示</span>
<span class="cm">* </span>
<span class="cm">* (1)我们需要一个变量来表示当前该哪方走棋</span>
<span class="cm">* (2)还需要一个用来改变走其方的函数changePlayer()</span>
<span class="cm">* </span>
<span class="cm">* 如下所示： </span>
<span class="cm">*/</span>

<span class="kt">int</span> <span class="n">currentPlayer</span> <span class="o">=</span> <span class="n">WHITE</span><span class="p">;</span> <span class="c1">//初始化为白方走棋，BLACK表示黑方走棋 </span>

<span class="kt">void</span> <span class="nf">changePlayer</span><span class="p">(){</span>
  <span class="n">currentPlayer</span> <span class="o">=</span> <span class="mi">1</span> <span class="o">-</span> <span class="n">currentPlayer</span><span class="p">;</span> <span class="c1">//改变走棋方，不是0 就是1 </span>
<span class="p">}</span>

<span class="cm">/*</span>
<span class="cm">* 1.4 在棋盘上放棋子和拿走棋子 </span>
<span class="cm">* </span>
<span class="cm">* 有了棋盘，我们就可以在棋盘上放棋子了</span>
<span class="cm">* </span>
<span class="cm">* (1)所以我们还需要几个函数用来在棋盘上放棋子和拿走棋子。 </span>
<span class="cm">* </span>
<span class="cm">* 如下所示： </span>
<span class="cm">*/</span>

<span class="c1">//在棋盘上放一枚棋子的函数</span>
<span class="kt">void</span> <span class="nf">addPiece</span><span class="p">(</span><span class="kt">int</span> <span class="n">location</span><span class="p">){</span> <span class="c1">//根据位置和当前走棋方添加棋子</span>
  <span class="kt">int</span> <span class="n">piece</span><span class="p">;</span>
  
  <span class="n">piece</span> <span class="o">=</span> <span class="n">currentPlayer</span> <span class="o">*</span> <span class="mi">4</span> <span class="o">+</span> <span class="mi">3</span><span class="p">;</span> <span class="c1">//由当前走棋方计算当前走棋方棋子</span>
  
  <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">location</span><span class="p">]){</span>
    <span class="n">board</span><span class="p">[</span><span class="n">location</span><span class="p">]</span> <span class="o">=</span> <span class="n">piece</span><span class="p">;</span>
  <span class="p">}</span>
<span class="p">}</span>

<span class="c1">//在棋盘上拿走一枚棋子的函数</span>
<span class="kt">void</span> <span class="nf">delPiece</span><span class="p">(</span><span class="kt">int</span> <span class="n">location</span><span class="p">){</span> <span class="c1">//根据位置删除棋子 </span>
  <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">location</span><span class="p">]){</span>
    <span class="n">board</span><span class="p">[</span><span class="n">location</span><span class="p">]</span> <span class="o">=</span> <span class="n">NOPIECE</span><span class="p">;</span> <span class="c1">//NOPIECE == 0表示无棋子 </span>
  <span class="p">}</span>
<span class="p">}</span>

<span class="cm">/*************************************************************</span>
<span class="cm">* = 第二节  走法生成 =</span>
<span class="cm">*</span>
<span class="cm">* 2.1 走法表示</span>
<span class="cm">*</span>
<span class="cm">* 走法表示就是用一个变量来表示棋子从棋盘上哪里走到哪里。</span>
<span class="cm">* 我们可以定义一个结构体来表示一个走法，也可以用一串数字表示。</span>
<span class="cm">* 在本程序里，我们用一个int类型来表示一个走法，低位表示起点位</span>
<span class="cm">* 置(的棋盘数组下标)，高位表示目的位置(的棋盘数组下标)。</span>
<span class="cm">* </span>
<span class="cm">* 由此，</span>
<span class="cm">* (1)我们需要写几个函数来处理走法的起点和终点。</span>
<span class="cm">* </span>
<span class="cm">* 如下： </span>
<span class="cm">*/</span>

<span class="c1">//根据走法生成走法起点位置(起点位置的棋盘数组下标)</span>
<span class="kt">int</span> <span class="nf">generateMoveFrom</span><span class="p">(</span><span class="kt">int</span> <span class="n">move</span><span class="p">){</span>
  <span class="k">return</span> <span class="n">move</span> <span class="o">&</span> <span class="mi">255</span><span class="p">;</span>
<span class="p">}</span>

<span class="c1">//根据走法生成走法目的位置(目的位置的棋盘数组下标)</span>
<span class="kt">int</span> <span class="nf">generateMoveTo</span><span class="p">(</span><span class="kt">int</span> <span class="n">move</span><span class="p">){</span>
  <span class="k">return</span> <span class="n">move</span> <span class="o">>></span> <span class="mi">8</span><span class="p">;</span>
<span class="p">}</span>

<span class="c1">//由起点位置和目的位置合成走法</span>
<span class="kt">int</span> <span class="nf">composeMove</span><span class="p">(</span><span class="kt">int</span> <span class="n">locationFrom</span><span class="p">,</span> <span class="kt">int</span> <span class="n">locationTo</span><span class="p">){</span>
  <span class="k">return</span> <span class="n">locationFrom</span> <span class="o">+</span> <span class="n">locationTo</span> <span class="o">*</span> <span class="mi">256</span><span class="p">;</span>
<span class="p">}</span>

<span class="cm">/*</span>
<span class="cm">* 2.2 走法生成 </span>
<span class="cm">*</span>
<span class="cm">* 走法生成就是生成一个局面可以有哪些走法，一般是用一个函数来生成所有可能的走法。 </span>
<span class="cm">* 生成的这些走法，我们可以保存在一个走法列表里，方面使用。</span>
<span class="cm">* 我们可以用这个走法列表来判断一步棋是否合法，最重要的是，我们需要用这个走法列表来搜索所有可能的局面。 </span>
<span class="cm">* 六子冲的每颗棋子都是按上下左右四个方向走，通过对棋盘数组下标的观察，我们可以用原位置的数组下标分别</span>
<span class="cm">* 加上-8、8、-1、1四个数就分别得到往上、下、左、右四个方向走一步的位置的数组下标。所以我们用一个数组</span>
<span class="cm">* 存储这四个数。</span>
<span class="cm">* </span>
<span class="cm">* (1)定义一个常量MAX_GEN_MOVES来表示最大生成的走法数</span>
<span class="cm">* (2)我们需要声明一个数组用来保存生成的走法列表</span>
<span class="cm">* (3)用一个数组来表示棋子可走的方向</span>
<span class="cm">* (4)还需要写一个一次性生成所有走法的函数。</span>
<span class="cm">*/</span>

<span class="cp">#define MAX_GEN_MOVES 32 </span><span class="c1">//这里顺便定义一个常量来表示走法的最大生成数 </span>

<span class="k">static</span> <span class="kt">int</span> <span class="n">theMoves</span><span class="p">[</span><span class="n">MAX_GEN_MOVES</span><span class="p">];</span> <span class="c1">//定义一个走法数组用来保存生成的所有走法，一个局面最多走法数不会超过MAX_GEN_MOVES种 </span>

<span class="k">static</span> <span class="k">const</span> <span class="kt">char</span> <span class="n">movesTable</span><span class="p">[</span><span class="mi">4</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="o">-</span><span class="mi">8</span><span class="p">,</span> <span class="mi">8</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">};</span> <span class="c1">//这个数组用来表示棋子的走子方向</span>

<span class="c1">//走法生成函数，产生一个局面的所有走法 </span>
<span class="kt">int</span> <span class="nf">generateAllMoves</span><span class="p">(</span><span class="kt">int</span> <span class="o">*</span><span class="n">moves</span><span class="p">){</span> <span class="c1">//传递一个走法列表数组指针，返回生成的所有走法 </span>
  <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">from</span><span class="p">,</span> <span class="n">to</span><span class="p">,</span> <span class="n">genCount</span><span class="p">;</span>
  <span class="kt">int</span> <span class="n">myPiece</span><span class="p">,</span> <span class="n">pieceFrom</span><span class="p">,</span> <span class="n">pieceTo</span><span class="p">;</span>
  
  <span class="c1">//走法计数器清零</span>
  <span class="n">genCount</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
  <span class="c1">//获取当前走棋方标记</span>
  <span class="n">myPiece</span> <span class="o">=</span> <span class="n">currentPlayer</span> <span class="o">*</span> <span class="mi">4</span> <span class="o">+</span> <span class="mi">3</span><span class="p">;</span> <span class="c1">//根据当前走棋方，确定当前走棋方棋子 </span>
  
  <span class="c1">//遍历棋盘找到当前走棋方棋子</span>
  <span class="k">for</span><span class="p">(</span><span class="n">from</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">from</span> <span class="o"> <span class="mi">64</span><span class="p">;</span> <span class="n">from</span><span class="o">++</span><span class="p">){</span>
    <span class="c1">//取得当前位置的棋子</span>
    <span class="n">pieceFrom</span> <span class="o">=</span> <span class="n">board</span><span class="p">[</span><span class="n">from</span><span class="p">];</span>
    
    <span class="c1">//1.如果找到的不是本方棋子，继续找</span>
    <span class="k">if</span><span class="p">(</span><span class="n">pieceFrom</span> <span class="o">!=</span> <span class="n">myPiece</span><span class="p">){</span> 
      <span class="k">continue</span><span class="p">;</span>
    <span class="p">}</span>
    
    <span class="c1">//2.如果找到本方棋子，探测四个方向是否可走</span>
    <span class="k">for</span><span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"> <span class="mi">4</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span>
      <span class="n">to</span> <span class="o">=</span> <span class="n">from</span> <span class="o">+</span> <span class="n">movesTable</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="c1">//目标位置</span>
      <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">to</span><span class="p">]){</span> <span class="c1">//如果还在棋盘内</span>
        <span class="n">pieceTo</span> <span class="o">=</span> <span class="n">board</span><span class="p">[</span><span class="n">to</span><span class="p">];</span> <span class="c1">//获取此位置棋子</span>
        <span class="k">if</span><span class="p">(</span><span class="n">pieceTo</span> <span class="o">==</span> <span class="n">NOPIECE</span><span class="p">){</span> <span class="c1">//如果此位置无棋子，此走法可行 </span>
          <span class="n">moves</span><span class="p">[</span><span class="n">genCount</span><span class="p">]</span> <span class="o">=</span> <span class="n">composeMove</span><span class="p">(</span><span class="n">from</span><span class="p">,</span> <span class="n">to</span><span class="p">);</span> <span class="c1">//保存走法 </span>
          <span class="n">genCount</span><span class="o">++</span><span class="p">;</span> <span class="c1">//计数</span>
        <span class="p">}</span> 
      <span class="p">}</span> 
    <span class="p">}</span><span class="c1">//end for(i)</span>
    
  <span class="p">}</span><span class="c1">//end for(from)</span>
  <span class="k">return</span> <span class="n">genCount</span><span class="p">;</span> <span class="c1">//返回生成的走法数</span>
<span class="p">}</span>

<span class="cm">/*</span>
<span class="cm">* 2.3 走一步棋 </span>
<span class="cm">* </span>
<span class="cm">* 要走一步棋很简单，我们只需要先把要走的棋子从棋盘的原位置上拿</span>
<span class="cm">* 走，然后再把这颗棋子放在棋盘上的目标位置上。我们可以利用前面</span>
<span class="cm">* 的addPiece()和delPiece()函数来写一个走棋函数。</span>
<span class="cm">* </span>
<span class="cm">* 在走一步棋之前，我们最好先判断这步棋是否符合走棋规则，以免引</span>
<span class="cm">* 起以后的混乱，我们可以利用走法生成函数来判断一步棋是否合法。 </span>
<span class="cm">* 有的时候为了提高效率也可以单独写一个函数判断走法是否合法。 </span>
<span class="cm">* 在这里为了简单就用直接利用走法生成函数，生成所有走法，如果走</span>
<span class="cm">* 法在走法列表里说明走法合法。 </span>
<span class="cm">* </span>
<span class="cm">* 走一步棋后往往会引发吃子，六子冲的吃子需要我们进行检查，六子</span>
<span class="cm">* 冲的吃子不光与所走棋子有关，还与其他棋子的合作有关。</span>
<span class="cm">* </span>
<span class="cm">* 在下一节的局面搜索中，我们还会用到走棋函数，并且在搜索的过程</span>
<span class="cm">* 中，我们会在棋盘上走棋，以探测未来棋局的变化和走势，为了不破</span>
<span class="cm">* 坏当前局面，每走一步棋我们就要记录当前的走法和所吃的子，以便</span>
<span class="cm">* 还原，所以在吃子过程中，我们需要记录吃子的位置。</span>
<span class="cm">* </span>
<span class="cm">* (1)写一个能在棋盘上走一步棋的函数。</span>
<span class="cm">*/</span>

<span class="cm">/**吃子参考方案 - 检查序列法**</span>

<span class="cm">//吃子检查序列数组</span>
<span class="cm">static int eatSequence[2][2][4] = {</span>
<span class="cm">  {{7, 3, 3, 0},{0, 7, 3, 3}},</span>
<span class="cm">  {{3, 7, 7, 0},{0, 3, 7, 7}}</span>
<span class="cm">};</span>

<span class="cm">//检查吃子的函数，无返回吃子位置部分</span>
<span class="cm">int checkEat(int to){</span>
<span class="cm">  int i, j, k, step, eat, check; //检查吃子专用</span>
<span class="cm">  int pieceSequence[4]; //pieceSequence用来保存棋子序列(检查吃子时用)</span>
<span class="cm">  </span>
<span class="cm">  // 检查吃子，从上往下、从下往上、从左往右、从右往左，沿四个方向检查吃子情况</span>
<span class="cm">  // 比如：从左往右检查，只需检查是否呈“●○○_”或“_●○○”序列(假如白方为当前方)</span>
<span class="cm">  </span>
<span class="cm">  for(i = 0; i 
<span class="cm">    </span>
<span class="cm">    //1. 取得焦点位置(焦点就是当前检查点)</span>
<span class="cm">    check = to; //check变量这时作为焦点位置</span>
<span class="cm">    </span>
<span class="cm">    //2. 取得步长</span>
<span class="cm">    step = movesTable[i];</span>
<span class="cm">    </span>
<span class="cm">    //3. 把焦点位置往反方向移动到棋盘边上</span>
<span class="cm">    while(inBoard[check]){</span>
<span class="cm">      check -= step; //往反方向移动焦点</span>
<span class="cm">    }</span>
<span class="cm">    </span>
<span class="cm">    //4. 往正方向取得棋子序列，保存在数组pieceSequence中</span>
<span class="cm">    for(j = 0; j 
<span class="cm">      form += step; //往正方向移动焦点</span>
<span class="cm">      if(inBoard[check]){</span>
<span class="cm">        pieceSequence[j] = board[check];</span>
<span class="cm">      }</span>
<span class="cm">    }</span>
<span class="cm">    </span>
<span class="cm">    //5. 把焦点位置再次往反方向移动到棋盘边上，以便由焦点位置根据吃子序列数组取得吃子位置</span>
<span class="cm">    while(inBoard[check]){</span>
<span class="cm">      check -= step; //往反方向移动焦点</span>
<span class="cm">    }</span>
<span class="cm">    </span>
<span class="cm">    //6. 检查棋子序列是否与两个吃子序列匹配，若匹配则吃子</span>
<span class="cm">    for(k = 0; k 
<span class="cm">      //6.1 初始化为有子可吃</span>
<span class="cm">      eat = 1;</span>
<span class="cm">      //6.2 检查序列是否完全匹配</span>
<span class="cm">      for(j = 0; j 
<span class="cm">        if(pieceSequence[j] != eatSequence[currentPlayer][k][j]){</span>
<span class="cm">          eat = 0;</span>
<span class="cm">        }</span>
<span class="cm">      }</span>
<span class="cm">      //6.3 检查到序列完全匹配则，按位置吃子</span>
<span class="cm">      if(eat == 1){</span>
<span class="cm">        delPiece(check + step * (k + 1)); //由焦点取得吃子位置</span>
<span class="cm">      }</span>
<span class="cm">    }</span>
<span class="cm">  }</span>
<span class="cm">}</span>
<span class="cm">*/</span>

<span class="c1">//能根据走法走一步棋的函数 </span>
<span class="kt">int</span> <span class="nf">makeOneMove</span><span class="p">(</span><span class="kt">int</span> <span class="n">move</span><span class="p">,</span> <span class="kt">int</span> <span class="o">*</span><span class="n">eatTable</span><span class="p">){</span> <span class="c1">//传递一个用来保存吃子位置的数组</span>
  <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">genCount</span><span class="p">,</span> <span class="n">isLegalMove</span><span class="p">,</span> <span class="n">from</span><span class="p">,</span> <span class="n">to</span><span class="p">;</span>
  <span class="kt">int</span> <span class="n">step</span><span class="p">,</span> <span class="n">focus</span><span class="p">,</span> <span class="n">myPiece</span><span class="p">,</span> <span class="n">oppPiece</span><span class="p">,</span> <span class="n">eatCount</span><span class="p">;</span> <span class="c1">//吃子专用</span>
  
  <span class="n">isLegalMove</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="c1">//初始化走法为不合法</span>
  <span class="n">genCount</span> <span class="o">=</span> <span class="n">generateAllMoves</span><span class="p">(</span><span class="n">theMoves</span><span class="p">);</span> <span class="c1">//生成所有走法</span>
  <span class="c1">//在所有走法中查找当前走法是否存在</span>
  <span class="k">for</span><span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"> <span class="n">genCount</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span>
    <span class="c1">//如果找到一个走法等于当前走法 </span>
    <span class="k">if</span><span class="p">(</span><span class="n">theMoves</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">move</span><span class="p">){</span>
      <span class="n">isLegalMove</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="c1">//所有走法中有此走法，说明走法合法</span>
      <span class="k">break</span><span class="p">;</span> 
    <span class="p">}</span>
  <span class="p">}</span>
  
  <span class="c1">//1.首先判断走法是否合法</span>
  <span class="k">if</span><span class="p">(</span><span class="n">isLegalMove</span> <span class="o">==</span> <span class="mi">1</span><span class="p">){</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="c1">//返回走棋失败 </span>
  <span class="p">}</span>
  
  <span class="c1">//2.分解走法，取得起点位置和目的位置</span>
  <span class="n">from</span> <span class="o">=</span> <span class="n">generateMoveFrom</span><span class="p">(</span><span class="n">move</span><span class="p">);</span>
  <span class="n">to</span> <span class="o">=</span> <span class="n">generateMoveTo</span><span class="p">(</span><span class="n">move</span><span class="p">);</span>
  
  <span class="c1">//3.走一步棋</span>
  <span class="n">delPiece</span><span class="p">(</span><span class="n">from</span><span class="p">);</span>
  <span class="n">addPiece</span><span class="p">(</span><span class="n">to</span><span class="p">);</span>
  
  <span class="c1">//4.检查吃子</span>
  <span class="n">eatCount</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="c1">//一步有可能同时吃掉两子</span>
  <span class="n">myPiece</span> <span class="o">=</span> <span class="n">currentPlayer</span> <span class="o">*</span> <span class="mi">4</span> <span class="o">+</span> <span class="mi">3</span><span class="p">;</span>        <span class="c1">//由当前走棋方计算当前走棋方棋子</span>
  <span class="n">oppPiece</span> <span class="o">=</span> <span class="p">(</span><span class="mi">1</span> <span class="o">-</span> <span class="n">currentPlayer</span><span class="p">)</span> <span class="o">*</span> <span class="mi">4</span> <span class="o">+</span> <span class="mi">3</span><span class="p">;</span> <span class="c1">//由当前走棋方计算对方棋子</span>
  
  <span class="c1">//检查吃子，从上往下、从下往上、从左往右、从右往左，沿四个方向检查吃子情况</span>
  <span class="k">for</span><span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"> <span class="mi">4</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span>
    
    <span class="n">step</span> <span class="o">=</span> <span class="n">movesTable</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="c1">//取得步长</span>
    
    <span class="c1">//检查是否为第一种吃子情况“○○●_” 所走棋子为序列中的第一个白子</span>
    <span class="n">focus</span> <span class="o">=</span> <span class="n">to</span> <span class="o">+</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到棋子前方第一个位置</span>
    <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">&&</span> <span class="n">board</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">==</span> <span class="n">myPiece</span><span class="p">){</span>
      <span class="n">focus</span> <span class="o">+=</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到棋子前方第二个位置</span>
      <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">&&</span> <span class="n">board</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">==</span> <span class="n">oppPiece</span><span class="p">){</span>
        <span class="n">focus</span> <span class="o">+=</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到棋子前方第三个位置</span>
        <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">&&</span> <span class="n">board</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">==</span> <span class="n">NOPIECE</span><span class="p">){</span>
          <span class="n">focus</span> <span class="o">-=</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到吃子位置</span>
          <span class="n">delPiece</span><span class="p">(</span><span class="n">focus</span><span class="p">);</span> <span class="c1">//吃子</span>
          <span class="n">eatTable</span><span class="p">[</span><span class="n">eatCount</span><span class="p">]</span> <span class="o">=</span> <span class="n">focus</span><span class="p">;</span> <span class="c1">//记录吃子的位置</span>
          <span class="n">eatCount</span><span class="o">++</span><span class="p">;</span> <span class="c1">//计数</span>
        <span class="p">}</span>
      <span class="p">}</span>
    <span class="p">}</span>
    
    <span class="c1">//检查是否为第二种吃子情况“○○●_” 所走棋子为序列中的第二个白子</span>
    <span class="n">focus</span> <span class="o">=</span> <span class="n">to</span> <span class="o">-</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到棋子后方位置</span>
    <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">&&</span> <span class="n">board</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">==</span> <span class="n">myPiece</span><span class="p">){</span>
      <span class="n">focus</span> <span class="o">=</span> <span class="n">to</span> <span class="o">+</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到棋子前方第一个位置</span>
      <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">&&</span> <span class="n">board</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">==</span> <span class="n">oppPiece</span><span class="p">){</span>
        <span class="n">focus</span> <span class="o">+=</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到棋子前方第二个位置</span>
        <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">&&</span> <span class="n">board</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">==</span> <span class="n">NOPIECE</span><span class="p">){</span>
          <span class="n">focus</span> <span class="o">-=</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到吃子位置</span>
          <span class="n">delPiece</span><span class="p">(</span><span class="n">focus</span><span class="p">);</span> <span class="c1">//吃子</span>
          <span class="n">eatTable</span><span class="p">[</span><span class="n">eatCount</span><span class="p">]</span> <span class="o">=</span> <span class="n">focus</span><span class="p">;</span> <span class="c1">//记录吃子的位置</span>
          <span class="n">eatCount</span><span class="o">++</span><span class="p">;</span> <span class="c1">//计数</span>
        <span class="p">}</span>
      <span class="p">}</span>
    <span class="p">}</span>
   
    <span class="c1">//检查是否为第三种吃子情况“●○○_” 所走棋子为序列中的第二个白子</span>
    <span class="n">focus</span> <span class="o">=</span> <span class="n">to</span> <span class="o">-</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到棋子后方位置</span>
    <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">&&</span> <span class="n">board</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">==</span> <span class="n">oppPiece</span><span class="p">){</span>
      <span class="n">focus</span> <span class="o">=</span> <span class="n">to</span> <span class="o">+</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到棋子前方第一个位置</span>
      <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">&&</span> <span class="n">board</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">==</span> <span class="n">myPiece</span><span class="p">){</span>
        <span class="n">focus</span> <span class="o">+=</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到棋子前方第二个位置</span>
        <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">&&</span> <span class="n">board</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">==</span> <span class="n">NOPIECE</span><span class="p">){</span>
          <span class="n">focus</span> <span class="o">=</span> <span class="n">to</span> <span class="o">-</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到吃子位置</span>
          <span class="n">delPiece</span><span class="p">(</span><span class="n">focus</span><span class="p">);</span> <span class="c1">//吃子</span>
          <span class="n">eatTable</span><span class="p">[</span><span class="n">eatCount</span><span class="p">]</span> <span class="o">=</span> <span class="n">focus</span><span class="p">;</span> <span class="c1">//记录吃子的位置</span>
          <span class="n">eatCount</span><span class="o">++</span><span class="p">;</span> <span class="c1">//计数</span>
        <span class="p">}</span>
      <span class="p">}</span>
    <span class="p">}</span>
   
    <span class="c1">//检查是否为第四种吃子情况“_○○●” 所走棋子为序列中的第二个白子</span>
    <span class="n">focus</span> <span class="o">=</span> <span class="n">to</span> <span class="o">-</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到棋子后方位置</span>
    <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">&&</span> <span class="n">board</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">==</span> <span class="n">NOPIECE</span><span class="p">){</span>
      <span class="n">focus</span> <span class="o">=</span> <span class="n">to</span> <span class="o">+</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到棋子前方第一个位置</span>
      <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">&&</span> <span class="n">board</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">==</span> <span class="n">myPiece</span><span class="p">){</span>
        <span class="n">focus</span> <span class="o">+=</span> <span class="n">step</span><span class="p">;</span> <span class="c1">//把焦点移到棋子前方第二个位置</span>
        <span class="k">if</span><span class="p">(</span><span class="n">inBoard</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">&&</span> <span class="n">board</span><span class="p">[</span><span class="n">focus</span><span class="p">]</span> <span class="o">==</span> <span class="n">oppPiece</span><span class="p">){</span>
          <span class="n">focus</span> <span class="o">=</span> <span class="n">focus</span><span class="p">;</span> <span class="c1">//焦点已经在吃子位置</span>
          <span class="n">delPiece</span><span class="p">(</span><span class="n">focus</span><span class="p">);</span> <span class="c1">//吃子</span>
          <span class="n">eatTable</span><span class="p">[</span><span class="n">eatCount</span><span class="p">]</span> <span class="o">=</span> <span class="n">focus</span><span class="p">;</span> <span class="c1">//记录吃子的位置</span>
          <span class="n">eatCount</span><span class="o">++</span><span class="p">;</span> <span class="c1">//计数</span>
        <span class="p">}</span>
      <span class="p">}</span>
    <span class="p">}</span>
   
  <span class="p">}</span>
  
  <span class="c1">//5.交换走棋方</span>
  <span class="n">changePlayer</span><span class="p">();</span>
  
  <span class="k">return</span> <span class="mi">1</span> <span class="o">+</span> <span class="n">eatCount</span><span class="p">;</span> <span class="c1">//返回吃子的个数加1，我们调用此函数时，只需要用返回值减1就得到吃子个数</span>
<span class="p">}</span>

<span class="cm">/*************************************************************</span>
<span class="cm">* = 第三节  局面评估 =</span>
<span class="cm">*</span>
<span class="cm">* 3.1 判断胜负</span>
<span class="cm">*</span>
<span class="cm">* 有了能生成局面上所有能走的棋的函数，程序就能知道哪些棋可以走，哪些棋不能走。 </span>
<span class="cm">* 现在为了完善规则，我们还差一个判断胜负的函数了。已知一个局面，是否已经分出</span>
<span class="cm">* 胜负呢？看下面函数。</span>
<span class="cm">* </span>
<span class="cm">* (1)需要写一个判断胜负的函数。</span>
<span class="cm">*/</span>

<span class="c1">//判断是否分出胜负的函数 </span>
<span class="kt">int</span> <span class="nf">isCurrentPlayerDie</span><span class="p">(){</span>
  
  <span class="c1">//如果生成零个走法，则已被困死，将返回1</span>
  <span class="k">if</span><span class="p">(</span><span class="n">generateAllMoves</span><span class="p">(</span><span class="n">theMoves</span><span class="p">)){</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
  <span class="p">}</span>
  <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
<span class="p">}</span>

<span class="cm">/*</span>
<span class="cm">* 3.2 局面评估</span>
<span class="cm">*</span>
<span class="cm">* 局面评估就是量化一个局面的对双方的优劣势，比如一个局面对白方有</span>
<span class="cm">* 利，那么到底有利多少呢？我们需要给这个局面打一个分。</span>
<span class="cm">* </span>
<span class="cm">* 一个局面的优劣，与很多因素有关：双方的棋子，棋子的数目，棋子的</span>
<span class="cm">* 位置，棋子的灵活型，棋子之前的牵制等。</span>
<span class="cm">* </span>
<span class="cm">* 为了简单，本程序只对局面进行最简单的评估，我们设一颗棋子的价值</span>
<span class="cm">* 为3，那么白方棋子的总价值就是3*白方棋子的剩余数。同样黑方的总</span>
<span class="cm">* 价值就是3*黑方棋子的剩余数。</span>
<span class="cm">* </span>
<span class="cm">* 我们可以用 白方棋子的总价值 减去 黑方棋子的总价值 表示一个局面</span>
<span class="cm">* 的价值(评分)，那么对白方来说分数越高越好，对黑方来说，分数越低</span>
<span class="cm">* 越好。对白方来说最好的分数是36，对黑方来说最好的分数是-36，分</span>
<span class="cm">* 数越大，对白方越有利，分数越小对黑方越有利，所以，白方走棋的原</span>
<span class="cm">* 则是使局面的分数变大，而黑方走棋的原则是使局面的分数变小。</span>
<span class="cm">* </span>
<span class="cm">* (1)我们需要一个评估函数来计算一个局面的评分，如下：</span>
<span class="cm">*/</span>

<span class="c1">//局面评估函数 </span>
<span class="kt">int</span> <span class="nf">evaluatePosition</span><span class="p">(){</span>
  <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">whiteValue</span><span class="p">,</span> <span class="n">blackValue</span><span class="p">,</span> <span class="n">value</span><span class="p">;</span>
  
  <span class="c1">//初始化双方的总价值</span>
  <span class="n">whiteValue</span> <span class="o">=</span> <span class="n">blackValue</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
  
  <span class="c1">//遍历棋盘，找到棋子</span>
  <span class="k">for</span><span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"> <span class="mi">64</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span>
    <span class="k">if</span><span class="p">(</span><span class="n">board</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">STONE</span><span class="p">){</span>
      <span class="n">whiteValue</span> <span class="o">+=</span> <span class="mi">3</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">if</span><span class="p">(</span><span class="n">board</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">LEAF</span><span class="p">){</span>
      <span class="n">blackValue</span> <span class="o">+=</span> <span class="mi">3</span><span class="p">;</span>
    <span class="p">}</span>
  <span class="p">}</span>
  
  <span class="c1">//计算局面价值</span>
  <span class="n">value</span> <span class="o">=</span> <span class="n">whiteValue</span> <span class="o">-</span> <span class="n">blackValue</span><span class="p">;</span>
  
  <span class="k">return</span> <span class="n">value</span><span class="p">;</span>
<span class="p">}</span>

<span class="cm">/*************************************************************</span>
<span class="cm">* = 第四节  局面搜索 =</span>
<span class="cm">* </span>
<span class="cm">* 4.1 搜索函数 -- 极小值极大值算法</span>
<span class="cm">* </span>
<span class="cm">* 极小值极大值算法会动态的产生一颗博弈树，这颗树的每一个节点就是一个局面，</span>
<span class="cm">* 它返回最有利于当前走棋方的走法和搜索到的最佳局面的评分。极小值极大值算</span>
<span class="cm">* 法是很多其他博弈搜索算法的基础。</span>
<span class="cm">* </span>
<span class="cm">* 极小值极大值算法的设计思想是轮到双方走棋时，都去寻找最有利与自己的走法</span>
<span class="cm">* 并假设对方也会走出一步好棋。</span>
<span class="cm">* </span>
<span class="cm">* 总之，极小值极大值算法的作用就是从庞大的博弈树中尽可能的找到最有利于当</span>
<span class="cm">* 前走棋方的走法。</span>
<span class="cm">* </span>
<span class="cm">* 在局面搜索的过程中搜索函数会尝试在棋盘上走棋，以取得未来几步的局面。</span>
<span class="cm">* 为了不破坏当前局面，我们还需要一个撤销走一步棋的函数，用来还原局面。</span>
<span class="cm">* </span>
<span class="cm">* (1)我们需要一个变量来保存搜索函数找到的最佳走法 </span>
<span class="cm">  (2)需要一个全局变量来跟踪搜索的当前深度。</span>
<span class="cm">* (3)需要写一个撤销走法的函数 </span>
<span class="cm">* (4)一个极小值极大值搜索函数 </span>
<span class="cm">*/</span>

<span class="cp">#define SEARCH_DEPTH 7 </span><span class="c1">//设置搜索深度</span>
<span class="cp">#define INFINITY_VALUE 100 </span><span class="c1">//设置局面价值无穷大为100，因为局面价值最大为36，</span>
                           <span class="c1">//100不可能达到，所以就相当于无穷大。 </span>

<span class="c1">//最佳走法</span>
<span class="kt">int</span> <span class="n">bestMove</span><span class="p">;</span> 

<span class="c1">//搜索深度</span>
<span class="kt">int</span> <span class="n">theDepth</span><span class="p">;</span> 

<span class="c1">//撤销一步棋的函数 </span>
<span class="kt">void</span> <span class="nf">undoOneMove</span><span class="p">(</span><span class="kt">int</span> <span class="n">move</span><span class="p">,</span> <span class="kt">int</span> <span class="n">eatCount</span><span class="p">,</span> <span class="kt">int</span> <span class="o">*</span><span class="n">eatTable</span><span class="p">){</span>
  <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">from</span><span class="p">,</span> <span class="n">to</span><span class="p">;</span>

  <span class="n">from</span> <span class="o">=</span> <span class="n">generateMoveFrom</span><span class="p">(</span><span class="n">move</span><span class="p">);</span>
  <span class="n">to</span> <span class="o">=</span> <span class="n">generateMoveTo</span><span class="p">(</span><span class="n">move</span><span class="p">);</span>
  
  <span class="c1">//还原被吃的子</span>
  <span class="k">for</span><span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"> <span class="n">eatCount</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span>
    <span class="n">addPiece</span><span class="p">(</span><span class="n">eatTable</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="c1">//添加对方棋子(注意，这时走棋方为对方，添加对方棋子)</span>
  <span class="p">}</span>
  
  <span class="n">changePlayer</span><span class="p">();</span> <span class="c1">//交换走棋方</span>
  <span class="n">delPiece</span><span class="p">(</span><span class="n">to</span><span class="p">);</span>   <span class="c1">//删除棋子</span>
  <span class="n">addPiece</span><span class="p">(</span><span class="n">from</span><span class="p">);</span> <span class="c1">//添加己方棋子</span>
<span class="p">}</span>

<span class="c1">//极小值极大值搜索函数</span>
<span class="kt">int</span> <span class="nf">MinMaxSearch</span><span class="p">(</span><span class="kt">int</span> <span class="n">depth</span><span class="p">){</span> <span class="c1">//depth是搜索博弈树的深度，就相当于能看到将来的多少步棋。 </span>
                             <span class="c1">//因为随着深度的增加，博弈树的节点树呈指数级增长，数据相</span>
                             <span class="c1">//当庞大，所以深度不易太深，一般7层以上PC机算起来就很吃力了。</span>
  <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">genCount</span><span class="p">,</span> <span class="n">value</span><span class="p">,</span> <span class="n">bestValue</span><span class="p">;</span>
  <span class="kt">int</span> <span class="n">allMoves</span><span class="p">[</span><span class="n">MAX_GEN_MOVES</span><span class="p">];</span>
  <span class="kt">int</span> <span class="n">eatCount</span><span class="p">,</span> <span class="n">eatTable</span><span class="p">[</span><span class="mi">2</span><span class="p">];</span> <span class="c1">//还原局面时用</span>
  
  <span class="c1">//如果搜索到指定深度，则返回局面评估值</span>
  <span class="k">if</span><span class="p">(</span><span class="n">depth</span> <span class="o">==</span> <span class="mi">0</span><span class="p">){</span>
    <span class="k">return</span> <span class="n">evaluatePosition</span><span class="p">();</span>
  <span class="p">}</span>

  <span class="c1">//初始化最佳值</span>
  <span class="k">if</span><span class="p">(</span><span class="n">currentPlayer</span><span class="p">){</span>
    <span class="n">bestValue</span> <span class="o">=</span> <span class="n">INFINITY_VALUE</span><span class="p">;</span> <span class="c1">//正无穷</span>
  <span class="p">}</span><span class="k">else</span><span class="p">{</span>
    <span class="n">bestValue</span> <span class="o">=</span> <span class="o">-</span><span class="n">INFINITY_VALUE</span><span class="p">;</span> <span class="c1">//负无穷</span>
  <span class="p">}</span>

  <span class="n">genCount</span> <span class="o">=</span> <span class="n">generateAllMoves</span><span class="p">(</span><span class="n">allMoves</span><span class="p">);</span>
  
  <span class="k">for</span><span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span></span></span></span></span></span></span></span></span></span></span></span></code>Nach dem Login kopieren