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, and2
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, and2
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.
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