thicc-tac-toe AI, pctf2021

thicc_ai.py

# This is AI source for the thicc-tac-toe challenge server from PlaidCTF 2021.
# It's also the reference solution, since it loses to itself often enough.
from __future__ import print_function
from collections import Counter
import random

def ai(B, xo, randomize=True):
  our_two_aways = set()
  their_two_aways = set()
  about_to_win = None
  for line, (owner, count) in B.count_all_lines():
    if owner is None: # conflict or empty line
      continue
    # mono line
    if count == B.X - 1:
      for idx in B.points(line):
        if B[idx] is None:
          if owner == xo:
            return idx # go win
          else:
            # if about_to_win is not None, opponent
            # has two winning moves. oh well.
            about_to_win = idx
          break
      else:
        assert False
    elif count == B.X - 2:
      for p in B.points(line):
        if B[p] is None:
          if owner == xo:
            our_two_aways.add(p)
          else:
            their_two_aways.add(p)

  if about_to_win is not None:
    return about_to_win

  def metric(idx, for_opponent=False):
    """Return a score tuple indicating how generally good an empty spot is."""
    try:
      t = B._ai_lines_thru_point_cache[idx][xo]
      if for_opponent:
        return t[:1] + (-t[1],) + t[2:]
      else:
        return t
    except KeyError:
      pass

    counted = []
    empty_lines = 0
    for line in B.linesthru(idx):
      owner, count = B.count_line(line)
      if owner is not None:
        counted.append((owner, count))
      elif count == 0:
        empty_lines += 1

    t = (
      sum(v**v for k,v in counted),  # conflict score
      sum(k==xo for k,v in counted), # is it us?
      empty_lines, # empty lines
      sum(i*2+1 == B.X for i in idx), # centers, for odd dimensions.
    )
    B._ai_lines_thru_point_cache.setdefault(idx, {})[xo] = t
    if for_opponent:
      return t[:1] + (-t[1],) + t[2:]
    else:
      return t

  # look for "checkmate" spots
  their_checkmates = set()
  for idx in sorted(our_two_aways|their_two_aways):
    us = 0
    them = 0
    for line in B.linesthru(idx):
      owner, count = B.count_line(line)
      if count >= B.X - 2:
        if owner == xo:
          us += 1
        elif owner is not None:
          them += 1
    if us >= 2:
      return idx # take our checkmate spot. We've already checked one-aways.
    elif them >= 2:
      their_checkmates.add(idx)

  if len(their_checkmates) == 1:
    # TODO: This is wrong; instead of taking someone else's checkmate spot,
    # we should take the most advantageous spot that breaks the checkmate.
    return list(their_checkmates)[0]
  elif len(their_checkmates) > 1:
    # Uhoh, multiple checkmate spots by other.
    # We must simultaneously break checkmates and force a move
    good_moves = set()
    for idx in our_two_aways:
      for line in B.linesthru(idx):
        owner, count = B.count_line(line)
        if owner == xo and count == B.X - 2:
          t = [i for i in B.points(line) if B[i] is None and i != idx]
          assert len(t) == 1
          if t[0] not in their_checkmates: # the forced position
            good_moves.add(idx)

    if len(good_moves) == 0:
      # I think we'll lose unless opponent makes a mistake?
      # Unless there's one spot that causes both checkmate moves to
      # become non-checkmate moves, I guess? But we don't check for that.
      good_moves = our_two_aways & their_checkmates
      if len(good_moves) == 0:
        good_moves = their_checkmates
    good_moves = sorted(good_moves)
  elif our_two_aways:
    # Check to see if forcing an opponent to move looks stronger for
    # us than them.
    l = len(metric(next(iter(our_two_aways))))
    cutoff = (0,)*(l-1) + (1,)
    good_moves = []

    for idx in our_two_aways:
      for line in B.linesthru(idx):
        if B.count_line(line) == (xo, B.X-2):
          # line is the 2-away line
          other = {i for i in B.points(line) if B[i] is None} - {idx}
          assert len(other) == 1
          other = other.pop()
          # Evaluate how other looks for the opponent, compared to idx for us.
          t = tuple(i-j for i,j in zip(metric(idx), metric(other, for_opponent=True)))
          if t > cutoff:
            cutoff = t
            good_moves = [idx]
          elif t == cutoff:
            good_moves.append(idx)
    good_moves.sort()
  else:
    good_moves = []

  # Pick the "most conflicting" spot, prefering ours? Not right but w/e
  if randomize:
    t = ((metric(idx), random.getrandbits(10), idx) for idx in (good_moves or B.iterempty()))
  else:
    t = ((metric(idx), idx) for idx in (good_moves or B.iterempty()))

  #t = sorted(t)[::-1]
  #print '>>>', t
  try:
    return max(t)[-1]
  except ValueError:
    return None

It's worth noting that this is NOT a good AI, and should be beatable by any formal game-playing search techniques. This AI only looks approximately one move ahead!

Would you be willing to release some of your board logic? I’m interested to see how you reduced a 5-dimensional space to a problem that Python could solve in a reasonable amount of time. I’m sure it’s possible, but I didn’t see it as a problem that was worth the time in 48 hours and I’d be interested to see the algorithm.