TC MoneyGame

From Algorithmist
Jump to navigation Jump to search

Summary[edit]

You're asked to analyze a 2-player game. The rules of the game involve coins and their values. Your task is to determine, if both players play optimally, how much each player wins/loses in the game.

From TopCoder Single Round Match 343.

Hints[edit]

  • Note that the game is symmetric, there are at most 10 coins of each of three denominations, and whatever is not held by either player, is in the pot. Hence there are no more than positions.
  • See the Combinatorial Game Theory category for techniques on solving this (minimax search; also use dynamic programming).