Представление игровых состояний в Tic Tac Toe

Question

Цель задания, над которым я сейчас работаю, для моего класса Data Structures - создать Quantum Tic Tac Toe с ИИ, который играет на победу.

В настоящее время у меня возникли проблемы с поиском наиболее эффективного способа представления состояний.

Обзор текущей структуры:

AbstractGame

• Имеет и управляет AbstractPlayers (game.nextPlayer () возвращает следующего игрока по int ID)
• Имеет и инициализирует AbstractBoard в начале игры
• Имеет GameTree (Завершено, если вызывается при инициализации, в противном случае не завершено)

AbstractBoard

• Имеет состояние, измерение и родительскую игру
• Является посредником между игроком и государством (переводит состояния из наборов строк в представление Point
• является государственным потребителем

AbstractPlayer

• является государственным производителем
• Имеет ConcreteEvaluationStrategy для оценки текущей платы

StateTransveralPool

• Предварительно вычисляет возможные трансверсалы "3-х состояний".
• Хранит их в HashMap, где Набор содержит следующие состояния для данного "3-состояния"

Штат

• Содержит 3 комплекта - набор X-ходов, O-ходов и доски
• Каждое целое число в наборе является строкой. Эти целочисленные значения можно использовать для получения следующего состояния строки из 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. Если у меня есть игрок Max (x) с доской {R1, R2, R3}, то получить следующие состояния строк для R1, R2 и R3 просто ..

Set<Integer> R1nextStates = StateTransversalPool.get(R1); 

Проблема в том, что мне нужно объединить каждое из этих состояний с R1 и R2.

Есть ли лучшая структура данных, кроме Set, которую я мог бы использовать? Есть ли более эффективный подход в целом? Я также нашел пункт <-> посредничество государства громоздким. Есть ли другой подход, который я мог бы попробовать там?

Спасибо!

Вот код для моего класса 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 и перехожу к квантовому TTT. Учитывая структуру, это должно быть так же просто, как создать несколько новых классов бетона и настроить некоторые вещи.

Answer 1

Мое предложение:

• Рассмотрите возможность представления отдельных квадратов, а не рядов, поэтому +1 == O, -1 == X и 0 подразумевают пустой квадрат. Это позволяет вам определять конечное состояние , проверяя, равна ли сумма горизонтальной, вертикальной или диагональной строки +3 или -3.
• Во-вторых, "свести" эту 2D матрицу 3x3 в один массив, в котором элементы [0-2] представляют первую строку, элементы [3-5] представляют вторую строку, а элементы [6-8] представляют третью строку.
• Используйте рекурсию или итеративный подход для генерации последующих игровых состояний с учетом текущего состояния доски.

EDIT

Мне стало скучно, и я решил написать «игрушечный код» для реализации игровой доски, включая методы, чтобы определить, находится ли она в состоянии терминала, и сгенерировать набор состояний доски после того, как будет сделан следующий ход. Следует обобщить на любой размер доски, хотя я не пробовал. Наслаждайтесь ...

Пример вывода

$ 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');
    }
    }
}

Answer 2

Разве у каждого квадрата не должно быть только трех возможных состояний (, X, O)?

Либо сохраняйте сетку из 3-х состояний, либо храните 2 списка ходов. Вам не нужно хранить всю доску, потому что она определяется ходами.

Кроме того, что вы подразумеваете под:

создание следующих состояний для GameTree

Что такое GameTree? и каковы некоторые примеры "следующих состояний"?