Build a deterministic Go AI

Question

Here's an interesting problem I thought of the other day, which involves bits of code competing against other bits of code not just in a property that the code has, but by playing a game against those other bits of code.

Your task is to build a program that takes the current state of a Go board, and determines what move to make or to pass.

Your program will accept the following as input:

• 19 lines, each with 19 characters, representing the pieces currently on the Go board. A character of 0 represents an empty square, 1 is black, and 2 is white.

• Two numbers representing the number of prisoner pieces each player has (black, then white).

• One number representing whose turn it is to move (black or white). As above, 1 is black, and 2 is white.

and output one of the following:

• A pair of coordinates a b representing the coordinates at which to move. 1 1 is the top-left square, and the first and second numbers represent moving down and to the right respectively.

• The string pass, which represents a move to pass.

For example, the program may receive the following input:

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

which represents a game where only a few moves have been played.

Then the program might output 6 5, which means "put a black stone on the point 6th from the top and 5th from the left". This would capture the white stone at 7 5. The state of the board would then change to:

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

(Note that although a white stone was captured, it counts as a prisoner for black.)

Your code must additionally satisfy the following properties:

• If your program is given the same input state, it must always produce the same output. This is the determinism of the Go AI. It must not have a random component.

• Your program must not take more than approximately 60 seconds to determine what move to make. This rule will not be strictly applied due to variations in computing power, but it must make a move in a reasonable amount of time.

• Your program's source code must not exceed a total of 1 megabyte (1,048,576 bytes).

• Your program must always make legal moves. Your program cannot make a move where a stone already exists, and cannot place a piece that would result in a group of its own stones being captured. (One exception to the rules for the purposes of this challenge is that a program is allowed to create a position that was originally there - because it is only given the current position of a board, it cannot be expected to store which moves had been made before.)

Your submission will then play in an all-play-all tournament against all the other submissions, in a game of Go where the state of the board begins as empty, and each program takes turns being fed the position of the board and making a move.

Each pair of submissions will play two rounds - one round with each player being black. Because the AIs in this problem are completely deterministic, two of the same AIs playing together will always result in exactly the same game being played.

Conditions for a win are as such:

• If your program plays to the end of the game, the Chinese scoring rules of Go will be used to determine the winner. No komi will be applied.

• If your program plays to the point that an earlier state is reached, thus causing an infinite loop, the two programs will be declared to have tied.

Your submission will be scored by how many points it scores against other submissions. A win is worth 1 point, and a tie is worth half a point. The submission with the most points is the overall winner.

---

This is a king-of-the-hill challenge, in which anybody can post a new entry at any time, and the standings will be re-evaluated periodically when this happens.

Answer 1

Here is my entry to get this challenge off the ground. Python code:

print "pass"

According to your rules always playing "pass" is a valid (albeit bad) strategy.

Answer 2

Java : Pick a spot, any spot

Simply chooses spots on the board to test for validity. It uses the PRNG, but with a set seed so that's it's deterministic. It uses different chunks of the PRNG cycle depending on how many turns have passed.

For each candidate position, it checks to see that it's a valid move (but not that it's a smart move). If it isn't, it moves on to the next candidate. If it cannot find a valid move after 1000 tries, it passes.

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

Answer 3

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

From reading Wikipedia, I think this will beat the current solution.

Answer 4

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

Chooses the first empty space. Wins against any of the AIs as of time of posting.