做个简单的黑白棋(1)
发表于 2006-02-02 11:31 AM 作者: cat
非常简单。这回弄点核心的类，下回弄UI. 就这破东西能应付我们大学一门课了.
首先做个Board类，我的这个类似乎肥了点，不管这么多了，实现了吃子（翻转）、历史纪录（Undo, Redo）以及取得一些盘面信息等功能。
给个接口(java)：
实现起来仔细一点即可，就putStone稍微繁琐一点而已。只是娱乐一下也不必太讲究效率 
然后定义一个Player接口：
然后写个AI:
用了个简单的alpha-beta裁剪：
伪代码如下：
这里稍微有点麻烦的就是game end的处理，具体实现如下：
这个类还没完，里面还有一个函数：staticEvaluate, 这里做了个很简单的：移动力（可以落子的地方）和边角，效率很低。（其实边角这两个feature完全可以合在一起，用一个棋盘的bitmap来搞，这里就naive到底了）其中countMobility就是数一下color0一方可以走的格子比对方多几个，countEdge数一下边上多几个， countCorner数一下角上如何。
至此AI也有了，差个Game引擎以及一个UI. 引擎简单：
UI也简单，下回分解个巨土的GUI出来，有兴趣写个简单的Console UI也很方便。
首先做个Board类，我的这个类似乎肥了点，不管这么多了，实现了吃子（翻转）、历史纪录（Undo, Redo）以及取得一些盘面信息等功能。
给个接口(java)：
代码:
package myothello;
public class Board {
public Board();
public int getBlackScore();
public int getWhiteScore();
public int getScore(int color);
public int getStonesOnBoard();
public int getCurrentColor();
public int getCurrentStep();
public boolean isEndOfGame();
public boolean isInBoard(int x, int y);
public int getBoard(int i, int j);
public void setBoard(int i, int j, int v);
public boolean isLegalMove(int x, int y);
public boolean isLegalMove(int x, int y, int color);
public int putStone(int x, int y);
public void pass();
public int getUndoCount();
public int getRedoCount();
public void undo()
public void undo(int n);
public void redo();
public void redo(int n);
} 然后定义一个Player接口：
代码:
package myothello;
public interface Player {
void play(Board board);
int getColor();
} 用了个简单的alpha-beta裁剪：
伪代码如下：
代码:
int evaluate(board, depth, alpha, beta) {
if (depth == 0 || game end)
return static-evaluate(board);
for each valid move p in board {
board.move(p);
value = -evaluate(board, depth-1, -beta, -alpha);
board.unmove(p);
if (value >= beta) return beta;
if (value > alpha) alpha = value;
}
return alpha;
} 代码:
package myothello;
import java.util.*;
public class VirtualPlayer implements Player {
public VirtualPlayer(int color, int depth);
public int getColor();
public void play(Board board) {
synchronized (board) {
bestMove = null;
evaluate(board, -INFINITY, INFINITY, depth, true);
if (bestMove != null) {
board.putStone(bestMove.x, bestMove.y);
} else {
board.pass();
}
}
}
public int evaluate(Board board, int alpha, int beta, int depth, boolean recordBestMove) {
if (depth == 0) return staticEvaluate(board);
--depth;
ArrayList<Point> validMoves = getValidMoves(board);
if (validMoves.size() == 0) {
board.pass();
int score1;
if (hasValidMove(board)) {
score1 = -evaluate(board, -beta, -alpha, depth, false);
} else {
board.pass();
score1 = evaluateEndOfGame(board);
board.undo();
}
board.undo();
return score1;
}
for (Point p : validMoves) {
board.putStone(p.x, p.y);
int value = -evaluate(board, -beta, -alpha, depth, false);
board.undo();
if (value >= beta) return beta;
if (value > alpha) {
alpha = value;
if (recordBestMove) bestMove = p;
}
}
return alpha;
}
private ArrayList<Point> getValidMoves(Board board); 代码:
public static int countMobility(Board board, int color0);
public static int countEdge(Board board, int color0);
public static int countCorner(Board board, int color0);
public int staticEvaluate(Board board) {
int color = board.getCurrentColor();
int mobility = 100 * countMobility(board, color);
int edge = 30 * countEdge(board, color);
int corner = 10000 * countCorner(board, color);
return mobility + edge + corner;
}
public static int evaluateEndOfGame(Board board) {
int color = board.getCurrentColor();
int oppoColor = -color;
if (board.getScore(color) > board.getScore(oppoColor)) {
return INFINITY - 1 - board.getScore(oppoColor);
} else
if (board.getScore(color) < board.getScore(oppoColor)) {
return -INFINITY + 1 + board.getScore(color);
} else {
return 0;
}
}
} 代码:
while (!board.isEndOfGame()) {
showBoard(board);
getPlayer(currentColor).play(board);
} 
评论总数 0
评论
 发表评论 |
作者为 cat 的最新文章
- C# events VS delegates (2006-11-17)
- .net 匿名delegate 可以修改的局部变量 (2006-11-17)
- 做个简单的黑白棋(2) (2006-02-04)
- 做个简单的黑白棋(1) (2006-02-02)
- Stored Procedure (2006-01-28)
