java - 在 Tic Tac Toe 中表示游戏状态

Question

我目前正在为我的数据结构类(class)做的作业的目标是创建一个量子井字游戏，其中包含一个可以获胜的 AI。

目前，我在寻找表示状态的最有效方法时遇到了一些麻烦。

当前结构概述:

抽象游戏

• 拥有并管理 AbstractPlayers(game.nextPlayer() 通过 int ID 返回下一个玩家)
• 在游戏开始时拥有并初始化 AbstractBoard
• 有一个 GameTree(如果在初始化时调用则完整，否则不完整)

抽象板

• 有状态、维度和父游戏
• 是 Player 和 State 之间的中介，(将 States 从行集合转换为 Point 表示
• 是一个 StateConsumer

抽象播放器

• 是国家生产商
• 有一个 ConcreteEvaluationStrategy 来评估当前的董事会

状态横向池

• 预先计算“三态”的可能横截面。
• 将它们存储在 HashMap 中，其中 Set 包含给定“三态”的 nextState

状态

• 包含 3 组——一组 X-Moves、O-Moves 和棋盘
• 集合中的每个整数都是一行。这些整数值可用于从 StateTransversalPool 获取下一个行状态

SO，原理是每行可以用二进制数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} => board{R1,R2,R3}

问题是快速生成 GameTree 的下一个状态。如果我有玩家 Max (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。鉴于框架，它应该像创建几个新的具体类和调整一些东西一样简单。

Answer 1

我的建议:

• 考虑表示单个方 block 而不是行，其中 +1 == O、-1 == X 和 0 表示空方 block . 这允许您通过检查水平、垂直或对角线行的总和是否等于 +3 或 -3 来检测结束状态。
• 然后将这个 2D 3x3 矩阵“扁平化”为一个数组，其中元素 [0-2] 代表第一行，元素 [3-5] 代表第二行，元素 [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');
    }
    }
}