4 ms·

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

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 https://en.wikipedia.org/wiki/Magic_square

laurentl 8y ago
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.
- chrisshroba 8y ago
  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
  - laurentl 8y ago
    Point taken. I love itertools :D
jjnoakes 8y ago
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.
- Sharlin 8y ago
  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))
neoncontrails 8y ago
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
packetpirate 8y ago
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.
jedimastert 8y ago
Oh wow. My mind is boggled. Boggled I say!

laurentl 8y ago

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.

chrisshroba 8y ago
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
- laurentl 8y ago
  Point taken. I love itertools :D

jjnoakes 8y ago

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.

Sharlin 8y ago
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))

neoncontrails 8y ago

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

packetpirate 8y ago

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.

jedimastert 8y ago

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