Erstellen Sie eine deterministische Go-KI

11

Hier ist ein interessantes Problem, an das ich neulich gedacht habe, bei dem Codebits nicht nur in einer Eigenschaft des Codes mit anderen Codebits konkurrieren, sondern auch ein Spiel gegen diese anderen Codebits spielen.

Ihre Aufgabe ist es, ein Programm zu erstellen, das den aktuellen Status eines Go-Boards übernimmt und festlegt, welche Bewegung ausgeführt oder bestanden werden soll.

Ihr Programm akzeptiert Folgendes als Eingabe:

  • 19 Zeilen mit jeweils 19 Zeichen, die die derzeit auf dem Go-Brett befindlichen Teile darstellen. Ein Zeichen von steht 0für ein leeres Quadrat, 1ist schwarz und 2weiß.

  • Zwei Zahlen, die die Anzahl der Gefangenenstücke darstellen, die jeder Spieler hat (schwarz, dann weiß).

  • Eine Zahl, die angibt, wer an der Reihe ist, sich zu bewegen (schwarz oder weiß). Wie oben 1ist schwarz und 2ist weiß.

und geben Sie eine der folgenden Optionen aus:

  • Ein Koordinatenpaar, a bdas die Koordinaten darstellt, um die bewegt werden soll. 1 1ist das Quadrat oben links, und die erste und die zweite Zahl stehen für die Bewegung nach unten bzw. rechts.

  • Die Zeichenfolge pass, die eine zu übergebende Bewegung darstellt.

Beispielsweise kann das Programm die folgende Eingabe erhalten:

0000000000000000000
0000000000000000000
0000000000000000000
0001000000000002000
0000000000000000000
0000000000000000000
0001210000000000000
0000100000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0002000000000001000
0000000000000000000
0000000000000000000
0000000000000000000
0 0 1

Dies ist ein Spiel, bei dem nur wenige Züge gespielt wurden.

Dann könnte das Programm ausgeben 6 5, was bedeutet, "einen schwarzen Stein auf den Punkt 6 von oben und 5 von links setzen". Dies würde den weißen Stein bei einfangen 7 5. Der Status des Boards würde sich dann ändern zu:

0000000000000000000
0000000000000000000
0000000000000000000
0001000000000002000
0000000000000000000
0000100000000000000
0001010000000000000
0000100000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0002000000000001000
0000000000000000000
0000000000000000000
0000000000000000000
1 0 2

(Beachten Sie, dass ein weißer Stein zwar gefangen genommen wurde, aber als Gefangener für Schwarz gilt.)

Ihr Code muss zusätzlich die folgenden Eigenschaften erfüllen:

  • Wenn Ihr Programm denselben Eingabestatus erhält, muss es immer dieselbe Ausgabe erzeugen. Dies ist der Determinismus der Go AI. Es darf keine zufällige Komponente haben.

  • Ihr Programm darf nicht länger als ungefähr 60 Sekunden dauern, um zu bestimmen, welche Bewegung ausgeführt werden soll. Diese Regel wird aufgrund von Schwankungen der Rechenleistung nicht strikt angewendet, muss jedoch in angemessener Zeit ausgeführt werden.

  • Der Quellcode Ihres Programms darf insgesamt 1 Megabyte (1.048.576 Byte) nicht überschreiten.

  • Ihr Programm muss immer legale Schritte unternehmen. Ihr Programm kann keine Bewegung ausführen, bei der bereits ein Stein vorhanden ist, und es kann kein Teil platziert werden, das dazu führen würde, dass eine Gruppe eigener Steine ​​erfasst wird. (Eine Ausnahme von den Regeln für die Zwecke dieser Herausforderung besteht darin, dass ein Programm eine Position erstellen darf, die ursprünglich dort war. Da nur die aktuelle Position eines Bretts angegeben wird, kann nicht erwartet werden, dass gespeichert wird, welche Züge ausgeführt wurden Vor.)

