KoTH: Gomoku (pięć z rzędu)

Gomoku lub Pięć z rzędu to gra planszowa rozgrywana przez dwóch graczy na siatce z czarno-białymi kamieniami. Ten, kto umie układać kamieni z rzędu (poziomo, pionowo lub po przekątnej), wygrywa.$15 \times 15$$5$

Zasady

W tym KoTH zagramy w zasadę Zamień2, co oznacza, że ​​gra składa się z dwóch faz: W początkowej fazie dwaj gracze określają, kto pierwszy / kto gra czarny, a następnie umieszczają jeden kamień w każdej rundzie, zaczynając od gracza który wybrał czarny.

Faza początkowa

Niech gracze będą A i B, a A otworzy grę:

• Umieszcza dwa czarny i jeden biały kamień na planszy
• B może wybrać jeden z następujących trzech ruchów:
  • gracz B decyduje się zagrać na czarno: faza początkowa dobiegła końca
  • gracz B decyduje się na umieszczenie białego kamienia i gra na biało: faza początkowa dobiegła końca
  • gracz B decyduje się zagrać jeden czarny i jeden biały kamień: A wybiera kolor

Faza gry

Każdy gracz kładzie jeden kamień swojego koloru na planszy, zaczynając od gracza, który gra czarny, trwa to dopóki nie będzie już wolnych miejsc do gry (w tym przypadku jest remis) lub jeden gracz zdoła zagrać kamieni w jednym wiersz (w którym to przypadku gracz wygrywa).$5$

Rząd oznacza poziomą, pionową lub ukośną. Zwycięstwo to zwycięstwo - nie ma znaczenia, czy graczowi udało się zdobyć więcej niż jeden rząd.

Zasady gry KoTH

• każdy gracz gra przeciwko sobie dwa razy:
  • początkowo będzie losowo decydować, kto będzie pierwszy
  • w następnej grze gracz, który grał jako ostatni, jest pierwszy
• wygrana jest warta 2 punkty, remis 1 i przegrana 0
• celem jest zdobycie jak największej liczby punktów

Twój bot

Aby to wyzwanie było dostępne dla jak największej liczby języków, wejście / wyjście będzie odbywać się za pośrednictwem stdin / stdout (liniowe). Program oceniający wyświetli monit o wydrukowanie linii na standardowe wejście bota, a twój bot wydrukuje jedną linię na standardowe wyjście .

Po otrzymaniu EXITwiadomości otrzymasz pół sekundy, aby zakończyć zapisywanie do akt, zanim sędzia zabije proces.

Losowość

Aby umożliwić weryfikację turniejów, sędzia stosuje losową randomizację, a twój bot musi to zrobić z tego samego powodu. Bot otrzyma ziarno za pomocą argumentu wiersza poleceń, którego powinien użyć, zobacz następną sekcję.

Argumenty

Bot otrzymuje dwa argumenty wiersza poleceń:

1. imię przeciwnika
2. ziarno losowości

Stan użytkownika

Ponieważ Twój program będzie zawsze uruchamiany jako nowy dla każdej gry, musisz użyć plików, aby zachować wszelkie informacje, które chcesz zachować. Możesz czytać / zapisywać dowolne pliki lub tworzyć / usuwać podfoldery w bieżącym katalogu. Nie masz dostępu do żadnych plików w żadnym katalogu nadrzędnym!

Format wejścia / wyjścia

BOARDbędzie oznaczać listę aktualnych kamieni, wymienia tylko pozycje, w których kamień jest umieszczony, a każda pozycja będzie miała postać, ((X,Y),COLOR)gdzie Xi Ybędzie liczbą całkowitą z zakresu i będzie albo (czarna), albo ( biały).$[0,15)$COLOR"B""W"

Ponadto SPoznacza pojedynczą spację, XYkrotkę (X,Y)po dwie liczby całkowite w zakresie i oznacza wybór.$[0,15)$|

W początkowej fazie istnieją trzy różne rodzaje komunikatów:

Prompt (judge) -> Answer (bot)
"A" SP "[]"  -> XY XY XY
"B" SP BOARD -> "B" | "W" SP XY | XY XY
"C" SP BOARD -> "B" | "W"

