Skip to content

Instantly share code, notes, and snippets.

@glostis
Created January 8, 2021 08:50
Show Gist options
  • Save glostis/ab882bc21286ac205468ad62940a350b to your computer and use it in GitHub Desktop.
Save glostis/ab882bc21286ac205468ad62940a350b to your computer and use it in GitHub Desktop.
import random
from copy import deepcopy
from collections import defaultdict
from itertools import product
from tqdm import tqdm
def play_game(size=3, verbose=False):
candidates = {
i: set(product(range(size * size), range(size * size))) for i in range(size * size)
}
to_play = {i: size * size for i in range(size * size)}
player = -1
grid = [[" " for _ in range(size * size)] for _ in range(size * size)]
fill_per_square = defaultdict(int)
count = -1
while any(len(c) > 0 for c in candidates.values()):
player = (player + 1) % (size * size)
count += 1
choices = candidates[player]
if verbose and count != 0 and count % (size * size) == 0:
print_grid(grid, size)
print()
if len(choices) == 0:
continue
choices_per_square = defaultdict(set)
for r, c in choices:
square = ((r // size) * size, (c // size) * size)
choices_per_square[square].add((r, c))
# Strategy: dumb, choose randomly from all choices
# choose_from = choices
# Strategy: choose from square that is most filled already
# max_square = list(choices_per_square.keys())[0]
# max_opponents = fill_per_square[square]
# choose_from = set()
# for square, opponents in fill_per_square.items():
# if square in choices_per_square:
# if opponents > max_opponents:
# max_opponents = opponents
# max_square = square
# choose_from = choices_per_square[max_square]
# elif opponents == max_opponents:
# choose_from.update(choices_per_square[square])
# Strategy: choose from square where the fewest choices are left for the player
min_square = list(choices_per_square.keys())[0]
min_choices = len(choices_per_square[min_square])
choose_from = choices_per_square[min_square]
for square, choices_ in choices_per_square.items():
if len(choices_) < min_choices:
min_choices = len(choices_)
min_square = square
choose_from = choices_per_square[min_square]
elif len(choices_) == min_choices:
choose_from.update(choices_per_square[square])
# Strategy: same as above, but choose choices that are also choices for other players
choices_count = defaultdict(int)
for choices_ in candidates.values():
for choice_ in choices_:
choices_count[choice_] += 1
new_choose_from = set()
max_count = 0
for choice_, count_ in choices_count.items():
if choice_ in choose_from:
if count_ > max_count:
max_count = count_
new_choose_from = set([choice_])
elif count_ == max_count:
new_choose_from.add(choice_)
choose_from = new_choose_from
r, c = random.sample(choose_from, 1)[0]
grid[r][c] = player + 1
to_play[player] -= 1
# Remove row from choices
choices -= set(product([r], range(size * size)))
# Remove column from choices
choices -= set(product(range(size * size), [c]))
# Remove square from choices
square_r = (r // size) * size
square_c = (c // size) * size
choices -= set(product(range(square_r, square_r + size), range(square_c, square_c + size)))
fill_per_square[(square_r, square_c)] += 1
# Remove (r, c) from choices of all players
for cc in candidates.values():
cc.discard((r, c))
return to_play
def print_grid(grid, size):
for i, line in enumerate(grid):
string = ""
for j, char in enumerate(line):
if j % size == 0 and j != 0:
string += "| "
string += f"{char} "
if i % size == 0 and i != 0:
print("-" * (len(string) - 1))
print(string)
def main(size=3):
nb_games = 10000
nb_wins = {i: 0 for i in range(size * size + 1)}
wins = {i: 0 for i in range(size * size)}
for _ in tqdm(range(nb_games)):
to_play = play_game(size=size)
nb_wins[sum(count == 0 for count in to_play.values())] += 1
for player, count in to_play.items():
if count == 0:
wins[player] += 1
for p, w in nb_wins.items():
if w > 0:
print(f"{p} {(w / nb_games) * 100:.2f}")
print()
for p, w in wins.items():
print(f"{p} {(w / nb_games) * 100:.2f}")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment