O desafio é escrever um solucionador para o clássico jogo de lápis e papel Dots and Boxes . Seu código deve ter dois números inteiros me ncomo entrada, que especifica o tamanho do quadro.

Começando com uma grade vazia de pontos, os jogadores se revezam, adicionando uma única linha horizontal ou vertical entre dois pontos adjacentes não ligados. Um jogador que completa o quarto lado de uma caixa 1 × 1 ganha um ponto e faz outro turno. (Os pontos geralmente são registrados colocando na caixa uma marca de identificação do jogador, como uma inicial). O jogo termina quando não for possível colocar mais linhas. O vencedor do jogo é o jogador com mais pontos.

Você pode assumir que n = mou é n = m - 1e mé pelo menos 2.

O desafio é chegar ao solvemaior jogo possível de pontos e caixas em menos de um minuto. O tamanho de um jogo é simples n*m. A saída do seu código deve ser win, drawou losequal deve ser o resultado para o primeiro jogador, supondo que os dois jogadores joguem da melhor maneira.

Seu código deve ser compilável / executável no ubuntu usando ferramentas facilmente instaláveis ​​e gratuitas. Relate sua pontuação como a maior área que você pode resolver em seu computador em 1 minuto, juntamente com o tempo. Em seguida, testarei o código no meu computador e criará uma tabela de entradas ordenada por classificação.

No caso de um tie-break, o vencedor será o código mais rápido na maior placa de tamanho que puder resolver em menos de um minuto.

Seria melhor se o código emitido não apenas vencesse ou perdesse, mas também a pontuação real. Isso contribui para uma verificação da sanidade da correção.

C99 - placa 3x3 em 0,084s

Editar: refatorei meu código e fiz uma análise mais profunda dos resultados.

Edições adicionais: Poda adicionada por simetrias. Isso faz 4 configurações de algoritmo: com ou sem simetrias X com ou sem poda alfa-beta

Edições mais distantes: Adicionado memorização usando uma tabela de hash, finalmente alcançando o impossível: resolver uma placa 3x3!

Recursos principais:

• implementação direta do minimax com poda alfa-beta
• muito pouco gerenciamento de memória (mantém dll de movimentos válidos; O (1) atualizações por filial na pesquisa em árvore)
• segundo arquivo com poda por simetrias. Ainda obtém atualizações O (1) por filial (tecnicamente O (S), onde S é o número de simetrias. Isso é 7 para placas quadradas e 3 para placas não quadradas)
• terceiro e quarto arquivos adicionam memorização. Você tem controle sobre o tamanho da hashtable ( #define HASHTABLE_BITWIDTH). Quando esse tamanho é maior ou igual ao número de paredes, não garante colisões e O (1) é atualizado. As hashtables menores terão mais colisões e serão um pouco mais lentas.
• compilar com -DDEBUGpara impressões

Potenciais melhorias:

• corrigir pequeno vazamento de memória corrigido na primeira edição
• poda alfa / beta adicionada na 2ª edição
• remover simetrias adicionadas na 3ª edição (observe que as simetrias não são tratadas pela memorização, portanto isso permanece uma otimização separada.)
• memorização adicionada na 4ª edição
• atualmente a memorização usa um bit indicador para cada parede. Uma placa 3x4 possui 31 paredes; portanto, esse método não pode lidar com placas 4x4, independentemente das restrições de tempo. a melhoria seria emular números inteiros de bits X, onde X é pelo menos tão grande quanto o número de paredes.

Código

Devido à falta de organização, o número de arquivos ficou fora de controle. Todo o código foi movido para este repositório do Github . Na edição de memorização, adicionei um script makefile e testing.

Resultados

Notas sobre complexidade

As abordagens de força bruta para pontos e caixas explodem em complexidade muito rapidamente .

Considere um quadro com Rlinhas e Ccolunas. Existem R*Cquadrados, R*(C+1)paredes verticais e C*(R+1)paredes horizontais. Isso é um total de W = 2*R*C + R + C.

Como Lembik nos pediu para resolver o jogo com o minimax, precisamos atravessar as folhas da árvore do jogo. Vamos ignorar a poda por enquanto, porque o que importa são ordens de magnitude.

Existem Wopções para o primeiro movimento. Para cada um deles, o próximo jogador pode jogar qualquer uma das W-1paredes restantes, etc. Isso nos dá um espaço de pesquisa de SS = W * (W-1) * (W-2) * ... * 1, ou SS = W!. Os fatoriais são enormes, mas isso é apenas o começo. SSé o número de nós folha no espaço de pesquisa. Mais relevante para nossa análise é o número total de decisões que tiveram que ser tomadas (ou seja, o número de ramos B na árvore). A primeira camada de ramificações tem Wopções. Para cada um deles, o próximo nível tem W-1, etc.

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

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

Vejamos alguns tamanhos pequenos de tabela:

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

Esses números estão ficando ridículos. Pelo menos eles explicam por que o código de força bruta parece pendurar para sempre em uma placa 2x3. O espaço de pesquisa de uma placa 2x3 é 742560 vezes maior que 2x2 . Se 2x2 levar 20 segundos para ser concluído, uma extrapolação conservadora prevê mais de 100 dias de tempo de execução para 2x3. Claramente, precisamos podar.

Análise de poda

Comecei adicionando podas muito simples usando o algoritmo alfa-beta. Basicamente, para de procurar se um oponente ideal nunca lhe daria suas oportunidades atuais. "Ei, olhe - eu ganho muito se meu oponente me deixar ganhar todos os quadrados!"

edit Também adicionei poda com base em placas simétricas. Não uso uma abordagem de memorização, caso algum dia eu adicione memorização e queira manter essa análise separada. Em vez disso, funciona assim: a maioria das linhas tem um "par simétrico" em outro lugar da grade. Existem até 7 simetrias (horizontal, vertical, rotação 180, rotação 90, rotação 270, diagonal e a outra diagonal). Todos os 7 se aplicam a placas quadradas, mas os últimos 4 não se aplicam a placas não quadradas. Cada parede tem um ponteiro para o seu "par" para cada uma dessas simetrias. Se, entrando em um turno, o tabuleiro é horizontalmente simétrico, então apenas um de cada par horizontal precisa ser jogado.

editar editar Memoização! Cada parede recebe uma identificação única, que eu convenientemente defini como um indicador; a enésima parede tem o id 1 << n. O hash de um tabuleiro, então, é apenas o OR de todas as paredes jogadas. Isso é atualizado em cada filial no tempo O (1). O tamanho da hashtable é definido em a #define. Todos os testes foram executados com tamanho 2 ^ 12, por que não? Quando há mais paredes do que bits indexando a hashtable (12 bits neste caso), os 12 menos significativos são mascarados e usados ​​como índice. As colisões são tratadas com uma lista vinculada em cada índice de hashtable. O gráfico a seguir é minha análise rápida e suja de como o tamanho da hashtable afeta o desempenho. Em um computador com RAM infinita, sempre definiríamos o tamanho da tabela para o número de paredes. Uma placa 3x4 teria uma hashtable 2 ^ 31 de comprimento. Infelizmente, não temos esse luxo.

Ok, voltando à poda. Ao interromper a pesquisa no alto da árvore, podemos economizar muito tempo não descendo às folhas. O 'fator de poda' é a fração de todos os ramos possíveis que tivemos que visitar. A força bruta tem um fator de poda de 1. Quanto menor, melhor.

Python - 2x2 em 29s

Postagem cruzada de quebra - cabeças . Não é especialmente otimizado, mas pode ser um ponto de partida útil para outros participantes.

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 - placa 1x2 em 20ms

Demonstração on-line disponível aqui (aviso - muito lento se maior que 1x2 com profundidade total de pesquisa ): https://dl.dropboxusercontent.com/u/141246873/minimax/index.html

Foi desenvolvido para os critérios de vitória originais (código de golfe) e não para velocidade.

Testado no google chrome v35 no 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);