Крестики-нолики: как заполнить дерево решений?

Question

Я делаю программу Tic-Tac-Toe. Я планирую использовать минимакс с ним. Я создал дерево с местом для всех возможных последовательностей игр, и я ищу способ его заполнить. В настоящее время у меня есть этот тип:

typedef struct name
{
    char grid [3] [3];
    struct name * child [9];
} node;

и я ищу способ заполнить сетку так, как показано здесь . Как бы я заполнил сетку, чтобы убедиться, что все возможные комбинации существуют? Мой план состоит в том, чтобы игра распознавала каждый ход, который может сделать игрок, а затем решала, какие шаги предпринять, чтобы выиграть (мне все еще нужно выяснить часть решения, но я держу это до тех пор, пока не заполню решетки в дереве) .

Answer 1

Звучит как главный кандидат на рекурсию для меня ...

Answer 2

Кодировать позиции в базе 3. Сделать неиспользованную сетку 0; сетка с "X" a 1; и сетка с "O" a 2. Таким образом, абсолютное максимальное количество полных сеток, которое вы можете иметь, составляет 3 ^ 9 = 19683 (некоторые из них являются недопустимыми представлениями крестики-нолики)

Допустим, вы имеете дело с '020112021'. Его дети:

020112021 /* father */ (4759 base 10)
=========
020112022                 father + 1 (1 base 3)
0201120x1 /* invalid */   father + 3 (10 base 3)
020112121                 father + 9 (100 base 3)
02011x021 /* invalid */   father + 27 (1000 base 3)
020122021                 father + 81 (10000 base 3)
020212021                 father + 243
021112021                 father + 729
0x0112021 /* invalid */   father + 2187
120112021                 father + 6561 (100000000 base 3)

Я думаю, вы можете найти способ продолжить отсюда.

Answer 3

детская игра.

РЕДАКТИРОВАТЬ: На случай, если вышеупомянутая ссылка не работает, это ссылка на описание компьютера Tinkertoy от Scientific American October 1989,также составлено и опубликовано вместе с другими развлекательными статьями SA того же автора, что и Компьютер Tinkertoy и другие махинации .Парни (и девочки), которые построили эту машину, были достаточно умны, чтобы избежать любого альфа-бета-поиска, а также сжать доску во что-то, что можно легко вычислить.Тинкертойс.

Answer 4

Псевдокод, потому что рекурсию трудно превратить в список:

function descend(X_or_O, board)
    for square in board
        If square isn't empty: continue
        new_board = Fill in square with X_or_O.
        Check for a winner (if yes, return)
        newer_board = descend(opposite of X_or_O, new_board)
        tack newer_board onto the tree.
        clear out square

Это можно сделать с помощью пары for циклов и if операторов.

Answer 5

Это классический случай для рекурсии:

typedef struct name
{
    char grid [3] [3];
    struct name * child [9];
} node;

node * new_grid(node *parent) {
    node *n = calloc(1, sizeof(node));
    if (parent)
        memcpy(n->grid, parent->grid, sizeof(grid));
}

// is n a winner based on the move just made at x,y?
int winner(const node *n, int x, int y) {
    return (n->grid[x][0] == n->grid[x][1] == n->grid[x][2]) ||
           (n->grid[0][y] == n->grid[1][y] == n->grid[2][y]) ||
           ((x == y) && (n->grid[0][0] == n->grid[1][1] == n->grid[2][2])) ||
           ((2-x == y) && (n->grid[0][2] == n->grid[1][1] == n->grid[2][0]));
}

void fill(node *n, char c) {
    int x, y, children;
    node *child;

    for (x = 0; x < 3; x++) {
        for (y = 0; y < 3; y++) {
             if (n->grid[x][y])
                 continue;
             child = n->child[children++] = new_grid(n);
             child->grid[x][y] = c;

             // recurse unless this is a winning play
             if (!winner(child, x, y))
                 fill(child, c == 'x' ? 'y' : 'x');
        }
    }
}

int main(void) {
    node *start = new_grid(0);
    fill(start);
}

Answer 6

Здесь у вас есть рабочее решение.Он реализован на Python, но я думаю, что он может вам помочь.

Дерево игры рекурсивно создается с помощью функции build_tree и реализовано в виде списка списков.

Функция build_tree принимает в качестве входных параметров доску (узел дерева) и фигуру, у которой есть ход, и строит все возможные новые доски, полученные в результате применения фигуры к доске.Затем для каждой из этих новых досок она снова вызывает функцию build_tree, но на этот раз меняет фигуру, у которой есть ход.Когда доска является терминальной (без пустых квадратов), рекурсия заканчивается.

Это результирующее дерево для доски 1x3:

[(0, 0, 0), [[('x', 0, 0), [[(' x ',' o ', 0), [(' x ',' o ',' x ')]], [(' x ', 0,' o '), [('x', 'x', 'o')]]]], [(0, 'x', 0), [[('o', 'x', 0), [('o', 'x', 'x')]], [(0, 'x', 'o'), [('x', 'x', 'o')]]]]], [(0, 0,'x'), [[('o', 0, 'x'), [('o', 'x', 'x')]], [(0, 'o', 'x'), [('x', 'o', 'x')]]]]]]

Пустые квадраты обозначаются как 0.

Для игры в крестики-нолики, пожалуйста, измените blank_board = (0,0,0) до blank_board = (0,0,0,0,0,0,0,0,0), чтобы иметь доску 3х3.

def change_piece(piece):
    if piece == 'x': return 'o'
    return 'x'

def is_terminal(board):
    """Check if there are any empty square in the board"""
    for square in board:
        if square == 0:
            return False
    return True

def build_tree(node, piece):
    """Build the game tree recursively. 

    The tree is implemented as a list of lists.
    """
    child_nodes = []
    for index, value in enumerate(node):
        if value == 0:
            new_node = list(node)
            new_node[index] = piece
            new_node = tuple(new_node)
            if not is_terminal(new_node):
                child_nodes.append(build_tree(new_node,change_piece(piece)))
            else:
                child_nodes.append(new_node)
    if child_nodes:
        return [node,child_nodes]
    return

if __name__ == "__main__":
    blank_board = (0,0,0)
    game_tree = build_tree(blank_board,'x')
    print(game_tree)