Enigmatic Code

Programming Enigma Puzzles

Enigma 1284: Os and Xs offside

From New Scientist #2442, 10th April 2004 [link]

We are playing ordinary noughts and crosses but with two extra rules:

(i) A player may not go in the centre square if going in the centre square puts that player in a position which is better for them than every other position they could have gone to instead.

(ii) If after eight turns no one has won and the centre square is empty then the game ends and is declared a draw.

For the purpose of rule (i), position P is better for a player than position Q if either (a) the player can force a win from P but not from Q, or (b) the player can force a draw or better from P but not from Q.

If, in a game, O goes first and each player plays as well as possible, is the result a win for O, a win for X or a draw?

Note: I am still waiting for a phone line to be connected at my new house, so I only have sporadic access to the internet at the moment. The latest estimate is that I’ll have a connection by the end of October 2014.

[enigma1284]

One response to “Enigma 1284: Os and Xs offside

  1. Jim Randell 22 October 2014 at 2:22 pm

    I find this kind of problem a bit unsatisfying to solve programatically. Because when you find the solution, which is one of a very small set of values, it is not easy to use it to demonstrate that it is actually correct. Whereas it is quite easy to write a flawed program that produces the right answer.

    Nevertheless I think this Python program plays the game as given in the puzzle and examines all possible moves. It runs in 933ms.

    from collections import defaultdict
    from enigma import printf
    
    # 0 1 2
    # 3 4 5
    # 6 7 8
    
    # the winning lines are:
    lines = (
      (0, 1, 2), (3, 4, 5), (6, 7, 8),
      (0, 3, 6), (1, 4, 7), (2, 5, 8),
      (0, 4, 8), (2, 4, 6),
    )
    
    # return an updated grid with g[i] = v
    def update(g, i, v):
      g = list(g)
      g[i] = v
      return g
    
    # grid <g> with player <p1> to play
    def play(g, p1, p2):
    
      # has someone won?
      for s in lines:
        (g1, g2, g3) = (g[i] for i in s)
        if g1 is not None and g1 == g2 == g3:
          return g1
    
      # count the remaining squares
      n = g.count(None)
      # it's a draw if there are no squares left
      # or only the centre square (4) is left
      if n == 0 or n == 1 and g[4] is None:
        return 'draw'
    
      # otherwise, consider each playable square
      # and record outcomes
      m = defaultdict(list)
      for (i, x) in enumerate(g):
        if x is not None: continue
        r = play(update(g, i, p1), p2, p1)
        m[r].append(i)
      # consider outcomes (win, draw, lose)
      for x in (p1, 'draw', p2):
        if m[x]:
          # but not if 4 is the only move
          if m[x] == [4]: continue
          return x
    
    # start with an empty grid, O to play first
    r = play([None] * 9, 'O', 'X')
    printf("outcome = {r}")
    

    Solution: The result is a draw.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: