Build a deterministic Go AI

11

1

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.

Joe Z.

Posted 2014-01-14T07:07:46.443

Reputation: 30 589

Do you really expect someone to develop a program able to play go? This has been tried for 40 years or so and the best attempts can be easily beaten by any moderately experienced player. – None – 2015-02-04T07:00:11.280

1Well I think we could invite Google to this challenge. – flawr – 2016-03-13T19:04:14.813

Note that pseudorandom processes are fair game, as long as they're still completely deterministic. – Joe Z. – 2014-01-14T07:16:37.220

7Ok, waiting for all other submissions and then write my own in order to beat them - should be possible since the solutions are deterministic. – Howard – 2014-01-14T07:50:22.790

@Howard I guess the winner will be the last person to tweak their random seed before the code freeze. – shiona – 2014-01-14T08:16:03.223

@shiona The catch there is that Go still has a bunch of strategy involved, unlike a game like Rock Paper Scissors. A completely randomized solution will still lose to an advanced algorithm, no matter how the seed is changed. – Joe Z. – 2014-01-14T08:18:54.673

Sounds like you need a [king-of-the-hill] tag for this. – Gareth – 2014-01-14T08:48:44.297

Oh. I kind of assumed that was what my [code-tournament] tag was for. – Joe Z. – 2014-01-14T09:08:01.137

No point creating a new tag when there's one already in use. – Gareth – 2014-01-14T09:13:10.587

I didn't know the [king-of-the-hill] tag existed, which is the only reason I created the [code-tournament] one. – Joe Z. – 2014-01-14T09:13:50.667

The board representation is insufficient: how would the program recognise ko? – Peter Taylor – 2014-01-14T09:29:49.593

1It seems playing in ko such that the previous position is repeated is allowed but leads to immediate draw (since it causes a loop). Interesting... – FireFly – 2014-01-14T11:04:01.013

@JoeZ. I know, I've played some. It was an attempt of a retort towards Howards comment. – shiona – 2014-01-14T15:18:32.813

2Looks like that your problem is too dificult and nobody would work hard enough to produce a worthful answer (it is really a lot of work). It is a nice problem, but go is way too hard to work with. – Victor Stafusa – 2014-01-19T06:31:25.017

Yeah, that's true. I find myself struggling to even make a legal move function. – Joe Z. – 2014-01-19T20:58:07.533

1Why not use a smaller board? 9x9 is common enough for beginner players. It cuts the search space down dramatically, but it's not so small that it's been "beaten" yet by analysis (I think the largest that's been fully solved is 5x6). – Geobits – 2014-03-06T03:09:02.907

1How does input work? stdin or command line arguments? – Ypnypn – 2014-05-04T16:35:21.167

1This problem needs a "driver" that will run 2 solutions against each other and determine the result – aditsu quit because SE is EVIL – 2014-05-05T16:26:30.220

Answers

7

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.

Björn Lindqvist

Posted 2014-01-14T07:07:46.443

Reputation: 590

Your code will always lose against anyone that makes any play against it. Still, nice base-case answer. – Joe Z. – 2014-01-14T17:09:54.093

1@JoeZ. And from the looks of it he won with it :P – David Mulder – 2014-04-02T16:10:32.937

4

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

Geobits

Posted 2014-01-14T07:07:46.443

Reputation: 19 061

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

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

yayestechlab

Posted 2014-01-14T07:07:46.443

Reputation: 37

In fact, it will win by 361 points in both cases. – Joe Z. – 2014-04-26T18:03:54.130

Actually, I'll have to take that back, it doesn't follow spec. The AI is supposed to be stateless. It's only actually supposed to print one thing given the state of the board, and you've made it print two (1 1 and pass). – Joe Z. – 2014-04-29T22:53:10.560

@JoeZ. Fixed it. Wouldn't have compiled anyway. – yayestechlab – 2014-05-04T15:43:14.770

That will always print 1 1, actually, since the program is always run anew every time the board changes. – Joe Z. – 2014-05-04T17:51:35.350

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

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

Ypnypn

Posted 2014-01-14T07:07:46.443

Reputation: 10 485

2This doesn't guarantee a legal move. If the first available space has no liberties, it can't be played. For instance, if this AI played itself: After the first row of alternating pieces, 1 1 would be captured by white (now empty) and could not be played by black on the next turn. – Geobits – 2014-05-05T15:06:34.853