c4droid吧 关注：42,765贴子：262,837
不感兴趣
开通SVIP免广告
先介绍一下这个AI的大体框架：
1.局势评价函数
局势评价函数的任务就是对于给定的局面，计算出这个局面的分值。局面越有利，分值越高，局面越不利，分值越低。
显然，五子棋可能的局面数非常多，是不可能穷举的，要构造出一个好的局面评价函数并不容易。
我的方案如上图所示：先统计出棋盘上黑白方各棋型的数量，再根据统计结果给出评分。
2.搜索策略
有了局面评价函数，怎么得到最佳的落子点呢？
最简单的方法可以这样：对于当前棋盘上所有的空点，分别计算在各点处落子后的局面的评分值，找出落之后评分最高的那个点，就是AI下一步要落子的点。
上述方法是一种贪婪算法，它只考虑了一步以后的局势，十分短视。
(理论上，只要局面评价函数足够理想，贪婪法也可以是无懈可击的。而实际上，要构造一个理想的评价函数几乎不可能，贪婪法的效果并不好)
为了解决贪婪法短视的问题，应该往后考虑多步，使用minmax搜索算法。可是这又带来一个大问题：搜索的局面数关于搜索的步数指数增长。在minmax搜索的基础上使用alphabeta剪枝可以显著减少不必要的搜索数量。（具体有多显著？以我之前写的那个AI为例：不使用alphabeta剪枝时大概只能搜索6步，使用alphabeta剪枝后可以搜索12步）
搜索12步就够了吗？并不够。进一步压榨AI性能的方法有：迭代加深，hash表，等等
这里就不一一介绍了
1.局势评价函数
局势评价函数的任务就是对于给定的局面，计算出这个局面的分值。局面越有利，分值越高，局面越不利，分值越低。
显然，五子棋可能的局面数非常多，是不可能穷举的，要构造出一个好的局面评价函数并不容易。
我的方案如上图所示：先统计出棋盘上黑白方各棋型的数量，再根据统计结果给出评分。
2.搜索策略
有了局面评价函数，怎么得到最佳的落子点呢？
最简单的方法可以这样：对于当前棋盘上所有的空点，分别计算在各点处落子后的局面的评分值，找出落之后评分最高的那个点，就是AI下一步要落子的点。
上述方法是一种贪婪算法，它只考虑了一步以后的局势，十分短视。
(理论上，只要局面评价函数足够理想，贪婪法也可以是无懈可击的。而实际上，要构造一个理想的评价函数几乎不可能，贪婪法的效果并不好)
为了解决贪婪法短视的问题，应该往后考虑多步，使用minmax搜索算法。可是这又带来一个大问题：搜索的局面数关于搜索的步数指数增长。在minmax搜索的基础上使用alphabeta剪枝可以显著减少不必要的搜索数量。（具体有多显著？以我之前写的那个AI为例：不使用alphabeta剪枝时大概只能搜索6步，使用alphabeta剪枝后可以搜索12步）
搜索12步就够了吗？并不够。进一步压榨AI性能的方法有：迭代加深，hash表，等等
这里就不一一介绍了
不感兴趣
开通SVIP免广告
到现在为止，这个棋型统计器使用了 “查表大法” 和 “位运算大法” 加速，性能已经做到极致了
吗？
还是图样，速度还能再快10倍：
下五子棋的时候，每一步只落一个子，落子前和落子后的棋盘仅仅是落子点所在的行，列，斜列发生了变化，而其它行列完全没变。
只要记下棋盘每一行每一列的棋型，落子后只需要重新扫描落子点所在的行，列，斜列，而不用扫描整个棋盘，工作量一下子就降到了之前的1/15
于是棋盘的存储结构就变成了这样：
Ntype是棋型的种类数，我一共定义了16种不同的棋型，所以它等于16
现在，这个棋盘结构看起来有点臃肿了。
我试图把它压缩，写成这样：
能进一步压缩吗？
计算一下，每一行或列或斜列上最多可能有多少个棋型？由于一行的长度是15，扫描框的长度是6，所以扫描框在一行上可以扫10个不同的位置，最多产生10个棋型，表示0到10至少需要4个bit，一共16种棋型，需要64个bit。 所以，一个64位的int就能表示某一行或列或斜列上各棋型的数量了。
吗？
还是图样，速度还能再快10倍：
下五子棋的时候，每一步只落一个子，落子前和落子后的棋盘仅仅是落子点所在的行，列，斜列发生了变化，而其它行列完全没变。
只要记下棋盘每一行每一列的棋型，落子后只需要重新扫描落子点所在的行，列，斜列，而不用扫描整个棋盘，工作量一下子就降到了之前的1/15
于是棋盘的存储结构就变成了这样：
Ntype是棋型的种类数，我一共定义了16种不同的棋型，所以它等于16
现在，这个棋盘结构看起来有点臃肿了。
我试图把它压缩，写成这样：
能进一步压缩吗？
计算一下，每一行或列或斜列上最多可能有多少个棋型？由于一行的长度是15，扫描框的长度是6，所以扫描框在一行上可以扫10个不同的位置，最多产生10个棋型，表示0到10至少需要4个bit，一共16种棋型，需要64个bit。 所以，一个64位的int就能表示某一行或列或斜列上各棋型的数量了。
几张图理清结构体中 row[15], column[15], right[19], left[19], 与棋盘位图之间的关系：
给出棋子的坐标，通过变换即可求出该棋子在 row[15], column[15], right[19], left[19],
中的位置：
假设棋子坐标为 ( x, y )
则其在 row[15] 中的位置为 ( row[x] >> 2*y ) & 3
在 column[15] 中的位置为 ( column[y] >> 2*x ) & 3
令 int p = x + y - 5;
若 p>=0 && p<19
则其在 right[15] 中的位置为 ( right[p] << ( p<10 ? 2*y : 28-2*x ) ) & 3
令 int p = x - y + 9;
若 p>=0 && p<19
则其在 left[19] 中的位置为 ( left[p] << ( p<10 ? 2*x : 2*y ) ) & 3
之前的落子函数先将要落子的位置清空，再对其赋值，而大多数情况下要落子的点是空点。
为了提高运行效率，将之前的落子函数拆分成撤子和落子两个函数：
给出棋子的坐标，通过变换即可求出该棋子在 row[15], column[15], right[19], left[19],
中的位置：
假设棋子坐标为 ( x, y )
则其在 row[15] 中的位置为 ( row[x] >> 2*y ) & 3
在 column[15] 中的位置为 ( column[y] >> 2*x ) & 3
令 int p = x + y - 5;
若 p>=0 && p<19
则其在 right[15] 中的位置为 ( right[p] << ( p<10 ? 2*y : 28-2*x ) ) & 3
令 int p = x - y + 9;
若 p>=0 && p<19
则其在 left[19] 中的位置为 ( left[p] << ( p<10 ? 2*x : 2*y ) ) & 3
之前的落子函数先将要落子的位置清空，再对其赋值，而大多数情况下要落子的点是空点。
为了提高运行效率，将之前的落子函数拆分成撤子和落子两个函数：
不感兴趣
开通SVIP免广告
