中国象棋人机对战
走棋
各棋子的走法规则
吃子
AI走棋
赢棋、输棋
悔棋、重玩
切换皮肤、棋阵、级别
学习五子棋,引入连接,改造成在线对弈模式
UI
一个空canvas,挂载时进行初始化。
$v.F5变化时重新挂载。切换皮肤、棋阵、级别,重玩都是改变某个设置后改变$v.F5的值卸载后重新初始化的。
在$c.obj.ui
里预设了3种UI样式,根据其预设图片位置通过new $w.Image()
生成所有棋子及着点、外框、棋盘的图片。只有图片加载完成了才能进行桌布的绘制,所以在最后一个图片的onload
函数里调用$c.exp.绘制
。棋阵
根据设置从$c.obj.棋阵
克隆一个到$v.棋阵
。棋子
$c.exp.摆棋子
中根据其在棋阵中的位置生成各个棋子。估值
各棋子在棋阵中不同位置的估值,是AI走棋的依据。$c.obj.估值
预设了红子的估值,把它位置颠倒一下就成了黑子的估值。颠倒前要记得clone哦。走法
在AI走棋时会大量计算各种走法的估值,走法函数被调用的次数非常多。瞬间被海量调用的函数应该优先考虑原生代码而非表达式以提高速度,所以把它放在$c.js.走法
中。$w.AI
我们把AI算法相关的放在window.AI下以方便调用。
如果是在开发模式下的F12(开发者工具里)下查看,记得把window从top
切换到zc
。
画布上添加有click事件监听器,根据点击位置计算出其在棋盘中的x、y轴。
如果点击的是我方棋子则执行【选子】动作
给已选棋子添加外框
根据已选棋子在棋阵中的位置执行走法计算得出其所有着点
重绘及播放声音如果点击的是对方棋子且在上次已选棋子的着点上则执行【吃子】动作
把走棋路径推入【历史】中,并把两个棋子的位置添加外框
删除原棋子在棋阵中的位置并把新位置换成我方棋子
删除被吃棋子并并原已选棋子的位置挪到新位置
重绘及播放声音
如果被吃的是【将】则结束
稍等片刻后开始【AI走棋】如果点击的不是棋子但是在已选棋子的着点上则执行【落子】动作
类似【吃子】动作悔棋
就是重置整个棋阵棋子,根据【历史】的足迹重走一遍,直到最后两步
走到最后一步时添加外框
执行原生代码的【$w.AI.走棋】得到AI认为的最佳着点
如果没得到着点则AI已被将死
如果着点上是我方棋子则执行【AI吃子】,否则执行【AI落子】
AI搜索算法(选学内容)
极大极小搜索
圆形节点为红方走棋的局面,方形节点为黑方走棋局面,红色数字为局面估值(也就是红方的优势)。深度优先遍历这个搜索树。
初始局面为A,该红方走棋。红方有B1、B2、B3三种走法。
假设红方选择第一种走法,走到了局面B1。
在局面B1,该黑方走棋。黑方有C1、C2、C3三种走法。
C1、C2、C3是叶子节点,调用局面评估函数,算得局面估值(也就是红方优势)分别是8、10、15。
回到局面B1,此时该黑方走棋。黑方后完后,红方优势越小,对黑方越有利。黑方自然会走到对自己最有利的C1局面。此时我们认为,B1局面的估值是8。
同样的方法,B2、B3的估值分别是5、10。
回到初始局面A,红方走棋。现在已经知道,选择第一种走法,最终估值为8;选择第二种走法,最终估值为5;选择第三种走法,最终估值为10。估值就是红方的优势,红方自然会选择对自己优势最大的走法,也就是走到局面B3。
可知行棋路线为A -> B3 -> C7。
A点选择估值最大的局面,称为极大点;B1、B2、B3选择估值最小的局面,称为极小点。
Alpha-Beta搜索
叶子节点(depth == 0),调用评估函数并返回分值
当前局面全部走法
在根节点,Alpha取负无穷,Beta取正无穷。当函数递归时,Alpha和Beta不但取负数而且要交换位置。Alpha表示当前搜索节点走棋一方搜索到的最好值,任何比它小的值对当前节点走棋方都没有意义。Beta表示对手目前的劣势,这是对手所能承受的最坏结果。Beta值越大,表示对方劣势越明显;Beta值越小,表示对方劣势也越小。在对手看来,他总是希望找到一个对策不比Beta更坏。如果当前节点返回Beta或比Beta更好的值,作为父节点的对方就绝不会选择这种策略。