#10838 - The Pawn Chess

Solved By:	wesley
Theory Difficulty:	medium
Coding Difficulty:	medium
Algorithms Used:	dynamic programming recursion
Solution Description:	This is a fairly standard minimax game playing problem. There are fewer than 3^16 states, so you can store the result of the game for each possible configuration. Keep a 3^16 array for each colour. So, w[s] is the number of moves before white wins (or loses) given state s. b[s] is analogous for black. Your state should be a base-3 encoded number where each ternary digit corresponds to one cell on the board. w[s] > 0 means that white will win on state s in w[s] moves. w[s] < 0 means that white will lose on state s in -w[s] moves. w[s] = 0 means that white has no valid move in state s. Write a recursive function that takes a state, finds all possible moves, and chooses the best one. Memoize your results in w[] and b[]. The two base cases for your recursion are: 1) The current player has a winning move (return 1) 2) The current player has no moves (return 0)