26
第6-3课：博弈树与井字棋（Tic-Tac-Toe）
source link: https://blog.csdn.net/orbit/article/details/108729344
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
第6-3课：博弈树与井字棋（Tic-Tac-Toe）
上一课简单介绍了博弈树，从编程实现算法的角度看，博弈树是三种树中最简单的一种，无论是原理还是实现都不复杂。这一课，我们就以简单的井字棋（Tic-Tac-Toe）游戏为例，介绍一下如何用博弈树实现一个简单的井字棋 AI，最后的结果并不复杂，我希望大家把关注点放在如何设计数据模型、如何确定落子，以及将博弈树的理论应用到具体的问题等这样的过程上，而不是最后的结果。
Tic-Tac-Toe——规则简单的博弈
小时候，我不知道这游戏的真名是 Tic-Tac-Toe，只知道无聊的时候，和小伙伴们找块沙地，用小树枝画个井字就可以玩半天。井字棋总体来说没什么难度，只要稍微动动脑，两个人玩基本上都是平局，现在想想也没啥意思，但正因为井字棋规则非常简单，所以适合用来做博弈树算法讲解的例子。
这一课的重点依然是实现过程，也就是说如何将博弈树的理论应用到一个简单的游戏实现中，将上一课介绍的算法伪代码翻译成具体的算法实现。
棋盘与棋子的数学模型
井字棋游戏的棋盘类似一个 3 × 3 的九宫格形状，直观上很容易想到用一个 3 × 3 的二维数组表示棋盘，二维数组每个元素的值代表棋盘上对应位置的状态，有三种，分别是空、O 型棋子或 X 型棋子。使用二维数组的好处是数据访问比较直观，二维数组的两个下标可以直接表示棋子的位置，但缺点也很明显，首先是遍历棋盘需要用两重循环处理两个下标，其次是行、列以及斜线方向上都要做是否满足三点连线的判断，根据行、列和斜线的下标变化特点，需要用几套不同的方法处理。
我之前多次说过，很多高效的棋类游戏都用一维数组建模，这一课用井字棋游戏
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK