Game where two players take turns picking numbers until a target sum

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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

return is_first_player

and

if not flags[i]: