3
\$\begingroup\$

Working on the problem of sum game. Suppose we have consecutive numbers from 1 to n, and an expected sum number, there are two players, and each player tries to select one number in turn (once a number is selected by one player, the other player cannot select it again), and the selected numbers are summed together. The player who first get a sum which is >= expected sum wins the game. The question is trying to find if first player has a force win solution (means no matter what numbers 2nd player will choose each time, the first player will always win).

For example, if we have numbers from 1 (inclusive) to 5 (inclusive) and expected sum is 7, if the first player select 1, no matter what the 2nd player select, in the final the first player will always win.

Here is my code and my idea is, each player tries to see if select the largest number can win -- if not then selecting the smallest available (means not having been selected) number -- which gives the current player max chance to win in the following plays, and give the opponent player minimal chance to win in the following plays.

I think the above strategy is optimum for player 1 and player 2, if in this strategy, player 2 cannot win, it means player 1 could force win.

I want to review the code, and also if my thought of the algorithm (strategy) to resolve the problem is correct?

def try_best_win(numbers, flags, current_sum, expected_sum, is_first_player):
    if current_sum + numbers[-1] >= expected_sum:
        return is_first_player == True
    else:
        for i in range(len(flags)):
            # find the next smallest number
            if flags[i] == False:
                flags[i] = True
                return try_best_win(numbers, flags, current_sum+numbers[i], expected_sum, not is_first_player)

if __name__ == "__main__":
    print try_best_win([1,2,3,4,5], [False]*5, 0, 6, True) #False
    print try_best_win([1,2,3,4,5], [False]*5, 0, 7, True) #True
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't know if I understand your first test, Player 1 goes first and chooses 5, P2 then must loose as 5 + 1 = 6, and every other move is > 6. So it should be a WIN for player 1. \$\endgroup\$ – Dair Oct 23 '16 at 6:22
  • 1
    \$\begingroup\$ @Dair Player 2 will certainly win. If P1 chooses 5, then P2 chooses 1, then P2 wins by meeting or exceeding 6, and P1 loses. \$\endgroup\$ – 200_success Oct 23 '16 at 6:30
  • 1
    \$\begingroup\$ @200_success: Oh, ok. It seems I had the two switched around, I thought since P2 would go to 6 or greater it would lose. I feel like this is some sort of Nim variant with a nice solution... \$\endgroup\$ – Dair Oct 23 '16 at 6:32
  • 2
    \$\begingroup\$ Are you sure the indentation is right? As written, once flag becomes True it stays True forever, and recursion doesn't happen. \$\endgroup\$ – vnp Oct 23 '16 at 6:38
  • \$\begingroup\$ @Dair, which example do you mean? If you mean number from 1 to 5, and expected number is 6, player 1 cannot force win. My algorithm works in this way in this example, player 1 choose 1 (since player 1 see it could not win by choosing 5), then player 2 see it could win by choosing 5 in next round, then player 2 wins. If anything unclear, please feel free to advise. \$\endgroup\$ – Lin Ma Oct 23 '16 at 7:15
3
\$\begingroup\$

Prelude

Firstly, you might want to ask on Math Stack Exchange if there is any analysis. This game looks a lot like Nim and a variant of the subtraction game (mentioned later in the article). The subtraction game in particular has a really nice and cheesy solution. The major difference is that you prevent taking any number away twice.

On to the code!

Default values

When you start a game, the first player to go is, well, the first player. I don't think a user really wants to waste their time typing it. A similar argument goes for current_sum. You shouldn't really need to specify it. Hide it make the default value 0. so:

def try_best_win(numbers, flags, expected_sum, current_sum=0, is_first_player=True):

Is something you should probably do.

You don't really need flags.

You have a list of numbers (which btw, is a generalization of your problem statement, why?). Each one of these numbers represents a move you cannot play again. So in the recursive call:

  1. Apply the move
  2. Remove the move from numbers
  3. Recurse on the new set of numbers.

This is equivalent to what you are doing and removes the flag variable entirely.

Bugs

There are bugs in your program. @Mathias provides an example as to why your code is wrong. You should consider @vnp's comment. The typical game tree traversal involves a reduction phase of some sort. As another hint, you should really review slide 27/39 of these slides. (Ask yourself, what does your code do differently than what is on that slide!)

Abstraction (and more hints)

You can actually abstract a lot of this. See my question here for a general framework on solving these games. A general framework declutters a lot of code. However, as mentioned in the prelude, a mathematical analysis may (or may not) provide a better solution than the general framework.

