Wyzwanie polega na napisaniu solvera do klasycznej ołówkowej i papierowej gry Dots and Boxes . Twój kod powinien przyjmować dwie liczby całkowite mi njako dane wejściowe określające rozmiar tablicy.

Zaczynając od pustej siatki kropek, gracze na zmianę dodają pojedynczą poziomą lub pionową linię między dwoma niepołączonymi sąsiednimi kropkami. Gracz, który ukończy czwartą stronę pola 1 × 1, zdobywa jeden punkt i wykonuje kolejną turę. (Punkty są zazwyczaj rejestrowane poprzez umieszczenie w polu identyfikatora gracza, takiego jak inicjał). Gra kończy się, gdy nie można już umieścić więcej linii. Zwycięzcą gry jest gracz z największą liczbą punktów.

Możesz założyć, że albo n = malbo n = m - 1i mwynosi co najmniej 2.

Wyzwanie polega na solvejak największej grze w kropki i pudełka w niecałą minutę. Rozmiar gry jest po prostu n*m. Wyjście kodzie powinno być win, drawlublose co powinno być wynikiem dla pierwszego gracza zakładając obaj gracze grać optymalnie.

Twój kod musi być kompilowalny / uruchamialny na Ubuntu przy użyciu łatwo instalowalnych i bezpłatnych narzędzi. Podaj swój wynik jako największy obszar, jaki możesz rozwiązać na komputerze w ciągu 1 minuty wraz z czasem. Następnie przetestuję kod na moim komputerze i utworzę uporządkowaną tabelę wpisów.

W przypadku remisu zwycięzca będzie najszybszym kodem na planszy największego rozmiaru, który może rozwiązać w niecałą minutę.

Byłoby lepiej, gdyby kod generował nie tylko wygraną lub przegraną, ale także faktyczny wynik. To powoduje sprawdzenie poprawności poprawności poczytalności.

C99 - tablica 3x3 w 0,084s

Edycja: Zmodyfikowałem kod i przeprowadziłem głębszą analizę wyników.

Dalsze zmiany: Dodano przycinanie przez symetrie. To sprawia, że ​​4 konfiguracje algorytmów: z lub bez symetrii X z przycinaniem alfa-beta lub bez

Najdalsze edycje : Dodano zapamiętywanie za pomocą tabeli skrótów, w końcu osiągnięcie niemożliwego: rozwiązanie planszy 3x3!

Główne cechy:

