Othello翻转棋实战01-翻转棋AI代码实现
1. 作业要求
写一段程序，该程序读取当前的黑白棋棋盘上的棋子布局，并在一定时间内返回在该棋盘布局下对于棋手来说的推荐决策（下一步推荐棋手应该怎么走）。
在程序中，必须实现对棋子布局的表示，类OthelloPosition是来自老师的示例代码，但是并没有完成，需要补全。
最终的程序应该读取目前黑白棋的棋子位置，使用Alpha-Beta搜索和合理的启发式评估，返回推荐的下一步走法。
最简单的方式是构建一个类，这个类实现OthelloAlgorithm这个接口的功能。这个接口含有一个evaluate方法，
可以得到当前的棋子位置和返回OthelloAction下一步推荐走法。
这个接口还有设置启发式评估的方法（通过OthelloEvaluator来实现。）和设置搜索深度的方法。
注意，白棋总是先手，即白棋为Max，黑棋为Min。
作业通过的要求是自己做的简易翻转棋AI要打败老师的搜索深度为7的使用简易启发式的AI！（默认时间限制为5s）
要求： 代码必须使用 Alpha-Beta 搜索和合理的启发式评估。 代码必须能够以黑棋先手和白棋先手两种方式击败老师的AI。必须使用迭代深化搜索，达到时间限制就停止（如果稍微超过时间限制一点也没事儿）。 注意弱的AI程序使用固定的深度7（需要<1s），所以当时间限制增加时它不会增加深度，让它更容易被击败。
黑白棋的简介:百度百科：黑白棋
2.解决方案
- 首先写一个静态评估器，静态评估器可以对当前棋局上的棋子走势进行评估，返回一个得分。
- 设置该静态评估器的启发式，可以使用WPC与行动力的加权和来表示。
- 利用静态评估器，生成博弈树。
- 使用迭代的Alpha-Beta搜索算法进行搜索和剪枝。
- 返回推荐的落子位置。
3. 实现代码
3.1 OthelloAction类
此类表示游戏中的“移动”，即落子。落子由两个整数表示：玩家放置棋子的行和列。
此外，OthelloAction在计算期间可以在其中存储每个落子时对棋盘局势的静态估值。
| 成员变量 | 说明 |
|---|---|
protected int row = -1; |
表示行数，默认为-1 |
protected int column = -1; |
表示列数，默认为-1 |
protected int value = 0; |
表示当前落子决策下的对棋盘局势的静态估值 |
protected boolean pass = false; |
布尔值pass，代表着当前的落子决策是否是跳过 |
| 构造方法 | 说明 |
|---|---|
public OthelloAction(int r, int c) {} |
使用行和列进行带参构造 |
public OthelloAction(int r, int c, boolean p) |
使用行、列以及是否跳过进行带参构造 |
public OthelloAction(String s) {} |
// 字符串构造法。使用“pass”或者读取位置字符串构造。位置字符串例如：（5，6） |
| get/set方法 | 说明 |
|---|---|
public void setValue(int v) {} |
设置估值 |
public int getValue() {} |
得到估值 |
public void setColumn(int c) {} |
设置列数 |
public int getColumn() {} |
得到列数 |
public void setRow(int r) {} |
设置行数 |
public int getRow() {} |
得到行数 |
public void setPassMove(boolean b) {} |
设置pass的布尔值 |
public boolean isPassMove() {} |
得到pass的布尔值 |
| 成员方法 | 说明 |
|---|---|
public void print() {} |
控制台输出当前的落子行数和列数。例如（6，5） |
3.2 OthelloPosition类
一个用来表示游戏中当前棋盘布局的类。棋盘用二维的字符数组表示，使用一个布尔值代表黑方和白方。
| 成员变量 | 说明 |
|---|---|
protected static final int BOARD_SIZE = 8; |
定义棋盘的大小为8 |
protected boolean maxPlayer; |
定义当前是谁该走棋。应该白方走棋时为true |
protected char[][] board; |
定义棋盘的二维字符数组 |
| 构造方法 | 说明 |
|---|---|
public OthelloPosition(){} |
无参构造，生成一个没有棋子的棋盘二维字符数组 |
public OthelloPosition(String s) {} |
使用长度为65的字符串构造生成指定棋盘，字符串第一个字符代表当前棋手，剩下的代表各个位置的棋子 |
| 成员方法 | 说明 |
|---|---|
public void initialize() {} |
在棋盘中间放入两黑两白来初始化棋盘 |
public LinkedList |
返回一个链表，代表当前所有可以落的子的动作。 |
private boolean isMove(int row, int column) {} |
检查当前位置是否满足落子条件 |
private boolean checkNorth(int row, int column) {} |
检查当前位置是否在上方满足落子条件 |
private boolean checkEast(int row, int column) {} |
检查当前位置是否在右方满足落子条件 |
private boolean checkSouth(int row, int column) {} |
检查当前位置在下方是否满足落子条件 |
private boolean checkWest(int row, int column) {} |
检查当前位置在左方是否满足落子条件 |
private boolean checkNorthEast(int row, int column) {} |
检查东北方向，看是否满足落子的条件 |
private boolean checkSouthEast(int row, int column) {} |
检查东南方向，看是否满足落子的条件 |
private boolean checkSouthWest(int row, int column) {} |
检查西南方向，看是否满足落子的条件 |
private boolean checkNorthWest(int row, int column) {} |
检查西北方向，看是否满足落子的条件 |
private boolean isOpponentSquare(int row, int column) {} |
检查当前位置是否已经被对手占了 |
private boolean isOwnSquare(int row, int column) {} |
检查当前位置是否已经被自己占了 |
private boolean isCandidate(int row, int column) {} |
检查当前位置是否为候选位置（没有被占，且相邻位置有子） |
private boolean hasNeighbor(int row, int column) {} |
检查当前位置的相邻位置是否有子 |
private boolean isFree(int row, int column) {} |
检查当前位置是否无子 |
public boolean toMove(){} |
返回当前需要走棋的棋手maxPlayer |
public OthelloPosition makeMove(OthelloAction action) throws IllegalMoveException {} |
返回当前棋手落子后新的棋子局势 |
public char[][] flipPieces(OthelloPosition currentPosition, OthelloAction action, char playerMarker) {} |
按照规则翻转当前棋手落子后的棋盘上的棋子 |
public boolean isIllegalAction(OthelloAction action) {} |
判断该落子是否是合规落子 |
protected OthelloPosition clone() {} |
复制目标棋盘的棋子局势 |
public void illustrate() {} |
控制台可视化当前棋盘与棋子 |
private void printHorizontalBorder() {} |
控制台可视化棋盘的边缘 |
public String toString() {} |
重写了toString方法，返回的是一串65长度的字符串 |
3.3 OthelloEvaluator接口
该接口定义了静态评估器的强制方法，即该类可以通过当前棋局返回一个表示该棋局通过启发式评估而得到的静态评估值（如果当前棋局对白棋更有利，则为正数，反之）。
注意，评估器不应该在“展望未来”的位置上移动，而应该只评估该位置的静态特征。
| 成员方法 | 说明 |
|---|---|
public int evaluate(OthelloPosition position); |
一个对棋局的评估的抽象方法 |
3.4 OthelloAlgorithm接口
此接口定义了在游戏开始后，游戏程序为本轮移动的的玩家返回建议移动的算法。
该算法只定义了搜索方法。对于棋局的静态启发式评估由一个OthelloEvaluator给出。
| 成员方法 | 说明 |
|---|---|
public void setEvaluator(OthelloEvaluator evaluator); |
设置评估器的启发式的抽象方法 |
public OthelloAction evaluate(OthelloPosition position); |
对当前的棋局评估，返回对当前棋手最有利的落子的抽象方法 |
public void setSearchDepth(int depth); |
设置最大搜索深度的抽象方法 |
3.5 IllegalMoveException异常类
当程序做出不符合规则的移动时，抛出这个异常。
| 成员变量 | 说明 |
|---|---|
private OthelloAction action; |
一个OthelloAction类的变量，表示落子 |
| 带参构造 | 说明 |
|---|---|
public IllegalMoveException(OthelloAction a) {} |
出现异常时，将该不合规的移动赋值给action |
| 成员方法 | 说明 |
|---|---|
public OthelloAction getAction() {} |
返回action |
3.6 TimeLimitException异常类
当程序运行时长到了截止时间时，抛出这个异常。
| 无参构造 | 说明 |
|---|---|
public TimeLimitException() {} |
无参构造该异常 |
3.7 StaticEvaluator类
实现了OthelloEvaluator接口，静态评估当前棋局。
| 成员变量 | 说明 |
|---|---|
public static int[][] WPC = **Matrix** |
定义WPC矩阵 |
其中，Matrix是weighted piece counter矩阵，取自知乎上的参考文章。 \(\left\{ \begin{matrix} 500 & -25 & 10 & 5 & 5 & 10 & -25 & 500 \\ -25 & -45 & 1 & 1 & 1 & 1 & -45 & -25 \\ 10 & 1 & 3 & 2 & 2 & 3 & 1 &10 \\ 5 & 1 & 2 & 1 & 1 & 2 & 1 & 5 \\ 5 & 1 & 2 & 1 & 1 & 2 & 1 & 5 \\ 10 & 1 & 3 & 2 & 2 & 3 & 1 &10 \\ -25 & -45 & 1 & 1 & 1 & 1 & -45 & -25 \\ 500 & -25 & 10 & 5 & 5 & 10 & -25 & 500 \\ \end{matrix} \right\}\)
| 成员方法 | 说明 |
|---|---|
public int evaluate(OthelloPosition position) {} |
通过WPC和行动力的加权和来实现对当前棋局的静态评估 |
3.8 DynamicEvaluator类
实现了OthelloAlgorithm接口, 定义了Othello游戏主程序为本轮移动的的玩家返回建议移动的算法。
| 成员变量 | 说明 |
|---|---|
public OthelloEvaluator evaluator; |
表示这个主程序所使用的静态评估器 |
public int depth; |
表示这个主程序的搜索深度 |
public long timeLimit; |
表示这个主程序的搜索时间限制 |
long startTime; |
表示这个主程序运行时刻对应的时间 |
long endTime; |
表示这个主程序运行需要结束的时刻对应的时间 |
| set方法 | 说明 |
|---|---|
public void setTimeLimit(long timeLimit){} |
设置搜索时间限制 |
public void setEvaluator(OthelloEvaluator evaluator) |
设置主程序所使用的静态评估器 |
public void setSearchDepth(int depth) |
设置深度 |
| 成员方法 | 说明 |
|---|---|
public static boolean isFinish(OthelloPosition position){} |
（测试程序用） 判断游戏是否结束，即是否所有位置都被棋子占据 |
public void AIvsAI(OthelloPosition position, DynamicEvaluator dynamicEvaluator){} |
（测试程序用） 让程序自己和自己下棋，检查程序能否正常运行 |
public void Start(OthelloPosition position, DynamicEvaluator dynamicEvaluator){} |
运行主程序，返回当前布局最佳的落子 |
public OthelloAction MaxValue(OthelloPosition position, double alpha, double beta, int depth) throws IllegalMoveException, TimeLimitException {} |
Alpha-Beta算法中的Max |
public OthelloAction MinValue(OthelloPosition position, double alpha, double beta, int depth) throws IllegalMoveException, TimeLimitException {} |
Alpha-Beta算法中的Min |
public OthelloAction AlphaBeta(OthelloPosition position,int depth) throws IllegalMoveException {} |
Alpha-Beta算法 |
public OthelloAction evaluate(OthelloPosition position){} |
返回当前布局最佳的落子 |
4. 结果
结果:以执黑为例，赢了老师的AI一共10个子。
