Solving noughts and crosses - AKA tic tac toe
Posted: February 21st, 2021, 7:21 pm
Not a puzzle as such, more of an idea that might spur some discussion.
I was listening to a podcast about a chess computer that machine learned how to play by being given the rules and then set to play millions of games of chess against itself. The end result is a program that plays chess very very well.
I also recall that chess, has been 'solved' on a 5x5 board. So every possible move has been worked through and if one were to play against a machine that had the database, you can never win.
So I was musing about noughts and crosses and how I would have tried to solve that using an old machine with very limited memory - A BBC micro would be ideal.
I keep musing and might even dust off my very rusty programming skills to see where I get to.
With a 3x3 grid, we have only 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 for 362,880 possible game variations.
Except we don't.
Any play that ends in win reduces that number.
In idle musing, I was working on reducting the number of possible variants of play and the first multiplier '9' is not '9' it is three - There are only three possible opening moves, center of grid, corner or the middle bit. The board needs to be rotated or mirrored.
The drops the total gameplay variations to 120,960 and that is as far as I've got.
It won't be difficult to work out an algorithm to never ever lose at tic-tac-toe but I feel that it should have been possible with a bit of clever programming to solve it with a database of every move possible and fit it into 32k.
Over to you.
B.
I was listening to a podcast about a chess computer that machine learned how to play by being given the rules and then set to play millions of games of chess against itself. The end result is a program that plays chess very very well.
I also recall that chess, has been 'solved' on a 5x5 board. So every possible move has been worked through and if one were to play against a machine that had the database, you can never win.
So I was musing about noughts and crosses and how I would have tried to solve that using an old machine with very limited memory - A BBC micro would be ideal.
I keep musing and might even dust off my very rusty programming skills to see where I get to.
With a 3x3 grid, we have only 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 for 362,880 possible game variations.
Except we don't.
Any play that ends in win reduces that number.
In idle musing, I was working on reducting the number of possible variants of play and the first multiplier '9' is not '9' it is three - There are only three possible opening moves, center of grid, corner or the middle bit. The board needs to be rotated or mirrored.
The drops the total gameplay variations to 120,960 and that is as far as I've got.
It won't be difficult to work out an algorithm to never ever lose at tic-tac-toe but I feel that it should have been possible with a bit of clever programming to solve it with a database of every move possible and fit it into 32k.
Over to you.
B.