我目前正在为我的数据结构课程进行的作业的目标是创建一个具有赢得胜利的AI的Quantic Tic Tac Toe.
目前,我在寻找最有效的状态表示方法时遇到了一些麻烦.
当前结构概述：
抽象游戏
>具有并管理AbstractPlayers(game.nextPlayer()通过int ID返回下一个玩家)
>在游戏开始时拥有并初始化AbstractBoard
>带有GameTree(如果在初始化中调用则完成,否则完成)
抽象板
>具有状态,维度和父游戏
>是播放器和状态之间的中介,(将状态从行集合转换为点表示)
>是StateConsumer
抽象播放器
>是国家生产者
>具有具体的评估策略来评估当前董事会
StateTransveralPool
>预计算“三态”的可能横向.
>将它们存储在HashMap中,在其中Set包含给定“三态”的nextStates
州
>包含3组-一组X-Moves,O-Moves和棋盘
>集合中的每个整数都是一个行.这些Integer值可用于从StateTransversalPool获取下一个行状态
所以,原理是
每行都可以用二进制数000-111表示,其中0表示开放空间,而1表示封闭空间.
因此,对于不完整的TTT板：
From the Set<Integer> board perspective:
X_X R1 might be: 101
OO_ R2 might be: 110
X_X R3 might be: 101, where 1 is an open space, and 0 is a closed space
From the Set<Integer> xMoves perspective:
X_X R1 might be: 101
OO_ R2 might be: 000
X_X R3 might be: 101, where 1 is an X and 0 is not
From the Set<Integer> oMoves perspective:
X_X R1 might be: 000
OO_ R2 might be: 110
X_X R3 might be: 000, where 1 is an O and 0 is not
然后我们看到x {R1,R2,R3}& o {R1,R2,R3} =>板{R1,R2,R3}
问题很快为GameTree生成了下一个状态.如果我的玩家最大(x)与板子{R1,R2,R3},那么获得R1,R2和R3的下一个行状态很简单.
Set<Integer> R1nextStates = StateTransversalPool.get(R1);
问题是我必须将这些状态中的每一个与R1和R2结合在一起.
除了Set我可以使用更好的数据结构吗？通常有没有更有效的方法？我还发现Point-State调解很麻烦.我可以在那里尝试另一种方法吗？
谢谢！
这是我的ConcretePlayer类的代码.它可能有助于说明玩家如何使用StateProducer(可能需要成为StateFactory或StateBuilder)通过移动来产生新状态.
public class ConcretePlayerGeneric extends AbstractPlayer {
@Override
public BinaryState makeMove() {
// Given a move and the current state, produce a new state
Point playerMove = super.strategy.evaluate(this);
BinaryState currentState = super.getInGame().getBoard().getState();
return StateProducer.getState(this, playerMove, currentState);
}
}
编辑：我从普通的TTT开始,然后转到Quantum TTT.给定框架,它应该像创建几个新的Concrete类并进行一些调整一样简单.
解决方法:
我的建议：
>考虑代表单个正方形而不是行,其中1 == O,-1 == X,0表示一个空正方形.这使您可以通过检查水平,垂直或对角线行的总和等于3或-3来检测结束状态.
>其次,将该2D 3×3矩阵“展平”为单个数组,其中element [0-2]代表第一行,element [3-5]代表第二行,element [6-8]代表第三行.
>在给定棋盘当前状态的情况下,使用递归或迭代方法生成后续游戏状态.
编辑
我很无聊,因此决定编写一些“玩具代码”来实现游戏板,包括确定游戏板是否处于终端状态并在下一步行动后生成游戏板状态集的方法.尽管我还没有尝试过,但它应该适用于任何规模的董事会.请享用 …
样本输出
$java Board
Creating board:
---
---
---
Initialising board:
-OX
O--
XO-
Terminal state: false
Generating next move states:
XOX
O--
XO-
-OX
OX-
XO-
-OX
O-X
XO-
-OX
O--
XOX
码
import java.util.List;
import java.util.LinkedList;
import java.util.Random;
public class Board {
private final int[] squares;
public Board() {
this.squares = new int[9];
}
protected Board(int[] squares) {
this.squares = squares;
}
public void init() {
Random rnd = new Random();
int turn = 1; // 'O' always goes first.
for (int i=0; i<squares.length; ++i) {
double d = rnd.nextDouble();
if (d < 0.75) {
squares[i] = turn;
turn = turn == 1 ? -1 : 1; // Flip to other player's turn.
} else {
squares[i] = 0; // Empty square.
}
if (isTerminalState()) {
break;
}
}
}
public boolean isTerminalState() {
boolean ret = false;
boolean foundEmpty = false;
int hSum = 0;
int[] vSum = new int[3];
for (int i=0; i<squares.length; ++i) {
hSum += squares[i];
if (isWinningRow(hSum)) {
ret = true;
break;
} else if (i == 2 || i == 5) {
hSum = 0;
}
int col = i % 3;
vSum[col] += squares[i];
if (isWinningRow(vSum[col])) {
ret = true;
break;
}
if (squares[i] == 0) {
foundEmpty = true;
}
}
if (!ret) {
if (!foundEmpty) {
ret = true;
} else {
int diag1 = 0;
int diag2 = 0;
int rowSz = (int)Math.sqrt(squares.length);
for (int i=0; i<squares.length; ++i) {
if (i % (rowSz + 1) == 0) {
diag1 += squares[i];
if (isWinningRow(diag1)) {
ret = true;
break;
}
}
if (i > 0 && i % (rowSz - 1) == 0) {
diag2 += squares[i];
if (isWinningRow(diag2)) {
ret = true;
break;
}
}
}
}
}
return ret;
}
private boolean isWinningRow(int rowSum) {
return rowSum == 3 || rowSum == -3;
}
public List<Board> getNextStates() {
List<Board> ret = new LinkedList<Board>();
int tmp = 0;
for (int i=0; i<squares.length; ++i) {
tmp += squares[i];
}
// Next turn is 'O' (i.e. +1) if the board sums to 0.
// Otherwise it's 'X's turn.
int turn = tmp == 0 ? 1 : -1;
if (!isTerminalState()) {
for (int i=0; i<squares.length; ++i) {
if (squares[i] == 0) { // Empty square
int[] squaresA = new int[squares.length];
System.arraycopy(squares, 0, squaresA, 0, squares.length);
squaresA[i] = turn;
ret.add(new Board(squaresA));
}
}
}
return ret;
}
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i=0; i<squares.length; ++i) {
if (squares[i] == 1) {
sb.append('O');
} else if (squares[i] == -1) {
sb.append('X');
} else {
assert squares[i] == 0;
sb.append('-');
}
if (i == 2 || i == 5) {
sb.append('\n');
}
}
return sb.toString();
}
public static void main(String[] args) {
System.err.println("Creating board:\n");
Board bd = new Board();
System.err.println(bd);
System.err.println("\nInitialising board:\n");
bd.init();
System.err.println(bd);
System.err.println("Terminal state: " + bd.isTerminalState() + '\n');
System.err.println("\nGenerating next move states:\n");
List<Board> nextStates = bd.getNextStates();
for (Board bd1 : nextStates) {
System.err.println(bd1.toString() + '\n');
}
}
}