AI: Who wins the take-away game?

Solve a whole game by search with memoization.

What to build

A program that decides who wins a take-away game with perfect play, and gives a winning first move.

Requirements

  • There are several heaps of stones and a set of allowed takes. A move removes an allowed number of stones from one heap that has at least that many. Players alternate; a player who cannot move loses.
  • Print first player wins: take T from heap H for the first winning move (smallest heap number from 1, then smallest take), or second player wins.

Input

Line 1: the heap sizes. Line 2: the allowed takes.

Output

One line.

Constraints

At most 3 heaps of at most 15 stones; takes between 1 and 15.

Example

Input:

5
1 2 3

Output:

first player wins: take 1 from heap 1

Why it works

With perfect play every position is either a win or a loss for the player to move, and search with memoization labels each position once, from the end of the game backwards.

Examples

Example 1 · Input
5
1 2 3
Expected output
first player wins: take 1 from heap 1
Example 2 · Input
4
1 2 3
Expected output
second player wins

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

A position is winning for the player to move if some move leads to a position that is losing for the opponent; a position with no moves is losing.

Hint 2

Memoize the result for each tuple of heap sizes, or the search repeats the same positions many times.

Solution

Show one correct solution (try it yourself first)
from functools import lru_cache

heaps = tuple(map(int, input().split()))
takes = sorted(set(map(int, input().split())))


def moves(state):
    for h, size in enumerate(state):
        for t in takes:
            if t <= size:
                yield h, t, state[:h] + (size - t,) + state[h + 1:]


@lru_cache(maxsize=None)
def wins(state):
    return any(not wins(nxt) for _, _, nxt in moves(state))


for h, t, nxt in moves(heaps):
    if not wins(nxt):
        print(f"first player wins: take {t} from heap {h + 1}")
        break
else:
    print("second player wins")

Lesson: Game playing with minimax →