Zbuduj deterministyczną sztuczną inteligencję Go

11

Oto interesujący problem, o którym myślałem o innym dniu, który polega na tym, że fragmenty kodu konkurują z innymi fragmentami kodu nie tylko we właściwości, którą posiada kod, ale poprzez grę z innymi bitami kodu.

Twoim zadaniem jest zbudowanie programu, który przyjmuje bieżący stan planszy Go i określa, jaki ruch wykonać lub przekazać.

Twój program zaakceptuje następujące dane wejściowe:

  • 19 linii, każda po 19 znaków, reprezentujących elementy znajdujące się obecnie na planszy Go. Znak 0reprezentuje pusty kwadrat, 1jest czarny i 2jest biały.

  • Dwie liczby reprezentujące liczbę elementów więźnia każdego gracza (czarny, potem biały).

  • Jedna liczba reprezentująca, której tury ma się poruszyć (czarna lub biała). Jak wyżej, 1jest czarny i 2jest biały.

i wyślij jedną z następujących opcji:

  • Para współrzędnych a breprezentujących współrzędne, w których należy się poruszać. 1 1to lewy górny kwadrat, a pierwsza i druga cyfra oznaczają odpowiednio ruch w dół i w prawo.

  • Ciąg pass, który reprezentuje ruch do przejścia.

Na przykład program może otrzymać następujące dane wejściowe:

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

która reprezentuje grę, w której wykonano tylko kilka ruchów.

Wtedy program może wypisać 6 5, co oznacza „umieść czarny kamień na punkcie 6 od góry i 5 od lewej”. To uchwyciłoby biały kamień w 7 5. Stan tablicy zmieni się wtedy na:

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

(Pamiętaj, że chociaż schwytano biały kamień, liczy się jako więzień dla czarnych).

Twój kod musi dodatkowo spełniać następujące właściwości:

  • Jeśli program ma ten sam stan wejściowy, musi zawsze generować to samo wyjście. To jest determinizm Go AI. Nie może zawierać elementu losowego.

  • Twój program nie może zająć więcej niż około 60 sekund, aby ustalić, jaki ruch wykonać. Zasada ta nie będzie ściśle stosowana ze względu na różnice w mocy obliczeniowej, ale musi wykonać ruch w rozsądnym czasie.

  • Kod źródłowy programu nie może przekraczać łącznie 1 megabajta (1 048 576 bajtów).

  • Twój program musi zawsze dokonywać legalnych ruchów. Twój program nie może wykonać ruchu w miejscu, w którym kamień już istnieje, i nie może umieścić elementu, który spowodowałby złapanie grupy jego własnych kamieni. (Jednym wyjątkiem od zasad na potrzeby tego wyzwania jest to, że program może utworzyć pozycję, która pierwotnie tam była - ponieważ jest podany tylko bieżąca pozycja planszy, nie można oczekiwać, aby zapamiętać, które ruchy zostały wykonane przed.)

Twoje zgłoszenie zostanie następnie rozegrane w turnieju all-play-all przeciwko wszystkim innym zgłoszeniom, w grze Go, w której stan planszy zaczyna się jako pusty, a każdy program na zmianę jest karmiony pozycją planszy i wykonuje ruch .

Każda para zgłoszeń rozegra dwie rundy - jedną rundę, przy czym każdy gracz jest czarny. Ponieważ AI występujące w tym problemie są całkowicie deterministyczne, dwie takie same gry AI zawsze będą skutkowały dokładnie taką samą grą.

Warunki wygranej są następujące:

  • Jeśli twój program gra do końca gry, do ustalenia zwycięzcy zostaną użyte chińskie reguły punktacji Go. Nie zostaną zastosowane żadne komi.

  • Jeśli Twój program odtworzy się do tego stopnia, że ​​osiągnięty zostanie wcześniejszy stan, powodując nieskończoną pętlę, oba programy zostaną uznane za powiązane.

Twoje zgłoszenie zostanie ocenione na podstawie liczby punktów uzyskanych w porównaniu z innymi zgłoszeniami. Wygrana jest warta 1 punkt, a remis jest warty pół punktu. Zgłoszenie z największą liczbą punktów jest zwycięzcą ogólnym.


