在高二时，曾经尝试做过一个人机对战的五子棋，但是那时做出的电脑方，只会根据当前局势进行打分然后下子，棋力甚至不及一个没有研究过五子棋的普通人。因此，我打算对此进行改进。
极大极小值搜索
当在玩一些交替下子的棋类游戏时，一般在轮到自己下子时，都会去考虑如果下到这个位置上，在往后的几步中是否可以缩小对手的优势而提高自己的优势，对于资深的玩家来说，可以往后考虑的步数也就越多，棋力就越强。
当轮到某一方进行下子时，都会有一些合法的位置可供下子，当选择了某个位置下子后，对手也会有若干合法位置可以下子，这样的一个循环过程，就可以抽象成一棵博弈树。假如电脑是先手，那么奇数层就是电脑的走法，偶数层是玩家的走法，对于五子棋来说这棵博弈树实在太大了，根本无法穷尽，因此到了一定的层数就应该使用一个评估函数评估当前的局势，评估分数越大对电脑越有利，越小对玩家越有利。因此，轮到电脑走子的一层被称为MAX层，应该选择得分最大的结点，轮到玩家走子的一层被称为MIN层，应该选择得分最小的结点。
alpha-beta剪枝
在极大极小值搜素中，其实有很多结点都是不必进行搜索的。
直观来看就是某策略的后续走法比之前策略的还差时，就会停止搜索该策略的后续结点，因此便节约了大量的时间，但是最终的得到的结果跟极大极小值搜素是一致的，是一个无害的剪枝方法。
为了实现这个思想，在搜索的时候引入了 α、 β两个参数。 α表示在MAX层中取得的最大值，是一个下限，而 表示在MIN层中取得的最小值，β是一个上限。如果在MIN层中搜索到了一个比α还小的值，那么便可进行剪枝，因为这对于上一层的MAX层来说是一个比之前策略还差的走法，是不可能会被选择的。如果在MAX层中搜索到了一个比β还大的值，也可进行剪枝，因为这对于上一层的MIN层来说，是一个不能最小化对手利益的走法。
棋盘表示与更新
一般的五子棋棋盘表示会用一个一维或二位数组表示，然后0代表空，1代表黑棋，2代表白棋。但是在某些时候并不会去关心这个棋子是什么颜色，只会去关心是否有棋子，例如在生成走法的时候。
这时，每一行每一列都可以用一个二进制数表示，0代表空、1代表非空，对于五子棋还需增加一个斜线方向，斜线方向又分为正斜与反斜。 而对于局势评估时，就会去关心这个棋子究竟是什么颜色，因此每一行每一列每一条斜线都可用三进制数来表示，0代表空、1代表黑子、2代表白子。
走法生成
实际上，棋盘上空的位置都是合法的下子位置，但是不可能将所有的位置都纳入搜索的范围，这会让博弈树过于庞大，其实很多位置大概率都不会有很高的价值，例如四周很大范围内都没有棋子。
因此，可以做出一个规定，若一个位置为空且距离它2格以内有其他已下的棋子，就可以将其纳入到可行走法中。
为了生成可行的走法，一般的想法是循环整个棋盘中的位置，如果为空且它四周2格范围内有其他棋子，就将其放入可行走法表中，但是这样每次都要遍历整个棋盘来寻找，耗费较多的时间。因此转为遍历当前棋盘上所有棋子，将它们四周2格范围内的空位置放入可行走法表。这样可以节约一些时间，但是在棋子数量增多时消耗的时间也就增加了，当棋子数量变多时有一部分的棋子已经被其他棋子围了起来，周围已经没有空位置，但仍需耗费时间去遍历检查。
因此可以预置好一个数组，根据一个棋子所处的位行、位列和斜线，还有分别所处的顺序位置，直接获取它周围2格内的空位置。
评估函数
一个高效而准确的评估函数可以极大地提高电脑的棋力，对于五子棋来说，可以给每一个棋形一定的分数，然后就统计每一个棋形的数量即可。下面列出一个表格，以黑棋为例标出各个棋形的分数。
| 棋形名字 | 棋形 | 分数 |
|---|---|---|
| 连五 | 11111 | 100000 |
| 活四 | 011110 | 10000 |
| 眠四 | 11110 或 01111 | 1000 |
| 跳眠四 | 11011 或 10111 或 11101 | 1000 |
| 活三 | 01110 | 1000 |
| 跳活三 | 010110 或 011010 | 1000 |
| 眠三 | 11100 或 00111 | 100 |
| 活二 | 001100 | 100 |
| 跳活二 | 01010 | 100 |
| 眠二 | 11000 或 00011 | 10 |
| 活一 | 00100 | 10 |
一般的做法，就是在每次评估局势时，都遍历棋盘上所有的棋子，对于每个棋子都遍历行、列、正斜和反斜四个方向，然后统计出现的棋形，这种方法是有缺点的，容易重复统计，并且比较耗费时间。所以，可利用棋盘表示中提到的三进制数表示行、列、正反斜线，分别统计出现的棋形即可。为了进一步提高效率，可以将所有可能的棋子排列对应的分数预置到数组内，评估时直接根据三进制数来取得分数。由于五子棋棋盘为15 × 15，这个三进制数为15位，则最大值是14348906，遍历所有的棋子排列，使用AC自动机统计每一个排列中的棋形数量。
还可用局部刷新的方法进一步提高评估效率，在搜索时储存好每一行、列、正反斜的评估值，因为每下一个子时，只有这个子所处的行、列、正反斜四个方向会发生评估值的变化，所以在下一个子后，就马上更新所处的行、列、正反斜的评估值，得到新的局势评估值，在需要调用评估函数时就无需进行任何计算，直接获得评估值。
走法排序
alpha-beta剪枝的效率取决于结点的排序，当一些更好的走法排在前面时，更加容易引发剪枝，因此在生成走法之后，花费一点时间对每个走法进行大概的评估，是值得的。
可以做出这样的假设，对于某一个空位置，黑方下子后对其是有利的，或者白方下子后对其是有利的，那么这个位置就可能是一个好的下子位置，这里所述的“有利”可指成活三、活四甚至连五等高价值棋形。因此，需要量化这里说的“有利”，使排序变得可行。自然可想到利用评估函数中的分值来衡量“有利”
设Δval1表示下黑子前后的四个方向总分值差，Δval2表示下白子前后的四个方向总分值差。
val = Δval1 +Δval2
就描述了这个走法对双方的优势和，然后就按的大小对走法进行排序。
迭代加深
假如本来限制最大搜索深度为6，那么进行迭代加深时，就需要先依次进行深度为1,2,3,4,5的搜索，最后进行深度为6的搜索。这样的好处是，如果在较浅的搜索中已经找到了必胜走法，那就可以提前返回，节约了时间，而且浅层的搜索也可以给深层的搜索一些启发。
静态搜索
经过一系列优化之后，可以在几秒内搜索到6层的深度，提升棋力的一个关键就是提高搜索深度，但是深度增加到一定程度就难以再提高了，如果有一个好的走法在较深的层中就无法被搜索到了，这被叫做水平线效应。
为了克服水平线效应，在搜索到设定好的深度后，可以增加一个静态搜索，但是在这个搜索中不搜索全部走法，只去搜索可以产生活三、活四、眠四或堵对手活三、眠四的高估价走法，由于这样的走法较少，所以静态搜索耗费的额外时间较少。
置换表
在搜索过程中，可能会遇到一摸一样的棋局，这时如果有一个表储存了这样的棋局，就可以直接读取分值，而不需要继续进行搜索，这样的表被称为置换表。
为了能用一个整数表示一个棋局，黑、白子对应每个位置都预先产生好了一个64位的随机数，每下一个子，就用这个子所在位置对应的随机数与表示当前棋局的数做一次异或运算，而撤销下子时，由于异或的运算性质，也同样做一次跟下子一样的异或运行即可。这样的表示方法被称为Zobrist键值。
有了这样一个64位整数来表示棋局，将其模上置换表大小即可从置换表中获取分值，这样来看置换表也是一个哈希表，那么是有可能出现哈希冲突的，因此可以增加一个64位校验码，在读取置换表时先对比校验码。
对于同一个局面，它所经过的搜索深度可能是不同的，深度越大可信度也就越高，在存入置换表时就把搜索深度也存入，那么在读取置换表时，如果置换表中的深度比当前深度要大，就可以采用。
本项目在github上进行了开源，地址为：http://github.com/oscarab/Gobang
