#10838 - The Pawn Chess

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:dynamic programming
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)

Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By PHPGraphLib - Click For Official Site