\$\endgroup\$
  • \$\begingroup\$ Thanks Dair for sharing the slides and I read slides 27/39 -- all nice slides but not exactly the issue I met with, and yes there is a bug when number are [1, 2, 3, 4, 5, 6] and expected sum is 12, my algorithm cannot find player 1 could force win if 5 or 6 is first chosen by player 1, but what is wrong logic with my posted code/logic -- I think always choose smallest (if cannot win immediately by choosing the largest available) is the best strategy of force win? \$\endgroup\$ – Lin Ma Oct 23 '16 at 21:42
  • 1
    \$\begingroup\$ @LinMa: At a quick glance, it appears your code implements the strategy you suggest. Your strategy is not the optimal strategy. It's hard to elaborate as the counter example Mathias provides is essentially a proof that your strategy is non-optimal. I don't know of any obvious mathematical way to reduce the problem. I would advise you try to prove some stuff about the subtraction game and make generalizations and ask math stackexchange to see if they can generalize your results. \$\endgroup\$ – Dair Oct 23 '16 at 22:24
  • \$\begingroup\$ Thanks Dair. Actually I write a recursive algorithm before, which works by trying to see if the opponent could force win, if opponent cannot force win, then current player will win (similar to the principle in the game programming slides -- but it sounds a bit boring since it works for all kinds of problems and I just want to see if any optimization I can make for this specific problem), recursive solution works for your example, but I want to optimize it by trying to see if O(n) solution exists, \$\endgroup\$ – Lin Ma Oct 23 '16 at 23:03
  • \$\begingroup\$ (cont'd) so it is why I want to find some kinds of magic or heuristic solution (as I posted above). If you have to thought why my posted strategy does not work, please share. (at the same time, I will ask to math.exchange) :) \$\endgroup\$ – Lin Ma Oct 23 '16 at 23:03
  • \$\begingroup\$ Thanks for all the help Dair, mark your reply as answer. \$\endgroup\$ – Lin Ma Oct 27 '16 at 5:50
2
\$\begingroup\$

The parameters of the function are a bit verbose for the user. You should define an helper function that will provide the boilerplate:

def first_player_wins(numbers, target):
    flags = [False] * len(numbers)
    return try_best_win(numbers, flags, 0, target, True)

So you can call:

if __name__ == '__main__':
    first_player_wins([1, 2, 3, 4, 5], 6)
    first_player_wins([1, 2, 3, 4, 5], 7)

Your iteration can also be simplified by looping directly over the elements of flags: for flag in flags:. But since you also need i to modify it, you may want to use enumerate:

for i, flag in enumerate(flags):
    if not flag:
        flags[i] = True
        ...

Lastly, your logic is way too simple; as first_player_wins([1, 2, 3, 4, 5, 6], 12) returns False but player 1 can force a win by picking 5 or 6 as its first number.

\$\endgroup\$
  • \$\begingroup\$ Thanks Mathias, nice catch for the bug when number are [1, 2, 3, 4, 5, 6] and expected sum is 12, my algorithm cannot find player 1 could force win if 5 or 6 is first chosen by player 1, but what is wrong logic with my posted code/logic -- I think always choose smallest (if cannot win immediately by choosing the largest available) is the best strategy of force win? \$\endgroup\$ – Lin Ma Oct 23 '16 at 21:38
  • 1
    \$\begingroup\$ @LinMa I think Dair provided enough pointer to get you on tracks. \$\endgroup\$ – 409_Conflict Oct 23 '16 at 21:41
  • \$\begingroup\$ Thanks Mathias, I read his slides, but it is just general method of game algorithm programming, not exactly my specific issue. Why my strategy will fail in the case you mentioned? The basic assumption of my algorithm is, choose smallest will give least chance for opponent to win, which give himself/herself to win, what is wrong with the assumption here? \$\endgroup\$ – Lin Ma Oct 23 '16 at 21:45
  • 1
    \$\begingroup\$ The thing is that I don't really know the specifics of how it should be. It just happened that I tried to use a number slightly larger than the maximum of usable numbers to see if picking a big one could help change the outcome computed by your program. I’m not entirely sure how or why it works. \$\endgroup\$ – 409_Conflict Oct 23 '16 at 21:51
  • \$\begingroup\$ Thanks Mathias, actually I write a recursive algorithm before, which works by trying to see if the opponent could force win, if opponent cannot force win, then current player will win (similar to the principle in the game programming slides -- but it sounds a bit boring since it works for all kinds of problems and I just want to see if any optimization I can make for this specific problem), recursive solution works for your example, but I want to optimize it by trying to see if O(n) solution exists, \$\endgroup\$ – Lin Ma Oct 23 '16 at 21:58
1
\$\begingroup\$

You should never have to compare a boolean expression to True in python. Just use:

return is_first_player

and

if not flags[i]:
\$\endgroup\$
  • \$\begingroup\$ Thanks Graipher, thanks for the advice and I found there is a bug when number are [1, 2, 3, 4, 5, 6] and expected sum is 12, my algorithm cannot find player 1 could force win if 5 or 6 is first chosen by player 1, but what is wrong logic with my posted code/logic -- I think always choose smallest (if cannot win immediately by choosing the largest available) is the best strategy of force win? \$\endgroup\$ – Lin Ma Oct 23 '16 at 21:40
  • \$\begingroup\$ BTW, I fixed my bug here, if you have interest, we can continue discuss there => codereview.stackexchange.com/questions/145393/… \$\endgroup\$ – Lin Ma Oct 27 '16 at 5:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.