Ihre Einsendung wird dann in einem All-Play-All-Turnier gegen alle anderen Einsendungen gespielt, in einem Go-Spiel, bei dem der Status des Bretts als leer beginnt und jedes Programm abwechselnd die Position des Bretts erhält und einen Zug macht .

Jedes Einreichungspaar spielt zwei Runden - eine Runde, wobei jeder Spieler schwarz ist. Da die AIs in diesem Problem vollständig deterministisch sind, führen zwei derselben AIs, die zusammen spielen, immer dazu, dass genau dasselbe Spiel gespielt wird.

Die Bedingungen für einen Sieg sind als solche:

  • Wenn Ihr Programm bis zum Ende des Spiels abgespielt wird, werden die chinesischen Bewertungsregeln von Go verwendet, um den Gewinner zu ermitteln. Es wird kein Komi angewendet.

  • Wenn Ihr Programm so weit abgespielt wird, dass ein früherer Zustand erreicht ist, wodurch eine Endlosschleife verursacht wird, werden die beiden Programme als gebunden deklariert.

Ihre Einsendung wird danach bewertet, wie viele Punkte sie gegen andere Einsendungen erzielt. Ein Sieg ist 1 Punkt wert und ein Unentschieden einen halben Punkt. Die Einreichung mit den meisten Punkten ist der Gesamtsieger.


Dies ist eine King-of-the-Hill-Herausforderung, bei der jeder jederzeit einen neuen Eintrag veröffentlichen kann. In diesem Fall wird die Rangliste regelmäßig neu bewertet.

Joe Z.
quelle
7
Ok, auf alle anderen Einsendungen warten und dann meine eigenen schreiben, um sie zu schlagen - sollte möglich sein, da die Lösungen deterministisch sind.
Howard
1
Es scheint, dass das Spielen in ko so ist, dass die vorherige Position wiederholt wird, aber zum sofortigen Ziehen führt (da dies eine Schleife verursacht). Interessant ...
FireFly
2
Sieht so aus, als wäre Ihr Problem zu schwierig und niemand würde hart genug arbeiten, um eine wertvolle Antwort zu finden (es ist wirklich viel Arbeit). Es ist ein schönes Problem, aber es ist viel zu schwer, damit zu arbeiten.
Victor Stafusa
1
Warum nicht ein kleineres Board verwenden? 9x9 ist häufig genug für Anfänger. Es reduziert den Suchraum dramatisch, ist aber nicht so klein, dass es noch durch Analyse "geschlagen" wurde (ich denke, der größte, der vollständig gelöst wurde, ist 5x6).
Geobits
1
Wie funktioniert die Eingabe? Standard- oder Befehlszeilenargumente?
Ypnypn

Antworten:

7

Hier ist mein Beitrag, um diese Herausforderung auf den Weg zu bringen. Python-Code:

print "pass"

Nach Ihren Regeln ist das Spielen von "Pass" immer eine gültige (wenn auch schlechte) Strategie.

Björn Lindqvist
quelle
Ihr Code verliert immer gegen jeden, der dagegen spielt. Trotzdem eine schöne Antwort auf den Basisfall.
Joe Z.
1
@ JoeZ. Und wie es aussah, gewann er damit: P
David Mulder
4

Java: Wählen Sie einen Punkt, einen beliebigen Punkt

Wählt einfach Punkte auf der Tafel aus, um die Gültigkeit zu testen. Es verwendet das PRNG, aber mit einem festgelegten Startwert ist das deterministisch. Je nachdem, wie viele Runden vergangen sind, werden unterschiedliche Abschnitte des PRNG-Zyklus verwendet.

Für jede Kandidatenposition wird überprüft, ob es sich um einen gültigen Zug handelt (nicht jedoch um einen intelligenten Zug). Wenn dies nicht der Fall ist, geht es weiter zum nächsten Kandidaten. Wenn es nach 1000 Versuchen keinen gültigen Zug findet, ist es erfolgreich.

import java.util.Random;
import java.util.Scanner;

public class GoNaive {

    int[][] board;
    boolean[] checked;
    int me;

    public static void main(String[] args) {
        new GoNaive().run();
    }

