10838 - The Pawn Chess
This problem is reasonably complex, but an exhaustive memoized search of the state space will run in time. This problem will exercise your ability to do bitwise arithmetic. (In fact, memoization isn't strictly necessary - a simple brute-force search is enough to get accepted on the UVa OJ. Still, a memoized search is much faster.)
We are given a 4x4 chess board, consisting of only pawns, and we want to determine which player will win if the game is played optimally as well as how long it will take. Since there are 16 spots on the chess board, and each spot can only be in one of three states (empty, white, black), it is easy to see that is an upper bound to the total number of states. is just a little bit too much memory to run on the judges machine. However, there are quite a few restrictions on the state space, there are a total of 8 pieces, there are at most 4 white pieces and 4 black pieces, there can only be one white piece on the top row, and one black piece on the bottom row. While it's hard to count the actual size of the state space, it's easy to see that is quite a bit smaller than .
A better upper bound: If we have B black and W white pawns, there are ways to place the black pawns and then ways to place the white pawns. Summing over all possible B and W we get that there are 2267253 positions with at most 4 pawns of each color.
Since the state space is reasonably small, we can simply try to explore it all all and use memoization so that we avoid recomputation of identical states. A particularly nice encoding of the state space uses a pair of integers, one integer for the location of the black pieces, and another for the white pieces. We map the state of row zero column zero to the zeroth bit in the integer, row zero column one to the first bit, and in general row column to the bit.
At each state, we try every possible move and then recursively compute the optimal positions from each move. To each state we associate the optimal number of moves and winner as follows. If the optimal number of moves is and white wins, we associate , otherwise black wins so we associate . Then it's easy to find out the optimal move from state as a function of all its substates. The substates are easy to find by simply checking each position to see if it contains a pawn, and if so, if it can capture in either direction or move forward. Keep in mind that if we are going to lose, we want to play as long as possible, and that if we are going to win, we want to play as short as possible.
Make sure your encoding won't suffer from overflow, it's safe to use 64 bit integers, but you may have some problems with 32 bit ints.
- You can use hash_map to do state lookups efficiently.
2 .ppp .... .PPP .... ...p ...p pP.P ...P
white (7) black (2)