guess_who.py

#!/usr/bin/env python3

from fractions import Fraction
from functools import lru_cache

# to examine what moves are chosen
trace=False

@lru_cache(maxsize=None)
def f(x, y):
	# chance of winning by guessing
	moves = [Fraction(1, y)]
	for n in range(1, y//2 + 1):
		# chance of winning after asking a question that selects or excludes n options
		moves.append(1 - (n * f(n,x) + (y-n) * f(y-n,x)) / y)
	pmax = max(moves)
	if trace:
		print(f'moves available at ({x},{y}):')
		print('',', '.join(str(m) for m in moves))
		ns = [i for i, p in enumerate(moves) if p == pmax]
		print('',f'best moves: {ns} p={pmax}')
	return pmax

# trace=True; f.cache_clear(); f(14,14)

for n in (4, 24, 14):
	print(f'For a Guess Who game of size {n}, the optimal player will win with p={f(n,n)}')