• Pierwsza wiadomość prosi o trzy krotki, pierwsze dwie będą pozycjami czarnych kamieni, a trzecia pozycją białych.
• Druga wiadomość wymaga:
  • "B" -> wybierz czarny
  • "W" SP XY -> wybierz biały i umieść biały kamień na XY
  • XY XY -> umieść dwa kamienie (pierwszy czarny i drugi biały)
• Ostatni pyta tylko, w którym kolorze chcesz grać

Następnie rozpocznie się zwykła gra, a wiadomości staną się znacznie prostsze

N BOARD -> XY

gdzie Njest numerem rundy (zaczynając od ) i będzie miejscem, w którym umieścisz kamień.$0$XY

Jest jedna dodatkowa wiadomość, która nie oczekuje odpowiedzi

"EXIT" SP NAME | "EXIT TIE"

gdzie NAMEjest nazwa bota, który wygrał. Druga wiadomość zostanie wysłana, jeśli gra się skończy, ponieważ nikt nie wygrywa i nie ma już wolnych miejsc na kamienie (oznacza to, że nie można nazwać twojego bota TIE).

Formatowanie

Ponieważ wiadomości z bota można dekodować bez spacji, wszystkie spacje zostaną zignorowane (np. (0 , 0) (0,12)Traktowane jest tak samo jak (0,0)(0,12)). Wiadomości od sędziego zawierają tylko spację do oddzielenia różnych sekcji (tj. Jak wspomniano powyżej z SP), umożliwiając podział linii na spacje.

Każda nieprawidłowa odpowiedź spowoduje utratę tej rundy (nadal otrzymasz EXITwiadomość), zobacz zasady.

Przykład

Oto kilka przykładów rzeczywistych wiadomości:

A []
B [((0,0),"B"),((0,1),"W"),((14,14),"B")]
1 [((0,0),"B"),((0,1),"W"),((1,0),"B"),((1,1),"W"),((14,14),"B")]

Sędzia

Program oceniający możesz znaleźć tutaj : Aby dodać do niego bota, po prostu utwórz nowy folder w botsfolderze, umieść tam swoje pliki i dodaj plik metazawierający nazwę , polecenie , argumenty i flagę 0/1 (wyłącz / włącz stderr ) każdy na osobnej linii.

Aby uruchomić turniej, po prostu uruchom ./gomokui debuguj pojedynczy bot ./gomoku -d BOT.

Uwaga: Więcej informacji na temat konfiguracji i używania sędziego w repozytorium Github. Istnieją również trzy przykładowe boty ( Haskell , Python i JavaScript ).

Zasady

• przy każdej zmianie bota ^* turniej zostanie wznowiony, a gracz z największą liczbą punktów wygra (rozstrzygnięcie to pierwsze zgłoszenie)
• możesz zgłosić więcej niż jednego bota, o ile nie grają w wspólną strategię
• nie wolno dotykać plików poza katalogiem (np. manipulować plikami innych graczy)
• jeśli twój bot ulegnie awarii lub wyśle ​​nieprawidłową odpowiedź, bieżąca gra zostanie zakończona i przegrasz tę rundę
• chociaż sędzia (obecnie) nie egzekwuje limitu czasu na rundę, zaleca się utrzymanie czasu na niskim poziomie, ponieważ przetestowanie wszystkich zgłoszeń może być niewykonalne ^**
• nadużywanie błędów w programie dla sędziów liczy się jako luka

_{* Zachęcamy do korzystania z Github do oddzielnego przesyłania swojego bota bezpośrednio do botskatalogu (i potencjalnie modyfikowania util.sh)!}

_{** W przypadku pojawienia się problemu zostaniesz powiadomiony, powiedziałbym, że cokolwiek poniżej 500 ms (to dużo!) Powinno być na razie w porządku.}

Czat

Jeśli masz pytania lub chcesz porozmawiać o tym KoTH, dołącz do czatu !

KaitoBot

Wykorzystuje bardzo prymitywną implementację zasad MiniMax. Głębokość wyszukiwania jest również bardzo niska, ponieważ w przeciwnym razie zajmuje dużo czasu.

Może edytować, aby poprawić później.

Stara się także grać w czerń, jeśli to możliwe, ponieważ Wikipedia zdaje się mówić, że czerń ma przewagę.

Nigdy sam nie grałem w Gomoku, więc ustawiłem pierwsze trzy kamienie losowo z braku lepszego pomysłu.

