Hacker News new | past | comments | ask | show | jobs | submit login

My first programming project was a tic-tac-toe game with a computer opponent. I painstakingly copy-pasted about a hundred nested `if` statements to check for a winner & decide the computer’s next move.

Several years later I saw a Matlab demo that did this by indexing the grid using values from a 3x3 magic square[1]. In a magic square, every row, column, and diagonal has the same sum. So checking for a winner was just checking if a player’s three moves added up to 15. Finding a space that would make the computer win, or block the human opponent from winning, was subtracting two moves from 15 and checking if that spot was available.

[1]: https://en.wikipedia.org/wiki/Magic_square




This is cool. I never actually realized that magic squares exhausted all of the sums to 15; in other words, there is no triplet which sums to 15 and is not already a row, column, or diagonal. No false positives, so to speak.

I wonder if this is true of larger magic squares.


It is not. There are indeed exactly 8 ways to pick three elements from the set [1,9] such that their sum equals 15. But for 4x4, there are 86 (!) ways to pick four elements from [1, 15] so that their sum is 34 (the magic constant for 4x4), whereas only ten of the combinations are used in construction of the square.

Some Python:

  from collections import Counter
  from itertools import combinations

  def number_of_sums(n, M):
    combs = combinations(range(1,n**2+1), n)
    sums = (sum(c) for c in combs)
    return Counter(sums)[M]

  print(number_of_sums(3, 15))
  print(number_of_sums(4, 34))


In high school I made a tic-tac-toe game that implemented what I thought was a clever trick for its has-winner? routine: starting with a 3x3 grid of ones, I multiplied each of its rows, columns, and diagonals by a unique prime number. This results in a board that internally looks something like

238, 22, 494

21, 10659, 39

665, 55, 1105

so checking for a winner was equivalent to checking if the gcd of a player’s spaces was greater than 1.

Much less efficient! But it looks like I was on the right track in searching for compact numerical alternatives to traversing the board and measuring strides.

Edit: fixed an arithmetic error


Nitpick: this only works if the player played exactly three moves (in the version of Tic Tac Toe I know you can play for up to 5 moves). Generalizing to 4 moves is fairly simple, to 5 moves less so; you can test all '3 from 5' combinations, which is only 10 possibilities, but I doubt the code to do this is easy to read and understand after the fact.


I'd disagree here; I still think it's quite elegant. For example, in python, it would look something like

  from itertools import combinations
  magic_square = [2,7,6,
                  9,5,1,
                  4,3,8]
  def did_user_win(moves):
    # Convert moves to magic square values
    magic_values = [magic_square[move] for move in moves]
    # Check if any sum of three moves equals 15
    for three_values in combinations(magic_values,3):
      if sum(three_values) == 15: return True
    return False


Point taken. I love itertools :D


I thought I had an original and clever solution to TTT... my solution was to define all winning combinations as sets of (x,y) coordinate pairs and each time a player made a move, check to see if any of the winning combinations was a subset of the player's set of coordinate pairs.


Oh wow. My mind is boggled. Boggled I say!




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: