Takeaway: Solution

Problem: Takeaway
Whiteboard: Harder
Challenge: Medium
Concepts: Game Theory
Download: takeaway-solution.zip

This demonstrates a common strategy for writing game AIs, as both players are trying to make their best possible move.

A player can win if their opponent has no winning moves (and this is recursive definition, so the opponent can win the next move if the player has no winning replies).

We can solve this recursively. The can_win function takes the number of stones on the board. If the active player cannot move, they cannot win (they immediately lose; this is our base case). Otherwise, we try each our 3 possible moves; if making that move cause our opponent to lose, we win.

takeaway.py

def can_win(n):
    """Can this player win takeaway?"""

    # START SOLUTION

    # If this player cannot move, opponent wins
    if n < 2:
        return False

    # Try all of the legal moves
    for move in [2, 3, 5]:

        # If opp can't win if we made this move, we win
        if not can_win(n - move):
            return True

    # None of our moves kept opp from winning, so we lose
    return False

Dynamic Programming

This solution, while correct, isn’t as efficient as possible.

It will recalculate endings that it has already calculated (for example, when solving for n of 10, it will consider the outcome of 5 several times, as there are different ways we can get from 10 stones to 5 stones: one if player #1 removes 5, once if player #1 removes 2 and player #2 removes 3, and once if player #1 removes 3 and player #2 remove 2.

This is more work than needed — it should only have to calculate the outcome of 5 once.

We can solve this with a technique known as memoization, where you could remember the outcome of a particular board.

Here, we memoize the outcome of calling our function.

We first make a dictionary to hold the cache results. This will contain {num-stones: True-if-can-win, ...}:

cache = {}

Then we use that cache in a dynamic version of the function:

takeaway.py

def can_win_dynamic(n):
    """Can this player win takeaway?"""

    if n in cache:
        return cache[n]

    # If this player cannot move, opponent wins
    if n < 2:
        return False

    # Try all of the legal moves
    for move in [2, 3, 5]:
        they_could_win = can_win_dynamic(n - move)

        # If opp can't win if we made this move, we win
        if not they_could_win:
            cache[n] = True
            return True

    # None of our moves kept opp from winning, so we lose
    cache[n] = False
    return False

For larger values of n, this makes a huge difference. For example, for 50 stones using the dynamic version, the can_win function is called 110 times. With the regular, non-dynamic version, it’s called 2,305,817 times!