JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Terminal positions | Reply

We can see that n = 1, 3, 4 are winning positions for the first player, because he can simply take all the coins. For n=0 and 2 there are no possible moves -- the game is finished -- so these are the losing positions for the first player, because he can not make a move from them.

IMO for n=2 there is the move -- to take 1 coin (which leads to winning position for opponent), so, n=2 probably is not terminal position, but just the loosing one.
Re: Terminal positions (response to post by gorbunov) | Reply
Yes, you are correct. Thanks.
Re: Terminal positions (response to post by rasto6sk) | Reply
And thank you for the article. Sometimes I found myself stumped by the problems like LongLongNim, because neither DP, nor greedy or some other
"standard" method works on them, and a kind of deep mathematical background is required to get them right. Your article gives ideas that probably will help.
Re: Terminal positions (response to post by rasto6sk) | Reply
@rasto6sk
your tutorial indeed is helpful. i still could not understand one thing, what exactly does "terminal position" mean. for the game of coins you described wherein player can take {1,3,4} coins.. how does one find terminal positions.
Re: Terminal positions (response to post by dchamp) | Reply
A terminal position is a position from which no moves are possible (that is, the game ends when that position is reached, and a winner is declared). In the example of {1,3,4} coins, the only position in which the game ends is when there are 0 coins left. In any other position, there is at least one move available to the player, so the position is not terminal. If the possible moves were {3,5,7}, then positions 0, 1 and 2 are terminal, as you legally can't take coins in that scenario.
Re: Terminal positions (response to post by connect4) | Reply
Thanks for your quick reply connect4
your explanation makes sense to me. but then the author has written "if we play the game with misers rule, we need to change only the behavior of terminal positions." he then has shown two different tables clarifying this, but in Table-2 he has changed behaviors of positions 0,1,2,3,7,8,9,10 out of which only 0 is terminal position. we have possible moves in other positions except '0', so why did he change their behaviors.
RSS