Dot Game and Dynamic Programming
I am trying to solve a dynamic programming variant of the dot play.
The regular dot game is played with a line of dots. Each player takes one or two dots at their end of the line, and the person left without dots to win.
In this version of the game, each point has a different meaning. Each player takes alternating turns and takes either a point at both ends of the line. I want to come up with a way to use dynamic programming to find the maximum amount guaranteed by the first player.
I'm having trouble grabbing my head around this and trying to write a repeat for a solution. Any help is appreciated, thanks!
a source to share
Take a look at this site: http://people.csail.mit.edu/bdean/6.046/dp/ , especially issue number 10:
Optimal game strategy. Consider a series of n coins of values v (1) ... v (n), where n is even. We play a game against the opponent with alternating turns. On each turn, the player chooses the first or last coin from the line, removes it from the line forever, and gets the value of the coin. Determine the maximum possible amount of money that we can beat if we move first.
This is exactly what you want if I read your post correctly. The solution is pretty simple and it explains very well in my opinion.
a source to share