Задача состоит в том, чтобы написать решатель для классической игры в карандаш и бумагу Dots and Boxes . Ваш код должен принимать два целых числа mи в nкачестве входных данных указывать размер доски.

Начиная с пустой сетки точек, игроки ходят по очереди, добавляя одну горизонтальную или вертикальную линию между двумя смежными соседними точками. Игрок, который заканчивает четвертую сторону поля 1 × 1, зарабатывает одно очко и получает другой ход. (Очки, как правило, записываются путем размещения в поле идентификационной метки игрока, такой как инициал). Игра заканчивается, когда больше не может быть линий. Победителем игры становится игрок с наибольшим количеством очков.

Можно предположить , что либо n = mили , n = m - 1и m, по крайней мере 2.

Задача состоит в solveтом, чтобы максимально развернуть игру Dots and Boxes менее чем за минуту. Размер игры просто n*m. Вывод вашего кода должен быть win, drawили loseкоторый должен быть результатом для первого игрока, при условии, что оба игрока играют оптимально.

Ваш код должен быть компилируемым / запускаемым в Ubuntu с использованием легко устанавливаемых и бесплатных инструментов. Пожалуйста, сообщайте о вашей оценке как о самой большой области, которую вы можете решить на своем компьютере за 1 минуту вместе со временем. Затем я проверю код на своем компьютере и составлю ранжированную таблицу записей.

В случае тай-брейка победителем будет самый быстрый код на доске самого большого размера, которую он сможет решить менее чем за минуту.

Было бы лучше, если бы выводимый код не просто выиграл или проиграл, но и действительный счет. Это делает для проверки вменяемости правильности.

C99 - доска 3х3 за 0,084 с

Изменить: я реорганизовал мой код и сделал более глубокий анализ результатов.

Дальнейшие правки: добавлена ​​обрезка по симметрии. Это дает 4 конфигурации алгоритма: с симметрией или без X с или без альфа-бета-отсечения

Дальнейшие правки: добавлено запоминание с использованием хеш-таблицы, что в итоге привело к невозможному: решение доски 3х3!

Основные характеристики:

• простая реализация минимакса с альфа-бета-отсечкой
• очень мало управления памятью (поддерживает dll действительных ходов; O (1) обновлений для каждой ветви в поиске дерева)
• Второй файл с обрезкой по симметрии. По-прежнему достигает O (1) обновлений для каждой ветви (технически O (S), где S - число симметрий. Это 7 для квадратных досок и 3 для неквадратных плат)
• третий и четвертый файлы добавить памятку. Вы можете контролировать размер хеш-таблицы ( #define HASHTABLE_BITWIDTH). Когда этот размер больше или равен количеству стен, это гарантирует отсутствие столкновений и O (1) обновлений. Меньшие хеш-таблицы будут иметь больше коллизий и будут немного медленнее.
• компилировать с -DDEBUGраспечатками

Потенциальные улучшения:

• исправить небольшую утечку памяти, исправленную в первом редактировании
• альфа / бета-обрезка добавлена ​​во втором редактировании
• обрезать симметрии, добавленные в третьем редакторе (обратите внимание, что симметрии не обрабатываются с помощью памятки, поэтому это остается отдельной оптимизацией)
• памятка добавлена ​​в 4-й редакции
• В настоящее время в памятке используется индикаторный бит для каждой стены. Доска 3х4 имеет 31 стену, поэтому этот метод не может обрабатывать доски 4х4 независимо от временных ограничений. улучшение будет состоять в том, чтобы эмулировать X-битные целые числа, где X, по крайней мере, равно числу стен.

Код

Из-за отсутствия организации количество файлов выросло из-под контроля. Весь код был перемещен в этот репозиторий Github . В редакторе заметок я добавил make-файл и скрипт тестирования.

Результаты

Примечания о сложности

Подходы грубой силы к точкам и коробкам очень быстро взрываются .

Рассмотрим доску со Rстроками и Cстолбцами. Есть R*Cквадраты, R*(C+1)вертикальные стены и C*(R+1)горизонтальные стены. Это всегоW = 2*R*C + R + C .

Поскольку Лембик попросил нас решить игру с минимаксом, нам нужно пройти к листьям дерева игры. Давайте пока проигнорируем обрезку, потому что важны порядки.

Есть Wварианты для первого хода. Для каждого из них следующий игрок может сыграть на любой из W-1оставшихся стен и т. Д. Это дает нам пространство для поиска SS = W * (W-1) * (W-2) * ... * 1или SS = W!. Факториалы огромны, но это только начало. SSколичество листовых узлов в пространстве поиска. Более важным для нашего анализа является общее количество решений, которые необходимо было принять (т. Е. Количество ветвей B в дереве). Первый слой веток имеет Wпараметры. Для каждого из них есть следующий уровень и W-1т. Д.

B = W + W*(W-1) + W*(W-1)*(W-2) + ... + W!

B = SUM W!/(W-k)!
  k=0..W-1

Давайте посмотрим на некоторые небольшие размеры таблицы:

Board Size  Walls  Leaves (SS)      Branches (B)
---------------------------------------------------
1x1         04     24               64
1x2         07     5040             13699
2x2         12     479001600        1302061344
2x3         17     355687428096000  966858672404689

Эти цифры становятся смешными. По крайней мере, они объясняют, почему код грубой силы навсегда висит на доске 2х3. Пространство поиска платы 2х3 в 742560 раз больше, чем 2х2 . Если для завершения 2x2 требуется 20 секунд, консервативная экстраполяция прогнозирует более 100 дней времени выполнения для 2x3. Очевидно, что нам нужно обрезать.

Анализ обрезки

Я начал с добавления очень простого сокращения с использованием алгоритма альфа-бета. По сути, он прекращает поиск, если идеальный противник никогда не даст ему свои текущие возможности. «Эй, смотри - я выиграю много, если мой противник позволит мне получить каждый квадрат!», - подумал ни один ИИ.

редактировать Я также добавил обрезку на основе симметричных плат. Я не использую метод запоминания, просто на случай, если когда-нибудь я добавлю запоминание и хочу оставить этот анализ отдельным. Вместо этого это работает так: большинство линий имеют «симметричную пару» где-то еще в сетке. Существует до 7 симметрий (горизонтальная, вертикальная, 180 вращений, 90 вращений, 270 вращений, диагональ и другие диагонали). Все 7 относятся к квадратным доскам, но последние 4 не относятся к неквадратным доскам. Каждая стена имеет указатель на свою «пару» для каждой из этих симметрий. Если при входе в поворот доска является горизонтально симметричной, то необходимо играть только по одной из каждой горизонтальной пары .

редактировать редактировать запоминание! Каждая стена получает уникальный идентификатор, который я обычно устанавливаю как индикаторный бит; у n-ой стены есть id 1 << n. Хэш доски - это просто ИЛИ всех сыгранных стен. Это обновляется в каждой ветви за O (1) раз. Размер хеш-таблицы устанавливается в #define. Все тесты были выполнены с размером 2 ^ 12, потому что почему бы и нет? Когда имеется больше стенок, чем битов, индексирующих хеш-таблицу (в данном случае 12 битов), наименее значимые 12 маскируются и используются в качестве индекса. Столкновения обрабатываются с помощью связанного списка в каждом индексе хеш-таблицы. Следующая таблица - это мой быстрый анализ того, как размер хеш-таблицы влияет на производительность. На компьютере с бесконечной оперативной памятью мы всегда устанавливаем размер таблицы равным числу стен. Доска 3х4 будет иметь хеш-таблицу длиной 2 ^ 31. Увы, у нас нет такой роскоши.

Хорошо, вернемся к обрезке. Остановив поиск высоко в дереве, мы сможем сэкономить много времени, не опускаясь до листьев. «Фактор обрезки» - это часть всех возможных ветвей, которые нам приходилось посещать. У грубой силы фактор обрезки равен 1. Чем он меньше, тем лучше.

Питон - 2x2 в 29 с

Кросс-постинг из головоломок . Не особенно оптимизирован, но может стать полезной отправной точкой для других участников.

from collections import defaultdict

VERTICAL, HORIZONTAL = 0, 1

#represents a single line segment that can be drawn on the board.
class Line(object):
    def __init__(self, x, y, orientation):
        self.x = x
        self.y = y
        self.orientation = orientation
    def __hash__(self):
        return hash((self.x, self.y, self.orientation))
    def __eq__(self, other):
        if not isinstance(other, Line): return False
        return self.x == other.x and self.y == other.y and self.orientation == other.orientation
    def __repr__(self):
        return "Line({}, {}, {})".format(self.x, self.y, "HORIZONTAL" if self.orientation == HORIZONTAL else "VERTICAL")

class State(object):
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.whose_turn = 0
        self.scores = {0:0, 1:0}
        self.lines = set()
    def copy(self):
        ret = State(self.width, self.height)
        ret.whose_turn = self.whose_turn
        ret.scores = self.scores.copy()
        ret.lines = self.lines.copy()
        return ret
    #iterate through all lines that can be placed on a blank board.
    def iter_all_lines(self):
        #horizontal lines
        for x in range(self.width):
            for y in range(self.height+1):
                yield Line(x, y, HORIZONTAL)
        #vertical lines
        for x in range(self.width+1):
            for y in range(self.height):
                yield Line(x, y, VERTICAL)
    #iterate through all lines that can be placed on this board, 
    #that haven't already been placed.
    def iter_available_lines(self):
        for line in self.iter_all_lines():
            if line not in self.lines:
                yield line

    #returns the number of points that would be earned by a player placing the line.
    def value(self, line):
        assert line not in self.lines
        all_placed = lambda seq: all(l in self.lines for l in seq)
        if line.orientation == HORIZONTAL:
            #lines composing the box above the line
            lines_above = [
                Line(line.x,   line.y+1, HORIZONTAL), #top
                Line(line.x,   line.y,   VERTICAL),   #left
                Line(line.x+1, line.y,   VERTICAL),   #right
            ]
            #lines composing the box below the line
            lines_below = [
                Line(line.x,   line.y-1, HORIZONTAL), #bottom
                Line(line.x,   line.y-1, VERTICAL),   #left
                Line(line.x+1, line.y-1, VERTICAL),   #right
            ]
            return all_placed(lines_above) + all_placed(lines_below)
        else:
            #lines composing the box to the left of the line
            lines_left = [
                Line(line.x-1, line.y+1, HORIZONTAL), #top
                Line(line.x-1, line.y,   HORIZONTAL), #bottom
                Line(line.x-1, line.y,   VERTICAL),   #left
            ]
            #lines composing the box to the right of the line
            lines_right = [
                Line(line.x,   line.y+1, HORIZONTAL), #top
                Line(line.x,   line.y,   HORIZONTAL), #bottom
                Line(line.x+1, line.y,   VERTICAL),   #right
            ]
            return all_placed(lines_left) + all_placed(lines_right)

    def is_game_over(self):
        #the game is over when no more moves can be made.
        return len(list(self.iter_available_lines())) == 0

    #iterates through all possible moves the current player could make.
    #Because scoring a point lets a player go again, a move can consist of a collection of multiple lines.
    def possible_moves(self):
        for line in self.iter_available_lines():
            if self.value(line) > 0:
                #this line would give us an extra turn.
                #so we create a hypothetical future state with this line already placed, and see what other moves can be made.
                future = self.copy()
                future.lines.add(line)
                if future.is_game_over(): 
                    yield [line]
                else:
                    for future_move in future.possible_moves():
                        yield [line] + future_move
            else:
                yield [line]

    def make_move(self, move):
        for line in move:
            self.scores[self.whose_turn] += self.value(line)
            self.lines.add(line)
        self.whose_turn = 1 - self.whose_turn

    def tuple(self):
        return (tuple(self.lines), tuple(self.scores.items()), self.whose_turn)
    def __hash__(self):
        return hash(self.tuple())
    def __eq__(self, other):
        if not isinstance(other, State): return False
        return self.tuple() == other.tuple()

#function decorator which memorizes previously calculated values.
def memoized(fn):
    answers = {}
    def mem_fn(*args):
        if args not in answers:
            answers[args] = fn(*args)
        return answers[args]
    return mem_fn

#finds the best possible move for the current player.
#returns a (move, value) tuple.
@memoized
def get_best_move(state):
    cur_player = state.whose_turn
    next_player = 1 - state.whose_turn
    if state.is_game_over():
        return (None, state.scores[cur_player] - state.scores[next_player])
    best_move = None
    best_score = float("inf")
    #choose the move that gives our opponent the lowest score
    for move in state.possible_moves():
        future = state.copy()
        future.make_move(move)
        _, score = get_best_move(future)
        if score < best_score:
            best_move = move
            best_score = score
    return [best_move, -best_score]

n = 2
m = 2
s = State(n,m)
best_move, relative_value = get_best_move(s)
if relative_value > 0:
    print("win")
elif relative_value == 0:
    print("draw")
else:
    print("lose")

Javascript - доска 1х2 за 20мс

Онлайн-демонстрация доступна здесь (предупреждение - очень медленное, если размер больше 1x2 с полной глубиной поиска ): https://dl.dropboxusercontent.com/u/141246873/minimax/index.html

Был разработан для оригинальных критериев победы (код гольф), а не для скорости.

Проверено в Google Chrome v35 на Windows 7.

//first row is a horizontal edges and second is vertical
var gameEdges = [
    [false, false],
    [false, false, false],
    [false, false]
]

//track all possible moves and score outcome
var moves = []

function minimax(edges, isPlayersTurn, prevScore, depth) {

    if (depth <= 0) {
        return [prevScore, 0, 0];
    }
    else {

        var pointValue = 1;
        if (!isPlayersTurn)
            pointValue = -1;

        var moves = [];

        //get all possible moves and scores
        for (var i in edges) {
            for (var j in edges[i]) {
                //if edge is available then its a possible move
                if (!edges[i][j]) {

                    //if it would result in game over, add it to the scores array, otherwise, try the next move
                    //clone the array
                    var newEdges = [];
                    for (var k in edges)
                        newEdges.push(edges[k].slice(0));
                    //update state
                    newEdges[i][j] = true;
                    //if closing this edge would result in a complete square, get another move and get a point
                    //square could be formed above, below, right or left and could get two squares at the same time

                    var currentScore = prevScore;
                    //vertical edge
                    if (i % 2 !== 0) {//i === 1
                        if (newEdges[i] && newEdges[i][j - 1] && newEdges[i - 1] && newEdges[i - 1][j - 1] && newEdges[parseInt(i) + 1] && newEdges[parseInt(i) + 1][j - 1])
                            currentScore += pointValue;
                        if (newEdges[i] && newEdges[i][parseInt(j) + 1] && newEdges[i - 1] && newEdges[i - 1][j] && newEdges[parseInt(i) + 1] && newEdges[parseInt(i) + 1][j])
                            currentScore += pointValue;
                    } else {//horizontal
                        if (newEdges[i - 2] && newEdges[i - 2][j] && newEdges[i - 1][j] && newEdges[i - 1][parseInt(j) + 1])
                            currentScore += pointValue;
                        if (newEdges[parseInt(i) + 2] && newEdges[parseInt(i) + 2][j] && newEdges[parseInt(i) + 1][j] && newEdges[parseInt(i) + 1][parseInt(j) + 1])
                            currentScore += pointValue;
                    }

                    //leaf case - if all edges are taken then there are no more moves to evaluate
                    if (newEdges.every(function (arr) { return arr.every(Boolean) })) {
                        moves.push([currentScore, i, j]);
                        console.log("reached end case with possible score of " + currentScore);
                    }
                    else {
                        if ((isPlayersTurn && currentScore > prevScore) || (!isPlayersTurn && currentScore < prevScore)) {
                            //gained a point so get another turn
                            var newMove = minimax(newEdges, isPlayersTurn, currentScore, depth - 1);

                            moves.push([newMove[0], i, j]);
                        } else {
                            //didnt gain a point - opponents turn
                            var newMove = minimax(newEdges, !isPlayersTurn, currentScore, depth - 1);

                            moves.push([newMove[0], i, j]);
                        }
                    }



                }


            }

        }//end for each move

        var bestMove = moves[0];
        if (isPlayersTurn) {
            for (var i in moves) {
                if (moves[i][0] > bestMove[0])
                    bestMove = moves[i];
            }
        }
        else {
            for (var i in moves) {
                if (moves[i][0] < bestMove[0])
                    bestMove = moves[i];
            }
        }
        return bestMove;
    }
}

var player1Turn = true;
var squares = [[0,0],[0,0]]//change to "A" or "B" if square won by any of the players
var lastMove = null;

function output(text) {
    document.getElementById("content").innerHTML += text;
}

function clear() {
    document.getElementById("content").innerHTML = "";
}

function render() {
    var width = 3;
    if (document.getElementById('txtWidth').value)
        width = parseInt(document.getElementById('txtWidth').value);
    if (width < 2)
        width = 2;

    clear();
    //need to highlight the last move taken and show who has won each square
    for (var i in gameEdges) {
        for (var j in gameEdges[i]) {
            if (i % 2 === 0) {
                if(j === "0")
                    output("*");
                if (gameEdges[i][j] && lastMove[1] == i && lastMove[2] == j)
                    output(" <b>-</b> ");
                else if (gameEdges[i][j])
                    output(" - ");
                else
                    output("&nbsp;&nbsp;&nbsp;");
                output("*");
            }
            else {
                if (gameEdges[i][j] && lastMove[1] == i && lastMove[2] == j)
                    output("<b>|</b>");
                else if (gameEdges[i][j])
                    output("|");
                else
                    output("&nbsp;");

                if (j <= width - 2) {
                    if (squares[Math.floor(i / 2)][j] === 0)
                        output("&nbsp;&nbsp;&nbsp;&nbsp;");
                    else
                        output("&nbsp;" + squares[Math.floor(i / 2)][j] + "&nbsp;");
                }
            }
        }
        output("<br />");

    }
}

function nextMove(playFullGame) {
    var startTime = new Date().getTime();
    if (!gameEdges.every(function (arr) { return arr.every(Boolean) })) {

        var depth = 100;
        if (document.getElementById('txtDepth').value)
            depth = parseInt(document.getElementById('txtDepth').value);

        if (depth < 1)
            depth = 1;

        var move = minimax(gameEdges, true, 0, depth);
        gameEdges[move[1]][move[2]] = true;
        lastMove = move;

        //if a square was taken, need to update squares and whose turn it is

        var i = move[1];
        var j = move[2];
        var wonSquare = false;
        if (i % 2 !== 0) {//i === 1
            if (gameEdges[i] && gameEdges[i][j - 1] && gameEdges[i - 1] && gameEdges[i - 1][j - 1] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][j - 1]) {
                squares[Math.floor(i / 2)][j - 1] = player1Turn ? "A" : "B";
                wonSquare = true;
            }
            if (gameEdges[i] && gameEdges[i][parseInt(j) + 1] && gameEdges[i - 1] && gameEdges[i - 1][j] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][j]) {
                squares[Math.floor(i / 2)][j] = player1Turn ? "A" : "B";
                wonSquare = true;
            }
        } else {//horizontal
            if (gameEdges[i - 2] && gameEdges[i - 2][j] && gameEdges[i - 1] && gameEdges[i - 1][j] && gameEdges[i - 1] && gameEdges[i - 1][parseInt(j) + 1]) {
                squares[Math.floor((i - 1) / 2)][j] = player1Turn ? "A" : "B";
                wonSquare = true;
            }
            if (gameEdges[i + 2] && gameEdges[parseInt(i) + 2][j] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][j] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][parseInt(j) + 1]) {
                squares[Math.floor(i / 2)][j] = player1Turn ? "A" : "B";
                wonSquare = true;
            }
        }

        //didnt win a square so its the next players turn
        if (!wonSquare)
            player1Turn = !player1Turn;

        render();

        if (playFullGame) {
            nextMove(playFullGame);
        }
    }

    var endTime = new Date().getTime();
    var executionTime = endTime - startTime;
    document.getElementById("executionTime").innerHTML = 'Execution time: ' + executionTime;
}

