Play duck game vs optimal computer

ducks.py

from typing import Generator, Optional


BOARD_SIZE = 10


def move(board: int, squares: tuple[int]) -> int:
    for sq in squares:
        board = (1 << sq) ^ board
    return board


def get_moves(board: int) -> Generator[tuple[int], None, None]:
    i = 0
    while board:
        if board & 1:
            yield i,
        if board & 3 == 3:
            yield i, i + 1
        board >>= 1
        i += 1


def look_forward(board: int) -> tuple[list[tuple[tuple[int], int, int]], list[tuple[int]]]:
    moves: list[tuple[tuple[int], int, int]] = []
    mv: tuple[int]
    guaranteed_win: list[tuple[int]] = []
    for mv in get_moves(board):
        new: int = move(board, mv)
        next_move: tuple[int]
        if new == 0:
            moves.append((mv, 0, 1))
            continue
        if new.bit_count() == 1:
            moves.append((mv, 1, 0))
            guaranteed_win.append(mv)
            continue
        win: int = 0
        loss: int = 0
        yep = 1
        for next_move in get_moves(new):
            now: int = move(new, next_move)
            if now == 0:
                win += 1
                continue
            m: tuple[int]
            w: int
            l: int
            a, b = look_forward(now)
            for m, w, l in a:
                win += w
                loss += l
            yep &= bool(b)
        moves.append((mv, win, loss))
        if loss == 0:
            guaranteed_win.append(mv)
        if yep:
            guaranteed_win.append(mv)
    return moves, guaranteed_win


def first_guaranteed_win(board: int) -> Optional[tuple[int]]:
    for mv in get_moves(board):
        new: int = move(board, mv)
        next_move: tuple[int]
        if new == 0:
            continue
        if new.bit_count() == 1:
            return mv
        yep = 1
        for next_move in get_moves(new):
            now: int = move(new, next_move)
            if now == 0:
                continue
            m: tuple[int]
            w: int
            l: int
            b = look_forward(now)[1]
            yep &= bool(b)
        if yep:
            return mv
    return None


def choose_move(board: int) -> tuple[tuple[int], float]:
    # all_moves, winning = look_forward(board)
    winning = first_guaranteed_win(board)
    if winning:
        return winning, 1.0
    all_moves, _ = look_forward(board)
    return max({m: win / (win + loss) for m, win, loss in all_moves}.items(), key=lambda x: x[-1])


def print_board(board: int) -> None:
    i = BOARD_SIZE - 1
    while i >= 0:
        print(i % 10, end="")
        i -= 1
    print()
    i = BOARD_SIZE - 1
    while i >= 0:
        j = (board >> i) & 1
        print("\033[1;34m" * j, j, end="\033[0m", sep="")
        i -= 1
    print()


def check_if_valid(board: int, sq: tuple[int]) -> int:
    try:
        if len(sq) == 1:
            return board >> sq[0]
        elif len(sq) == 2:
            sq = tuple(sorted(sq))
            if sq[1] - sq[0] != 1:
                return 0
            return (board >> sq[0]) & 3 == 3
    except:
        return 0


def computer_turn(board: int) -> int:
    mv, rat = choose_move(board)
    new_board = move(board, mv)
    print(f"Computer chose \033[1;31m{','.join(map(str, mv))}\033[0m (win {int(rat * 100)}%)\n")
    print_board(new_board)
    return new_board


def human_turn(board: int) -> int:
    sq = -1,
    while not check_if_valid(board, sq):
        try:
            sq = tuple(map(int, input(" > ").split(",")))
        except:
            pass
    new_board = move(board, sq)
    print()
    print_board(new_board)
    return new_board


def initialise_board() -> int:
    return (1 << BOARD_SIZE) - 1


def main() -> None:
    b = initialise_board()
    print_board(b)
    print()
    while b != 0:
        b = human_turn(b)
        if b == 0:
            print("\033[1;31mYou lose.\033[1;0m")
            break
        print()
        b = computer_turn(b)
    else:
        print("\033[1;33mYou win.\033[1;0m")


main()