Tree Data Structures & Minimax Algorithm for Games

[wololo]

Homework Statement

Homework Equations

Tree data structures.
I think it might also have something to do with minimax algorithm, but it was only mentioned once and never discussed extensively in class so I doubt it is required.

The Attempt at a Solution

[/B]
If both players play as well as they can, the game will end in a draw. Player 1 will always have the option of choosing to draw rather than lose.

However I can't find a function that given n sticks will tell me who will win. For 5, 10 and other multiples of 5, player 2 necessarily wins but what about the other cases? How can I find a single formula that will necessarily tell me who will win, given that they play well?

 

[BvU]

Misunderstanding: you can't end in a draw.

 

[wololo]

Misunderstanding: you can't end in a draw.

"The player who removes the last match wins, except if there is only one match left, in which case the game is a draw." All the paths that end in 1 in the game tree are draws.

 

[BvU]

Oops, sloppy reading...
I remember something about analyzing games like this: start from the end situation and work backwards...
Your "multiples of 5" points that way. So player 2 will always work towards multiples of 5. So will 1. That way you have pinned down "playing well". Apparently you really want the other to start when playing this game, unless n is a multiple of 5 plus 2 or 3.