Le défi consiste à écrire un solveur pour le jeu de crayons et de papier classique Dots and Boxes . Votre code doit prendre deux entiers met nen entrée qui spécifie la taille de la carte.

En commençant par une grille de points vide, les joueurs se relaient, en ajoutant une seule ligne horizontale ou verticale entre deux points adjacents non joints. Un joueur qui termine le quatrième côté d'une case 1 × 1 gagne un point et prend un autre tour. (Les points sont généralement enregistrés en plaçant dans la boîte une marque d'identification du joueur, telle qu'une initiale). Le jeu se termine quand plus aucune ligne ne peut être placée. Le gagnant du jeu est le joueur avec le plus de points.

Vous pouvez supposer que soit n = mou n = m - 1et mest au moins égal à 2.

Le défi consiste à solvecréer le plus grand jeu de points et de boîtes possible en moins d'une minute. La taille d'un jeu est simple n*m. La sortie de votre code devrait être win, drawou losedevrait être le résultat pour le premier joueur en supposant que les deux joueurs jouent de manière optimale.

Votre code doit être compilable / exécutable sur Ubuntu à l'aide d'outils faciles à installer et gratuits. Veuillez rapporter votre score comme la plus grande zone que vous pouvez résoudre sur votre ordinateur en 1 minute avec le temps. Je vais ensuite tester le code sur mon ordinateur et créer un tableau d'entrées classées par rang.

Dans le cas d'un bris d'égalité, le gagnant sera le code le plus rapide sur le tableau le plus grand qu'il pourra résoudre en moins d'une minute.

Il serait préférable que le code génère non seulement des gains ou des pertes, mais également le score réel. Cela permet une vérification de la justesse de l'exactitude.

C99 - Carte 3x3 en 0,084 s

Edit: j'ai refactorisé mon code et fait une analyse plus approfondie des résultats.

Modifications supplémentaires: ajout de l'élagage par symétrie. Cela fait 4 configurations d'algorithmes: avec ou sans symétries X avec ou sans élagage alpha-bêta

Modifications les plus éloignées: Ajout de la mémorisation à l'aide d'une table de hachage, réalisant enfin l'impossible: résoudre une carte 3x3!

Caractéristiques principales:

