| | In the game of Reversi, players take turns placing chips on a 2D board.
Each player, on their turn, must place a piece into an empty cell on the board, in such a position that there exists at least one straight (horizontal, vertical, or diagonal) line between the new piece and another piece belonging to the player, with one or more opponent pieces between them. After placing the piece, the player captures (flips) all pieces between the new piece and any anchoring pieces in any of the 8 possible straight lines.
The goal of the game is to have as many of your pieces on the board as possible by the time the board is filled.
In classical play of the game, 2 players compete on an 8x8 board. In our version of the game, there will be 3 or 4 players, for odd and even boards, respectively, and the board size will be square, from 7x7 up to 12x12.
You will control the first player. The remaining players will all be controlled by the computer, and will execute moves according to a predefined strategy. Each additional player will have their own strategy which will remain constant for that test case. Each test case will have unique strategies used by the opponents. That is, strategies will not, in general, be re-used across multiple test cases.
A computer strategy consists of a weight that is assigned to each cell of the board. The computer then evaluates, for each potential move, the relative weight of the board owned by the current player as compared to the other players, and makes the move that results in the best weight ratio. For instance, if the total weight of cells owned by the player would be 5, and the weight of cells owned by other players would total 20, then that potential move is calculated to have a value of 0.25.
Strategies were pregenerated using a genetic algorithm. First, a set of 100 random strategies is created where each cell is given a weight from -50.0 to 50.0. Then, several games are simulated between randomly chosen opponents, with each player being awarded points based on the result of the game. For 3-player games, the winner is awarded 4 points, and 2nd place gets 1 point, 3rd place gets no points. For 4-player games, 9/4/1/0 points are awarded. Then, a new set of random strategies is created from the first set. Each strategy is created by selecting two of the initial strategies, with probability proportional to their total score accumulated during simulated play. Then, each cell of the new strategy randomly takes the weight from one of the two parent strategies, and adds a random value in the range -0.5 to 0.5. The set of child strategies then runs through the process again, and so on, for 50 to 100 generations. Each test is generated by running this process with a new initial population, and then selecting strategies uniformly, with replacement from the final 100.
Whenever a player has no legal moves, that player's turn is skipped. In the case of player 1 not having any moves, the submission's method is not called. If ever all players are unable to make a legal move, the game ends at that point.
Your method will be called when it is your turn to move. You will be given a String[] representing the current layout of the board. Each element of the input represents one row of the board. Each character represents a single cell. Characters '1', '2', etc, indicate that a player has captured that cell, while a '.' indicates an empty cell. You should return a int[] with two elements. Element 0 indicates the column, and element 1 the row in which you wish to move. The upper left corner of the board is (0,0).
Scoring for each test case is calculated as (# owned cells) * (# players) / boardSize. So, in a 3 player game on a 7x7 board, if you own 20 cells at the end of the game, your score would be 20 * 3 / 49 = 1.224. Your final score is the sum of your raw scores for each test case.
A visualizer is available to assist with the problem.
|