How to use Manhattan Distance to solve this game?

Question

Each player takes turns, removing 1 or 2 bananas from a basket of 50 bananas. The player who empties the basket wins.

What are the weights that should be used for the distances, and what should the matrix size be? Should the matrix change every time someone makes a move? Should player 1's moves be horizontal and player 2's moves vertical?

Thanks for the read

For more background information about this sort of game, see https://en.wikipedia.org/wiki/Nim or search Stack Overflow for "nim game". — m69's been on strike for years, Jun 25 '17 at 20:28

score 4 · Accepted Answer · answered Jun 25 '17 at 12:24

I'm not sure why you'd specifically want to use dynamic programming and/or Manhattan distance for this puzzle. This is a game for which you can find a fixed solution.

If you go first and there are 3 bananas, no matter what you play, I win. You pick one, I pick two, and vice versa. If there are six bananas, the same logic allows me to reduce the game to the 3 banana case. In fact, for any 3n bananas, I can reduce the game to 3(n-1) bananas. If the number of bananas isn't a multiple of three, then you can make it a multiple of three (By removing either one or two bananas), and ensure victory.

For k bananas, you always remove k % 3. If k % 3 == 0, you've lost unless your opponent makes a mistake, so play whatever you like. That's it.

score 1 · Answer 2 · answered Jun 25 '17 at 18:00

I agree with @pdpi but if you insist of solving this problem with dynamic programing, then you should do something like this :

f(left_in_the_basket, mine)
    if left_in_the_basket is 2 && turn is mine:
        return 1
    if left_in_the_basket is 1 && turn is mine:
        return 1
    if left_in_the_basket is 2 && turn is not mine:
        return -1
    if left_in_the_basket is 1 && turn is not mine:
        return -1
    return max (f(left_in_the_basket - 1, not mine), f(left_in_the_basket - 2, not mine))

How to use Manhattan Distance to solve this game?

2 Answers2