function initGame() {

    var width = 3;
    var height = 2;

    if (document.getElementById('txtWidth').value)
        width = document.getElementById('txtWidth').value;
    if (document.getElementById('txtHeight').value)
        height = document.getElementById('txtHeight').value;

    if (width < 2)
        width = 2;
    if (height < 2)
        height = 2;

    var depth = 100;
    if (document.getElementById('txtDepth').value)
        depth = parseInt(document.getElementById('txtDepth').value);

    if (depth < 1)
        depth = 1;

    if (width > 2 && height > 2 && !document.getElementById('txtDepth').value)
        alert("Warning. Your system may become unresponsive. A smaller grid or search depth is highly recommended.");

    gameEdges = [];
    for (var i = 0; i < height; i++) {
        if (i == 0) {
            gameEdges.push([]);
            for (var j = 0; j < (width - 1) ; j++) {
                gameEdges[i].push(false);
            }
        }
        else {
            gameEdges.push([]);
            for (var j = 0; j < width; j++) {
                gameEdges[(i * 2) - 1].push(false);
            }
            gameEdges.push([]);
            for (var j = 0; j < (width - 1) ; j++) {
                gameEdges[i*2].push(false);
            }
        }
    }

    player1Turn = true;

    squares = [];
    for (var i = 0; i < (height - 1) ; i++) {
        squares.push([]);
        for (var j = 0; j < (width - 1); j++) {
            squares[i].push(0);
        }
    }

    lastMove = null;

    render();
}

document.addEventListener('DOMContentLoaded', initGame, false);