This problem is based on a reduced version of a little known game called Tonga. We'll
call this version PseudoTonga.
PseudoTonga is played by two players, Black and White, on a NxN
board, for some even N. Pieces are black and white stones a little
smaller than a square of the board. Players alternate turns, with Black
In each turn the player in turn places a stone on any empty
square. A square is said to be uncolored if it's empty and
is said to be black or white if it has a black or white
stone on it.
As the game goes on isles of each color will become
apparent. A Black isle is a group of solidly connected black
squares, each being orthogonally adjacent to at least one neighbor
black square. White isles are similar groups of white squares.
. . . . . .
. . W B . .
. B W W B .
. . . W B .
B W W . . .
. . B . . .
White has a four-square isle and a two-square isle. Black has four
one-square isles and one two-square isle.
The game stops when there is no room for a new stone. The total points
of each player are calculated as the sum of the squares of all
that player's isles' sizes.
W W B B
W B W W
B W B B
B W W B
In this example, White has 32+32+22=22 points
and Black has 32+22+22+12=18 points.
Getting to the problem, you will have to make a program that plays PseudoTonga
against the TopCoder server. The TopCoder server will play with a fixed strategy
If the board is empty, he plays in one of the 4 middle squares.
If its not empty, for each square the server calculates a score. The score
of a square is calculated in the following way: First simulate playing
in the square, then try every play the oponent (i.e., you) is allowed
to play and for each of those try playing again optimally. Compute the
best scenario you can achieve for the worst scenario your oponent can
leave you (do a minimax) and that's the score. The scenarios after the three moves (two server moves and one player move) are evaluated by assigning a score to each isle of area2*perimeter, where area is the number of squares in the isle and perimeter is the number of unoccupied squares adjacent to the isle (squares off the board don't count). The server's isles contribute positive points to the scenario, while the player's (your) isles contribute negative points. Finally, the server randomly selects a square which leads to the maximum score (in other words, ties are broken randomly).
For each game it will be randomly decided with 50%-50% probabilities who
You have to implement two methods init and move. First
init will be called with 3 ints, N, row and
col. N will be an even number between 6 and 16
representing the number of squares of each side of the board. row
and col will represent the row and column of the first play of the server
(both 0-based) if he was selected to start or will both be -1 if you
were selected to start. You have to return a int with
exactly two elements, the first one being the number of the row of your
first play and the second one being the number of the column of your first
play (both 0-based). For each subsequent turn move will be called
with two parameters row and col with a play from the server. In
each call you have to return a int with two elements, in the same
format as in init, representing your next move.
If at any point you return an invalid play (an int that does not have exactly
two elements or in which one of the numbers is less than 0 or greater than
N-1 or the square you play in is occupied), your program returns a runtime error or your
time is up, a stone of server's color will be put in each remaining square and points will be
awarded according to the resulting layout.
The number of points for a test case is the number of points you got minus the
number of points the server got when the game finished. Note that is possible to have
negative points for a test case. The points you get overall is the sum of the signed square
root of the points of each individual test. For example, if your individual points in the
5 test cases were:
3, -4, 0, -1 and 8
then your overall score is:
sqrt(3) + (-sqrt(4)) + sqrt(0) + (-sqrt(1)) + sqrt(8)
Note that this calculation is doing with floating point numbers, so having a score of sqrt(2) is
better than a sqrt(1), even though they are both 1 if truncated or rounded to an integer.
The time limit is 20 seconds and the memory limit is 64 megabytes.