• mise en œuvre simple de minimax avec élagage alpha-bêta
• très peu de gestion de la mémoire (maintient la DLL des mouvements valides; O (1) mises à jour par branche dans la recherche dans l'arborescence)
• deuxième fichier avec élagage par symétrie. Réalise toujours O (1) mises à jour par branche (techniquement O (S) où S est le nombre de symétries. Il s'agit de 7 pour les panneaux carrés et 3 pour les panneaux non carrés)
• les troisième et quatrième fichiers ajoutent la mémorisation. Vous contrôlez la taille de la table de hachage ( #define HASHTABLE_BITWIDTH). Lorsque cette taille est supérieure ou égale au nombre de murs, elle ne garantit aucune collision ni mise à jour O (1). Les petites tables de hachage auront plus de collisions et seront légèrement plus lentes.
• compiler avec -DDEBUGpour les impressions

Améliorations potentielles:

• correction d'une petite fuite de mémoire corrigée lors de la première modification
• élagage alpha / bêta ajouté dans la 2e édition
• élaguer les symétries ajoutées dans la troisième édition (notez que les symétries ne sont pas gérées par la mémorisation, ce qui reste une optimisation distincte.)
• mémorisation ajoutée dans la 4e édition
• actuellement la mémorisation utilise un bit indicateur pour chaque mur. Une planche 3x4 a 31 murs, donc cette méthode ne pouvait pas gérer les planches 4x4 indépendamment des contraintes de temps. l'amélioration consisterait à émuler des entiers X bits, où X est au moins aussi grand que le nombre de murs.

Code

Faute d'organisation, le nombre de fichiers est devenu incontrôlable. Tout le code a été déplacé vers ce référentiel Github . Dans l'édition de mémorisation, j'ai ajouté un makefile et un script de test.

Résultats

Notes sur la complexité

Les approches par force brute des points et des boîtes explosent très rapidement en complexité .

Prenons un tableau avec des Rlignes et des Ccolonnes. Il y a des R*Ccarrés, R*(C+1)des murs verticaux et des C*(R+1)murs horizontaux. C'est un total de W = 2*R*C + R + C.

Parce que Lembik nous a demandé de résoudre le jeu avec minimax, nous devons traverser jusqu'aux feuilles de l'arbre à gibier. Ignorons pour l'instant la taille, car ce qui compte, ce sont les ordres de grandeur.

Il existe des Woptions pour le premier coup. Pour chacun d'eux, le joueur suivant peut jouer n'importe lequel des W-1murs restants, etc. Cela nous donne un espace de recherche de SS = W * (W-1) * (W-2) * ... * 1, ou SS = W!. Les factoriels sont énormes, mais ce n'est que le début. SSest le nombre de nœuds feuilles dans l'espace de recherche. Plus pertinent pour notre analyse est le nombre total de décisions qui ont dû être prises (c'est-à-dire le nombre de branches B dans l'arbre). La première couche de branches a des Woptions. Pour chacun d'eux, le niveau suivant a W-1, etc.

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

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

Regardons quelques petites tailles de table:

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

Ces chiffres deviennent ridicules. Au moins, ils expliquent pourquoi le code de force brute semble se bloquer indéfiniment sur une carte 2x3. L'espace de recherche d'une carte 2x3 est 742560 fois plus grand que 2x2 . Si 2x2 prend 20 secondes, une extrapolation prudente prédit plus de 100 jours de temps d'exécution pour 2x3. De toute évidence, nous devons tailler.

Analyse d'élagage

J'ai commencé par ajouter un élagage très simple en utilisant l'algorithme alpha-bêta. Fondamentalement, il arrête de chercher si un adversaire idéal ne lui donnerait jamais ses opportunités actuelles. "Hé, regarde - je gagne beaucoup si mon adversaire me laisse gagner chaque case!", Ne pensait jamais à l'IA.

edit J'ai également ajouté un élagage basé sur des planches symétriques. Je n'utilise pas une approche de mémorisation, juste au cas où un jour j'ajouterais la mémorisation et que je voudrais garder cette analyse séparée. Au lieu de cela, cela fonctionne comme ceci: la plupart des lignes ont une "paire symétrique" ailleurs sur la grille. Il existe jusqu'à 7 symétries (horizontale, verticale, rotation de 180, rotation de 90, rotation de 270, diagonale et l'autre diagonale). Les 7 s'appliquent aux planches carrées, mais les 4 dernières ne s'appliquent pas aux planches non carrées. Chaque mur a un pointeur sur sa "paire" pour chacune de ces symétries. Si, dans un tour, le plateau est symétrique horizontalement, alors une seule de chaque paire horizontale doit être jouée.

modifier modifier Mémorisation! Chaque mur reçoit un identifiant unique, que j'ai commodément défini comme un bit indicateur; le nième mur a l'identifiant 1 << n. Le hachage d'une planche n'est alors que le OU de tous les murs joués. Ceci est mis à jour à chaque branche en temps O (1). La taille de la table de hachage est définie dans a #define. Tous les tests ont été exécutés avec une taille 2 ^ 12, car pourquoi pas? Lorsqu'il y a plus de murs que de bits indexant la table de hachage (12 bits dans ce cas), les 12 moins significatifs sont masqués et utilisés comme index. Les collisions sont gérées avec une liste chaînée à chaque index de table de hachage. Le graphique suivant est mon analyse rapide et sale de la façon dont la taille de la table de hachage affecte les performances. Sur un ordinateur avec une RAM infinie, nous définirions toujours la taille de la table au nombre de murs. Une carte 3x4 aurait une table de hachage de 2 ^ 31 de long. Hélas, nous n'avons pas ce luxe.

Ok, revenons à l'élagage. En arrêtant la recherche en haut de l'arbre, on peut gagner beaucoup de temps en ne descendant pas vers les feuilles. Le «facteur d'élagage» est la fraction de toutes les branches possibles que nous avons dû visiter. La force brute a un facteur d'élagage de 1. Plus elle est petite, mieux c'est.

Python - 2x2 en 29s

Cross-affichage de puzzles . Pas spécialement optimisé, mais peut constituer un point de départ utile pour d'autres participants.

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 - carte 1x2 en 20ms

Démonstration en ligne disponible ici (avertissement - très lent si supérieur à 1x2 avec une profondeur de recherche complète ): https://dl.dropboxusercontent.com/u/141246873/minimax/index.html

A été développé pour les critères de victoire d'origine (code golf) et non pour la vitesse.

Testé dans google chrome v35 sur 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);