Problem H
Lines Of Action

Lines Of Action is a two-player game that is played on an $8$-by-$8$ board (e.g. a chess board). The first player is designated the color black, and the second player the color white. Each player has $12$ tokens in his or her respective color. In the initial setup, the black tokens are lined up along the top and bottom rows, and the white tokens are lined up along the left and right columns, as depicted in Figure (a) below.

The black player begins. A move consists of choosing one of your pieces and choosing a direction (north, northeast, east, southeast, south, southwest, west, or northwest) to move it in. The number of steps the piece can move in a certain direction is the same as the number of tokens (both black and white) on the board along the line of movement. A piece can jump past pieces of its own color, but it cannot jump past pieces of the opposite color. However, it can capture pieces of the opposite color by landing on them. Captured pieces are taken out of play. For example, in Figure (b) below, the white piece in row $5$, column $5$, has two possible moves: it can either move to row $8$, column $2$, or it can capture the black piece in row $1$, column $5$. Moving in all other directions would cause it to either land outside the board, jump past a black token, or land on a fellow white token.

(a) Initial board setup

    

(b) Making a move

The goal of the game is to collect all your remaining tokens into one connected component. The game squares are considered to connect vertically, horizontally, and diagonally, so in Figure (b) above, both players have three components. Note that if all but one of a player’s tokens are captured, this player automatically wins since that player’s only remaining piece constitutes a single connected component. If a move causes both players to simultaneously fulfil the win conditions, the player who made the move wins. If a situation arises where the player to move has no possible moves, the game is considered a draw.

Your Lines of Action-playing program will be playing against the judges’ player. The strategy of the judges’ player will be to simply pick one of its possible moves randomly (giving each possible move equal probability). In order to get accepted, you must manage to win the game within $100$ moves. Games exceeding $100$ moves will be considered draws.

Interaction

Your program will first get an integer indicating the color your program is playing ($0$ for black, $1$ for white). Then, the game begins. When it is your turn, you make a move by writing a line consisting of four space-separated integers $r_1$, $c_1$, $r_2$ and $c_2$ (all between $1$ and $8$, inclusive) to standard output, where $(r_1, c_1)$ indicates the row and column of the piece to be moved, and $(r_2, c_2)$ indicates the row and column of the destination position. When it is your opponent’s turn, you can expect a line containing four space-separated integers on standard input, representing a valid move for the opponent. Your program must detect that the game has ended (either due to a player winning, due to a player not having any possible moves, or due to $100$ moves having been made) by itself. When this has happened, the interaction ends and your program must terminate.

Remember to flush standard output after making a move!

0

8 2 6 4

6 1 8 3

1 2 3 4

6 8 8 6

1 4 5 4

3 8 1 6

8 4 4 4

3 1 1 3

1 5 3 5

8 6 7 7

1 7 5 3

7 1 8 2

8 5 6 5

8 2 8 6

8 7 4 3