const readline = require('readline');
const readLine = readline.createInterface({ input: process.stdin });

var debug = true;
var myColor = '';
var opponentColor = '';
var board = [];
var seed = parseInt(process.argv[3]);

function random(min, max) {
    changeSeed();
    var x = Math.sin(seed) * 10000;
    var decimal = x - Math.floor(x);
    var chosen = Math.floor(min + (decimal * (max - min)));
    return chosen;
}

function changeSeed() {
    var x = Math.sin(seed++) * 10000;
    var decimal = x - Math.floor(x);
    seed = Math.floor(100 + (decimal * 9000000));
}

function KaitoBot(ln) {
    var ws = ln.split(' ');

    if (ws[0] === 'A') {
        // Let's play randomly, we don't care.
        var nums = [];
        nums[0] = [ random(0, 15), random(0, 15) ];
        nums[1] = [ random(0, 15), random(0, 15) ];
        nums[2] = [ random(0, 15), random(0, 15) ];
        while (nums[1][0] == nums[0][0] && nums[1][1] == nums[0][1])
        {
            nums[1] = [ random(0, 15), random(0, 15) ];
        }
        while ((nums[2][0] == nums[0][0] && nums[2][1] == nums[0][1]) || (nums[2][0] == nums[1][0] && nums[2][1] == nums[1][1]))
        {
            nums[2] = [ random(0, 15), random(0, 15) ];
        }
        console.log('(' + nums[0][0] + ',' + nums[0][1] + ') (' + nums[1][0] + ',' + nums[1][1] + ') (' + nums[2][0] + ',' + nums[2][1] + ')');
    }
    else if (ws[0] === 'B') {
        // we're second to play, let's just pick black
        myColor = 'B';
        opponentColor = 'W';
        console.log('B');
    }
    else if (ws[0] === 'C') {
        // the other player chose to play 2 stones more, we need to pick..
        // I would prefer playing Black
        myColor = 'B';
        opponentColor = 'W';
        console.log('B');
    }
    else if (ws[0] === 'EXIT') {
        process.exit();
    }
    else {
        board = [];
        var json = JSON.parse(ws[1].replace(/\(\(/g,'{"xy":[')
                .replace(/"\)/g,'"}')
                .replace(/\),/g,'],"colour":'));
        // loop over all XYs and make a board object I can use
        for (var x = 0; x < 15; x++) {
            var newRow = []
            for (var y = 0; y < 15; y++) {
                var contains = false;
                json.forEach(j => {
                    if (j.xy[0] == x && j.xy[1] == y) {
                        contains = true;
                        newRow[newRow.length] = j.colour;
                    }
                });
                if (!contains) {
                    newRow[newRow.length] = ' ';
                }
            }
            board[board.length] = newRow;
        }
        // If we never picked Black, I assume we're White
        if (myColor == '') {
            myColor = 'W';
            opponentColor = 'B';
        }
        var bestMoves = ChooseMove(board, myColor, opponentColor);
        var chosenMove = bestMoves[random(0, bestMoves.length)];
        console.log('(' + chosenMove.X + ',' + chosenMove.Y + ')');
    }
}

function IsSquareRelevant(board, x, y) {
    return (board[x][y] == ' ' && 
        ((x > 0 && board[x - 1][y] != ' ') 
        || (x < 14 && board[x + 1][y] != ' ') 
        || (y > 0 && board[x][y - 1] != ' ') 
        || (y < 14 && board[x][y + 1] != ' ')
        || (x > 0 && y > 0 && board[x - 1][y - 1] != ' ') 
        || (x < 14 && y < 14 && board[x + 1][y + 1] != ' ') 
        || (y > 0 && x < 14 && board[x + 1][y - 1] != ' ') 
        || (y < 14 && x > 0 && board[x - 1][y + 1] != ' ')));
}

function ChooseMove(board, colorMe, colorOpponent) {
    var possibleMoves = [];
    for (var x = 0; x < 15; x++) {
        for (var y = 0; y < 15; y++) {
            if (IsSquareRelevant(board, x, y)) {
                possibleMoves[possibleMoves.length] = {X:x, Y:y};
            }
        }
    }
    var bestValue = -9999;
    var bestMoves = [possibleMoves[0]];
    for (var k in possibleMoves) {
        var changedBoard = JSON.parse(JSON.stringify(board));
        changedBoard[possibleMoves[k].X][possibleMoves[k].Y] = colorMe;
        var value = analyseBoard(changedBoard, colorMe, colorOpponent, colorOpponent, 2);
        if (value > bestValue) {
            bestValue = value;
            bestMoves = [possibleMoves[k]];
        } else if (value == bestValue) {
            bestMoves[bestMoves.length] = possibleMoves[k];
        }
    }
    return bestMoves;
}

function analyseBoard(board, color, opponent, nextToPlay, depth) {
    var tBoard = board[0].map((x,i) => board.map(x => x[i]));
    var score = 0.0;
    for (var x = 0; x < board.length; x++) {
        var inARow = 0;
        var tInARow = 0;
        var opponentInARow = 0;
        var tOpponentInARow = 0;
        var inADiago1 = 0;
        var opponentInADiago1 = 0;
        var inADiago2 = 0;
        var opponentInADiago2 = 0;

        for (var y = 0; y < board.length; y++) {
            if (board[x][y] == color) {
                inARow++;
                score += Math.pow(2, inARow);
            } else {
                inARow = 0;
            }
            if (board[x][y] == opponent) {
                opponentInARow++;
                score -= Math.pow(2, opponentInARow);
            } else {
                opponentInARow = 0;
            }
            if (tBoard[x][y] == color) {
                tInARow++;
                score += Math.pow(2, tInARow);
            } else {
                tInARow = 0;
            }
            if (tBoard[x][y] == opponent) {
                tOpponentInARow++;
                score -= Math.pow(2, tOpponentInARow);
            } else {
                tOpponentInARow = 0;
            }

            var xy = (y + x) % 15;
            var xy2 = (x - y + 15) % 15;
            if (xy == 0) {
                inADiago1 = 0;
                opponentInADiago1 = 0;
            }
            if (xy2 == 0) {
                inADiago2 = 0;
                opponentInADiago2 = 0;
            }

            if (board[xy][y] == color) {
                inADiago1++;
                score += Math.pow(2, inADiago1);
            } else {
                inADiago1 = 0;
            }
            if (board[xy][y] == opponent) {
                opponentInADiago1++;
                score -= Math.pow(2, opponentInADiago1);
            } else {
                opponentInADiago1 = 0;
            }
            if (board[xy2][y] == color) {
                inADiago2++;
                score += Math.pow(2, inADiago2);
            } else {
                inADiago2 = 0;
            }
            if (board[xy2][y] == opponent) {
                opponentInADiago2++;
                score -= Math.pow(2, opponentInADiago2);
            } else {
                opponentInADiago2 = 0;
            }


            if (inARow == 5 || tInARow == 5) {
                return 999999999.0;
            } else if (opponentInARow == 5 || tOpponentInARow == 5) {
                return -99999999.0;
            }
            if (inADiago1 == 5 || inADiago2 == 5) {
                return 999999999.0;
            } else if (opponentInADiago1 == 5 || opponentInADiago2 == 5) {
                return -99999999.0;
            }
        }
    }

    if (depth > 0) {
        var bestMoveValue = 999999999;
        var nextNextToPlay = color;
        if (nextToPlay == color) {
            nextNextToPlay = opponent;
            bestMoveValue = -999999999;
        }
        for (var x = 0; x < board.length; x++) {
            for (var y = 0; y < board.length; y++) {
                if (IsSquareRelevant(board, x, y)) {
                    var changedBoard = JSON.parse(JSON.stringify(board));
                    changedBoard[x][y] = nextToPlay;
                    var NextMoveValue = (analyseBoard(changedBoard, color, opponent, nextNextToPlay, depth - 1) * 0.1);

                    if (nextToPlay == color) {
                        if (NextMoveValue > bestMoveValue) {
                            bestMoveValue = NextMoveValue;
                        }
                    } else {
                        if (NextMoveValue < bestMoveValue) {
                            bestMoveValue = NextMoveValue;
                        }
                    }
                }
            }
        }
        score += bestMoveValue * 0.1;
    }
    return score;
}

readLine.on('line', (ln) => {

    KaitoBot(ln);

});

EDYCJE: Zmieniono dynamicznie zmianę zarodka, ponieważ w przeciwnym razie gdy javascript przekroczył 2 ^ 52, JavaScript nie byłby w stanie poprawnie obsłużyć przyrostu