    void run(){
        int turns = init();
        Random rand = new Random(seed);

        for(int i=0;i<turns*tries;i++)
            rand.nextInt(size*size);

        for(int i=0;i<tries;i++){
            int pos = rand.nextInt(size*size);
            for(int c=0;c<size*size;c++)
                checked[c]=false;
            if(board[pos%size][pos/size] == 0)
                if(hasLiberties(pos, me)){
                    System.out.print((pos%size+1) + " " + (pos/size+1));
                    System.exit(0);
                }
        }
        System.out.print("pass");
    }

    boolean hasLiberties(int pos, int color){
        if(checked[pos])
            return false;
        checked[pos] = true;

        int x = pos%size, y=pos/size, n;

        if(x>0){
            n = board[x-1][y];
            if(n==0 || (n==me && hasLiberties(y*size+x-1, color)))
                return true;
        }
        if(size-x>1){
            n = board[x+1][y];
            if(n==0 || (n==me && hasLiberties(y*size+x+1, color)))
                return true;
        }
        if(y>0){
            n = board[x][y-1];
            if(n==0 || (n==me && hasLiberties((y-1)*size+x, color)))
                return true;
        }
        if(size-y>1){
            n = board[x][y+1];
            if(n==0 || (n==me && hasLiberties((y+1)*size+x, color)))
                return true;
        }
        return false;
    }

    int init(){
        int turns = 0;
        board = new int[size][size];
        checked = new boolean[size*size];
        turns = 0;
        Scanner s = new Scanner(System.in);
        String line;
        for(int i=0;i<size;i++){
            line = s.nextLine();
            for(int j=0;j<size;j++){
                board[j][i] = line.charAt(j)-48;
                if(board[j][i] > 0)
                    turns++;
            }
        }
        String[] tokens = s.nextLine().split(" ");
        turns += Integer.valueOf(tokens[0]);
        turns += Integer.valueOf(tokens[1]);
        me = Integer.valueOf(tokens[2]);
        s.close();
        return turns;
    }

    final static int size = 19;
    final static int seed = 0xdeadface;
    final static int tries = 1000;
}
Geobits
quelle
2

Einige Scala:

package go;

class Go {
  def main(args : Array[String]) {
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    System.out.printLn("1 1")
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    System.out.printLn("pass")
  }
}

Nach dem Lesen von Wikipedia denke ich, dass dies die aktuelle Lösung übertreffen wird.

yayestechlab
quelle
Tatsächlich wird es in beiden Fällen mit 361 Punkten gewinnen.
Joe Z.
Eigentlich muss ich das zurücknehmen, es folgt nicht der Spezifikation. Die KI soll staatenlos sein. Es soll eigentlich nur eine Sache drucken , wenn der Status der Tafel gegeben ist, und Sie haben dafür gesorgt, dass zwei ( 1 1und pass) gedruckt werden .
Joe Z.
@ JoeZ. Repariert. Hätte sowieso nicht kompiliert.
Yayestechlab
Das wird eigentlich immer gedruckt 1 1, da das Programm jedes Mal neu ausgeführt wird, wenn sich die Karte ändert.
Joe Z.
1

Java

public class Go {
  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    for (int i = 0; i < 361;) {
      char c = s.nextChar();
      if (c != '\n') {
        if (c == '0') {
          System.out.println((i % 19 + 1) + " " + (i / 19 + 1));
          System.exit(0);
        }
        i++;
      }
    }
  }
}

Wählt den ersten leeren Raum. Gewinnt gegen eine der AIs zum Zeitpunkt der Veröffentlichung.

Ypnypn
quelle
2
Dies garantiert keinen legalen Umzug. Wenn der erste verfügbare Platz keine Freiheiten hat, kann er nicht gespielt werden. Zum Beispiel, wenn diese KI sich selbst spielte: Nach der ersten Reihe abwechselnder Teile 1 1würde sie von Weiß (jetzt leer) gefangen genommen und könnte in der nächsten Runde nicht von Schwarz gespielt werden.
Geobits