• prosta implementacja minimax z przycinaniem alfa-beta
• bardzo mało zarządzania pamięcią (utrzymuje dll prawidłowych ruchów; aktualizacje O (1) na gałąź w wyszukiwaniu drzewa)
• drugi plik z przycinaniem przez symetrie. Nadal osiąga aktualizacje O (1) na gałąź (technicznie O (S), gdzie S jest liczbą symetrii. Jest to 7 dla kwadratowych desek i 3 dla desek nie kwadratowych)
• trzeci i czwarty plik dodają zapamiętywanie. Masz kontrolę nad rozmiarem tablicy mieszającej (#define HASHTABLE_BITWIDTH ). Gdy ten rozmiar jest większy lub równy liczbie ścian, gwarantuje to brak kolizji i aktualizacji O (1). Mniejsze tablice skrótów będą miały więcej kolizji i będą nieco wolniejsze.
• Połącz z -DDEBUG wydrukami

Potencjalne ulepszenia:

• naprawić mały wyciek pamięci naprawiony podczas pierwszej edycji
• przycinanie alfa / beta dodano w 2. edycji
• przycinamy symetrie dodane w 3. edycji (zauważ, że symetrie nie są obsługiwane przez zapamiętywanie, więc pozostaje to osobną optymalizacją).
• zapamiętywanie dodane w 4. edycji
• obecnie memoizacja używa bitu wskaźnika dla każdej ściany. Tablica 3x4 ma 31 ścian, więc ta metoda nie poradzi sobie z tablicami 4x4 niezależnie od ograniczeń czasowych. poprawa polegałaby na emulacji liczb całkowitych X-bit, gdzie X jest co najmniej tak duża, jak liczba ścian.

Kod

Z powodu braku organizacji liczba plików wymknęła się spod kontroli. Cały kod został przeniesiony do tego repozytorium Github . W edycji notatki dodałem plik makefile i skrypt testowy.

Wyniki

Uwagi na temat złożoności

Podejścia brutalnych sił do kropek i pudełek bardzo szybko się komplikują .

Rozważ tablicę z Rrzędami i Ckolumnami. Istnieją R*Ckwadraty, R*(C+1)ściany pionowe i C*(R+1)ściany poziome. To w sumieW = 2*R*C + R + C .

Ponieważ Lembik poprosił nas o rozwiązanie gry z minimaxem, musimy przejść do liści drzewa gry. Na razie zignorujmy przycinanie, ponieważ liczy się rząd wielkości.

Istnieją Wopcje pierwszego ruchu. Dla każdego z nich następny gracz może zagrać w dowolną z W-1pozostałych ścian itp. To daje nam pole przeszukiwania SS = W * (W-1) * (W-2) * ... * 1, lub SS = W!. Czynniki są ogromne, ale to dopiero początek. SSto liczba węzłów liści w przestrzeni wyszukiwania. Bardziej istotna dla naszej analizy jest całkowita liczba decyzji, które musiały zostać podjęte (tj. Liczba gałęzi B drzewa). Pierwsza warstwa gałęzi ma Wopcje. Dla każdego z nich następny poziom ma W-1itp.

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

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

Spójrzmy na kilka małych rozmiarów stołu:

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

Te liczby stają się śmieszne. Przynajmniej wyjaśniają, dlaczego kod brutalnej siły wydaje się zawieszać na zawsze na płycie 2x3. Przestrzeń wyszukiwania na tablicy 2x3 jest 742560 razy większa niż 2x2 . Jeśli wykonanie 2x2 zajmuje 20 sekund, zachowawcza ekstrapolacja przewiduje ponad 100 dni czasu wykonania dla 2x3. Oczywiście musimy przycinać.

Analiza przycinania

Zacząłem od dodania bardzo prostego przycinania przy użyciu algorytmu alfa-beta. Zasadniczo przestaje szukać, czy idealny przeciwnik nigdy nie dałby mu obecnych możliwości. „Hej, spójrz - dużo wygrywam, jeśli mój przeciwnik pozwala mi zdobyć każdy kwadrat!”, Pomyślał, że nie ma AI.

edytuj Dodałem również przycinanie oparte na symetrycznych tablicach. Nie używam metody zapamiętywania, na wszelki wypadek, gdy pewnego dnia dodam zapamiętywanie i chcę oddzielić tę analizę od siebie. Zamiast tego działa to tak: większość linii ma „parę symetryczną” gdzieś na siatce. Istnieje do 7 symetrii (pozioma, pionowa, obrót o 180 stopni, obrót o 90 stopni, obrót o 270 stopni, przekątna i druga przekątna). Wszystkie 7 dotyczą desek kwadratowych, ale ostatnie 4 nie dotyczą desek kwadratowych. Każda ściana ma wskaźnik do „pary” dla każdej z tych symetrii. Jeśli wchodząc w zakręt, plansza jest symetryczna poziomo, wówczas należy zagrać tylko jedną z każdej pary poziomej .

edytuj edytuj Zapamiętywanie! Każda ściana ma unikalny identyfikator, który wygodnie ustawiam jako bit wskaźnikowy; n-ta ściana ma identyfikator 1 << n. Skrót tablicy jest więc tylko salą wszystkich granych ścian. Jest to aktualizowane w każdym oddziale w czasie O (1). Rozmiar tablicy hashtable jest ustawiony na #define. Wszystkie testy zostały przeprowadzone z rozmiarem 2 ^ 12, ponieważ dlaczego nie? Gdy jest więcej ścian niż bitów indeksujących tablicę mieszającą (w tym przypadku 12 bitów), najmniej znaczące 12 jest maskowane i używane jako indeks. Kolizje są obsługiwane za pomocą połączonej listy w każdym indeksie tablicy mieszającej. Poniższa tabela to moja szybka i brudna analiza wpływu wielkości tabeli mieszającej na wydajność. Na komputerze z nieskończoną pamięcią RAM zawsze ustawialiśmy rozmiar stołu na liczbę ścian. Tablica 3x4 miałaby tablicę mieszającą o długości 2 ^ 31. Niestety nie mamy tego luksusu.

Ok, wracając do przycinania. Zatrzymując wyszukiwanie wysoko w drzewie, możemy zaoszczędzić dużo czasu, nie schodząc do liści. „Czynnik przycinania” to ułamek wszystkich możliwych gałęzi, które musieliśmy odwiedzić. Brute-force ma współczynnik przycinania równy 1. Im jest mniejszy, tym lepiej.

Python - 2x2 w 29s

Publikowanie postów z puzzli . Niezbyt zoptymalizowany, ale może stanowić przydatny punkt wyjścia dla innych uczestników.

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 - płyta 1x2 w 20ms

Demo online dostępne tutaj (ostrzeżenie - bardzo wolne, jeśli większe niż 1x2 z pełną głębokością wyszukiwania ): https://dl.dropboxusercontent.com/u/141246873/minimax/index.html

Został opracowany dla oryginalnych kryteriów wygranych (kod golfa), a nie dla prędkości.

Testowane w Google Chrome v35 na 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);