11
\$\begingroup\$

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.

\$\endgroup\$
  • 7
    \$\begingroup\$ Ok, waiting for all other submissions and then write my own in order to beat them - should be possible since the solutions are deterministic. \$\endgroup\$ – Howard Jan 14 '14 at 7:50
  • 1
    \$\begingroup\$ It seems playing in ko such that the previous position is repeated is allowed but leads to immediate draw (since it causes a loop). Interesting... \$\endgroup\$ – FireFly Jan 14 '14 at 11:04
  • 2
    \$\begingroup\$ Looks 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. \$\endgroup\$ – Victor Stafusa Jan 19 '14 at 6:31
  • 1
    \$\begingroup\$ Why 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). \$\endgroup\$ – Geobits Mar 6 '14 at 3:09
  • 1
    \$\begingroup\$ How does input work? stdin or command line arguments? \$\endgroup\$ – Ypnypn May 4 '14 at 16:35
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Your code will always lose against anyone that makes any play against it. Still, nice base-case answer. \$\endgroup\$ – Joe Z. Jan 14 '14 at 17:09
  • 1
    \$\begingroup\$ @JoeZ. And from the looks of it he won with it :P \$\endgroup\$ – David Mulder Apr 2 '14 at 16:10
4
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ In fact, it will win by 361 points in both cases. \$\endgroup\$ – Joe Z. Apr 26 '14 at 18:03
  • \$\begingroup\$ 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). \$\endgroup\$ – Joe Z. Apr 29 '14 at 22:53
  • \$\begingroup\$ @JoeZ. Fixed it. Wouldn't have compiled anyway. \$\endgroup\$ – yayestechlab May 4 '14 at 15:43
  • \$\begingroup\$ That will always print 1 1, actually, since the program is always run anew every time the board changes. \$\endgroup\$ – Joe Z. May 4 '14 at 17:51
1
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ This 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. \$\endgroup\$ – Geobits May 5 '14 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.