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.

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ą.

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

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.

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.