Hugo Holden
Veteran Member
I decided to make a computer which used no master clock, no registers storing intermediate data, no CPU and no software protocol to play the Tic Tac Toe game against a human.
The idea is , it is just a mass of logic gates and ROM. The idea was to create a machine, that would play against a human, that would never allow the human to win, but not only that, beat the human and win against them at every opportunity.
The plan was to keep the current consumption very low (using 74HCT logic IC's). On account of the absence of clocking, the power consumption is extremely low.
But, the computation problem was not trivial. It is the solution to the Tic Tac Toe problem. Which seems simple on the face of it, until you attempt to create a machine that can play a human in both conditions of whether the machine or the human starts first and when the machine starts first, it starts in a random location on the player board.
There are "rule based" solutions suggested on Wikipedia to solve Tic Tac Toe, but these are defective when it comes to solving the scenarios of who starts first.
The primary reason is, for example, if you have the human starting first, a rule based system on where to move next often fails, because it cannot look further into the future than the move it makes at the time.
One example of this is a "two way trap". For example, lets say the human starts first and places their X in one corner of the player board. The machine responds on the basis of rules and takes the center square with their O because that maximizes their advantage.
But the human then decides to take the opposite square on the diagonal from their first choice, creating a diagonal line XOX. But the machine's rule based system tells it to take an available corner. As soon as that happens the machine is destined to lose, because it cannot see ahead, to the point that when the human responds and takes the corner to block the two diagonal aligned O's , the human has now created a future trap that the machine cannot escape from, because there are two options for the human to move on the next play for a win, and the machine can only block one of them. So the machine loses.
To create a game where either player can start first (this is only fair as the first player has an advantage) and one of the players is assigned to be the machine and the machine makes a random start, it actually requires over 800 unique responses. (I used a spinning wheel technique as the randomiser) That is also if the machine is a "good player" and takes advantage of every mistake made by a human to maximize wins not just draws. It is a zero sum game when the machine plays the human cannot beat it. The reason why, when the machine starts first, it should make a random start is that from the human's perspective, their opponent could in fact start anywhere on the board.
To pull this off I had to draw up every single possible pattern of game play (by hand) in a large number of charts, leading to the over 800 required responses, hand programmed stored in a vintage ROM.
To coordinate the the computation in the two different "which player starts first" scenarios, I deployed a parity IC and a game sequencer circuit. To make the game play well I used magnets inside player pieces with reversed poles so the encoder board knows whether a player piece is in any position on the board or not and whether it is an X or an O. This effectively converted a tristate logic scenario to binary. I used Ratiometric Hall devices, built into the player board and OP amps as comparators. There are no mechanical switches.
Another advantage is, the machine can never get out of step with itself. Even if it is power cycled it always comes up in the correct condition, which simply depends on the state (where the pieces are on the player board).
The machine also announces when it beats the human.
There are Tic Tac Toe apps on the net, with software based on a rule system, that are defective and can be beaten. Though the ones driven by an AI are generally very good and don't fall for two way traps set up by a human.
There was another design using a ROM, which used latches & intermediate data, but as far as I could see it had incomplete responses.
Also, although some claim to have solved it in software with a uP and based on a rule system, very few examples have had the software verified and few allow both players to start first, or randomize the machine's first move when it starts first. (it is a little like unverified Boeing MCAS software).
In my design it can be easily and fully verified from the charts (135 of them) I created which show the response, because every single pattern of game play and the machine's response to it is accounted for, for both of the which player started first scenarios. Part of the challenge to make this game was "to prove that it works and is unbeatable".
This machine doesn't have to compute any board pattern for an appropriate response, because, it is already pre-computed an programmed into the ROM. The 18 bit data from the encoder board is static data depending on the pattern of pieces on the board.
I built the machine out of 10mm thick black acrylic with white engraving. Also, the spare player piece (depending on who starts first) is placed on the board to act as a switch to instruct the game sequencer about when the "computation" or response (ROM activation) should be given, to light up the LED's where the machine wants its piece to be placed.
There is also a brief video link:
The idea is , it is just a mass of logic gates and ROM. The idea was to create a machine, that would play against a human, that would never allow the human to win, but not only that, beat the human and win against them at every opportunity.
The plan was to keep the current consumption very low (using 74HCT logic IC's). On account of the absence of clocking, the power consumption is extremely low.
But, the computation problem was not trivial. It is the solution to the Tic Tac Toe problem. Which seems simple on the face of it, until you attempt to create a machine that can play a human in both conditions of whether the machine or the human starts first and when the machine starts first, it starts in a random location on the player board.
There are "rule based" solutions suggested on Wikipedia to solve Tic Tac Toe, but these are defective when it comes to solving the scenarios of who starts first.
The primary reason is, for example, if you have the human starting first, a rule based system on where to move next often fails, because it cannot look further into the future than the move it makes at the time.
One example of this is a "two way trap". For example, lets say the human starts first and places their X in one corner of the player board. The machine responds on the basis of rules and takes the center square with their O because that maximizes their advantage.
But the human then decides to take the opposite square on the diagonal from their first choice, creating a diagonal line XOX. But the machine's rule based system tells it to take an available corner. As soon as that happens the machine is destined to lose, because it cannot see ahead, to the point that when the human responds and takes the corner to block the two diagonal aligned O's , the human has now created a future trap that the machine cannot escape from, because there are two options for the human to move on the next play for a win, and the machine can only block one of them. So the machine loses.
To create a game where either player can start first (this is only fair as the first player has an advantage) and one of the players is assigned to be the machine and the machine makes a random start, it actually requires over 800 unique responses. (I used a spinning wheel technique as the randomiser) That is also if the machine is a "good player" and takes advantage of every mistake made by a human to maximize wins not just draws. It is a zero sum game when the machine plays the human cannot beat it. The reason why, when the machine starts first, it should make a random start is that from the human's perspective, their opponent could in fact start anywhere on the board.
To pull this off I had to draw up every single possible pattern of game play (by hand) in a large number of charts, leading to the over 800 required responses, hand programmed stored in a vintage ROM.
To coordinate the the computation in the two different "which player starts first" scenarios, I deployed a parity IC and a game sequencer circuit. To make the game play well I used magnets inside player pieces with reversed poles so the encoder board knows whether a player piece is in any position on the board or not and whether it is an X or an O. This effectively converted a tristate logic scenario to binary. I used Ratiometric Hall devices, built into the player board and OP amps as comparators. There are no mechanical switches.
Another advantage is, the machine can never get out of step with itself. Even if it is power cycled it always comes up in the correct condition, which simply depends on the state (where the pieces are on the player board).
The machine also announces when it beats the human.
There are Tic Tac Toe apps on the net, with software based on a rule system, that are defective and can be beaten. Though the ones driven by an AI are generally very good and don't fall for two way traps set up by a human.
There was another design using a ROM, which used latches & intermediate data, but as far as I could see it had incomplete responses.
Also, although some claim to have solved it in software with a uP and based on a rule system, very few examples have had the software verified and few allow both players to start first, or randomize the machine's first move when it starts first. (it is a little like unverified Boeing MCAS software).
In my design it can be easily and fully verified from the charts (135 of them) I created which show the response, because every single pattern of game play and the machine's response to it is accounted for, for both of the which player started first scenarios. Part of the challenge to make this game was "to prove that it works and is unbeatable".
This machine doesn't have to compute any board pattern for an appropriate response, because, it is already pre-computed an programmed into the ROM. The 18 bit data from the encoder board is static data depending on the pattern of pieces on the board.
I built the machine out of 10mm thick black acrylic with white engraving. Also, the spare player piece (depending on who starts first) is placed on the board to act as a switch to instruct the game sequencer about when the "computation" or response (ROM activation) should be given, to light up the LED's where the machine wants its piece to be placed.
There is also a brief video link:
Last edited: