JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums News, Programs & Events Discussions Algorithm Games (Article) Terminal positions
 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 @rasto6skyour 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 connect4your 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.
 Forums News, Programs & Events Discussions Algorithm Games (Article) Terminal positions Previous Thread  |  Next Thread