Win rates for different "strategies" in the childrens game Obstgarten (orchard)

obstgarten.py

from abc import ABC, abstractmethod
from typing import List
from random import randint
from enum import Enum

Fruits = List[int]
NUM_FRUITS = 4


class PickFruit:
    i: int

    def __init__(self, i: int):
        self.i = i

    def __str__(self) -> str:
        return f"pick fruit {self.i + 1}"


class Basket:
    def __str__(self) -> str:
        return "basket"


class Crow:
    def __str__(self) -> str:
        return "crow"


Action = PickFruit | Crow | Basket


class Strategy(ABC):
    @abstractmethod
    def pick(self, fruits: Fruits) -> Fruits:
        ...


class PickFirstAvailable(Strategy):
    def pick(self, fruits: Fruits) -> Fruits:
        num_picked = 0
        i = 0
        while num_picked < 2:
            if fruits[i] >= 1:
                fruits[i] -= 1
                num_picked += 1
            else:
                i += 1

        return fruits


assert PickFirstAvailable().pick([3, 2, 0, 0]) == [1, 2, 0, 0]
assert PickFirstAvailable().pick([1, 1, 2, 0]) == [0, 0, 2, 0]
assert PickFirstAvailable().pick([0, 1, 2, 0]) == [0, 0, 1, 0]
assert PickFirstAvailable().pick([0, 0, 0, 5]) == [0, 0, 0, 3]


class PickHighest(Strategy):
    def pick(self, fruits: Fruits) -> Fruits:
        num_picked = 0
        while num_picked < 2:
            index_max = max(range(len(fruits)), key=fruits.__getitem__)
            fruits[index_max] -= 1
            num_picked += 1

        return fruits


assert PickHighest().pick([3, 5, 0, 0]) == [3, 3, 0, 0]
assert PickHighest().pick([1, 1, 2, 0]) == [0, 1, 1, 0]
assert PickHighest().pick([0, 6, 0, 6]) == [0, 5, 0, 5]


class PickLowest(Strategy):
    def pick(self, fruits: Fruits) -> Fruits:
        def index_min(fs):
            index = None
            min_count = None
            for i in range(0, NUM_FRUITS):
                if fs[i] > 0 and (index is None or fs[i] < min_count):
                    index = i
                    min_count = fs[i]

            return index

        num_picked = 0
        while num_picked < 2:
            i = index_min(fruits)
            fruits[i] -= 1
            num_picked += 1

        return fruits


assert PickLowest().pick([3, 5, 0, 0]) == [1, 5, 0, 0]
assert PickLowest().pick([0, 5, 2, 0]) == [0, 5, 0, 0]


class PickRandom(Strategy):
    def pick(self, fruits: Fruits) -> Fruits:
        num_picked = 0
        while num_picked < 2:
            i = randint(0, NUM_FRUITS - 1)
            if fruits[i] > 0:
                fruits[i] -= 1
                num_picked += 1

        return fruits


def random_action() -> Action:
    n = randint(0, 5)
    if n <= 3:
        return PickFruit(n)
    elif n == 4:
        return Basket()
    return Crow()


class GameResult(Enum):
    Win = 0
    Lose = 1


def simulate_game(strategy: Strategy) -> GameResult:
    fruits = [10] * NUM_FRUITS
    crow_pieces = 0

    while sum(fruits) > 0 and crow_pieces < 9:
        action = random_action()
        match action:
            case PickFruit(i=i):
                fruits[i] = max(0, fruits[i] - 1)
            case Crow():
                crow_pieces += 1
            case Basket():
                if sum(fruits) <= 2:
                    fruits = [0, 0, 0, 0]
                else:
                    num_before = sum(fruits)
                    fruits = strategy.pick(fruits)
                    num_after = sum(fruits)

                    assert num_after + 2 == num_before

        # print(f"{str(action):<20} {str(fruits):<15} {crow_pieces}")

    if sum(fruits) == 0:
        return GameResult.Win
    else:
        return GameResult.Lose


def run_games(n: int, strategy: Strategy):
    wins = 0
    for _ in range(n):
        result = simulate_game(strategy)
        if result == GameResult.Win:
            wins += 1

    print(
        f"Success rate of strategy {type(strategy).__name__:<20} = {float(wins)/n * 100.0:.1f} %"
    )


num_games = 100000
for strategy in [PickLowest(), PickFirstAvailable(), PickRandom(), PickHighest()]:
    run_games(num_games, strategy)

# Prints:
# Success rate of strategy PickLowest           = 53.3 %
# Success rate of strategy PickFirstAvailable   = 56.7 %
# Success rate of strategy PickRandom           = 63.1 %
# Success rate of strategy PickHighest          = 68.4 %