#10838 - The Pawn ChessSolved 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) |
Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By
|