Jest to wyzwanie na szczycie wzgórza, w którym każdy może opublikować nowy wpis w dowolnym momencie, a wyniki będą okresowo ponownie oceniane, gdy to nastąpi.

Joe Z.
źródło
7
Ok, czekam na wszystkie inne zgłoszenia, a następnie napiszę własne, aby je pokonać - powinno być możliwe, ponieważ rozwiązania są deterministyczne.
Howard
1
Wydaje się, że gra w ko w taki sposób, że poprzednia pozycja jest powtarzana jest dozwolona, ​​ale prowadzi do natychmiastowego losowania (ponieważ powoduje pętlę). Ciekawe ...
FireFly
2
Wygląda na to, że twój problem jest zbyt trudny i nikt nie pracowałby wystarczająco ciężko, aby uzyskać wartościową odpowiedź (to naprawdę dużo pracy). To niezły problem, ale go jest zbyt trudny do pracy.
Victor Stafusa,
1
Dlaczego nie skorzystać z mniejszej planszy? 9x9 jest dość powszechny dla początkujących graczy. Drastycznie zmniejsza przestrzeń wyszukiwania, ale nie jest tak mała, że ​​została „pobita” jeszcze przez analizę (myślę, że największy, który został w pełni rozwiązany, to 5x6).
Geobits
1
Jak działa wejście? argumenty standardowe lub wiersza poleceń?
Ypnypn

Odpowiedzi:

7

Oto mój wpis, aby rozpocząć to wyzwanie od podstaw. Kod Python:

print "pass"

Zgodnie z twoimi zasadami zawsze gra „pass” jest prawidłową (choć złą) strategią.

Björn Lindqvist
źródło
Twój kod zawsze przegrywa z każdym, kto zagra przeciwko niemu. Mimo to, ładna odpowiedź na pytanie podstawowe.
Joe Z.
1
@JoeZ. I na pierwszy
David Mulder
4

Java: Wybierz miejsce, dowolne miejsce

Po prostu wybiera miejsca na planszy, aby sprawdzić ważność. Używa PRNG, ale z ustawionym ziarnem, więc jest to deterministyczne. Wykorzystuje różne fragmenty cyklu PRNG w zależności od liczby minionych zwojów.

Dla każdego stanowiska kandydata sprawdza, czy jest to prawidłowy ruch (ale nie jest to mądry ruch). Jeśli nie jest, przechodzi do następnego kandydata. Jeśli nie uda się znaleźć prawidłowego ruchu po 1000 próbach, przechodzi.

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;
}
Geobity
źródło
2

Some 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")
  }
}

Po przeczytaniu Wikipedii myślę, że pobije to obecne rozwiązanie.

yayestechlab
źródło
W obu przypadkach wygra o 361 punktów.
Joe Z.
Właściwie muszę to cofnąć, to nie jest zgodne ze specyfikacją. AI ma być bezpaństwowcem. Powinien wydrukować tylko jedną rzecz, biorąc pod uwagę stan planszy, a ty wydrukowałeś dwie ( 1 1i pass).
Joe Z.
@JoeZ. Naprawione. I tak by się nie skompilował.
yayestechlab
To zawsze będzie drukowane 1 1, ponieważ program jest zawsze uruchamiany od nowa za każdym razem, gdy zmienia się płyta.
Joe Z.
1

Jawa

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++;
      }
    }
  }
}

Wybiera pierwszą pustą przestrzeń. Wygrywa z którąkolwiek z AI w momencie publikacji.

Ypnypn
źródło
2
Nie gwarantuje to legalnego ruchu. Jeśli pierwsze dostępne miejsce nie ma żadnych swobód, nie można z niego zagrać. Na przykład, jeśli ta sztuczna inteligencja zagrała sama: po pierwszym rzędzie naprzemiennych pionków 1 1zostałby schwytany przez białą (teraz pustą) i nie może być zagrany przez czarną w następnej turze.
Geobity