• Please review our updated Terms and Rules here

A STATIC COMPUTER.

H

Hugo Holden

Veteran Member
Joined
Dec 23, 2015
Messages
4,770
Location
Australia
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:

 
Last edited:
Yes, I couldn’t view it either.

I built an OXO machine many, many years ago from an electronics magazine. I was thinking about duplicating it at some point (because the old one ended up I know not where). I still have the magazine.

I also remember programming an AI n-dimensional OXO game using a genetic algorithm. I used to be pretty good, but the darn thing started to consistently win after a period of training. I eventually found out that some of my rules and fitness functions were not 100% correct. The darn thing had learnt to cheat by swapping one of my moves with its own!

That taught me a valuable lesson about software Verification, Testing and the like.

I will have a read of your text over the weekend. Thanks for sharing.

Dave
 
On the topic of Tic Tac Toe (aka Noughts and Crosses) and AI, one longtime favourite is 1961's MENACE, a computer that learned to play the game (albeit computer-moves-first only) using methods more-or-less analogous to modern reinforcement learning algorithms. It worked by accumulating coloured beads in a big arrangement of matchboxes.
 
I'm not sure why the video is not working yet, it works when I click on it. It must be something like privacy or region. I have posted very few videos, so I might be something I did.
 
My first exposure to a TTT electronic implementation was one built with stepping relays. Used 40W incandescent bulbs for readout and a rotary telephone dial for input. Plans were published back in the early 1960s, I think.
 
Chuck(G) said:
My first exposure to a TTT electronic implementation was one built with stepping relays. Used 40W incandescent bulbs for readout and a rotary telephone dial for input. Plans were published back in the early 1960s, I think.
Click to expand...

I had heard about this, apparently a similar system was built by Dick Smith in Australia in 1958, so it may well have been his design. It was said to have been built from telephone exchange parts. But it was not clear if it could work with either the machine or human starting first case, and if the machine could ever win against the human. But the machine could at least block all winning human moves and never be beaten by the human it was said.

I wonder where those early plans are now ?
 
There's a report from RCA back in 1955 here
And then there's the R-E "Tic Tac Moe" relay implementation of 1956 here.
I recall one that was exhibited at the Museum of Science and Industry in Chicago about the same time.

There are probably many, many articles on this as I recall that it was a favorite project for the high-school science fairs.
 
Chuck(G) said:
There's a report from RCA back in 1955 here
And then there's the R-E "Tic Tac Moe" relay implementation of 1956 here.
I recall one that was exhibited at the Museum of Science and Industry in Chicago about the same time.

There are probably many, many articles on this as I recall that it was a favorite project for the high-school science fairs.
Click to expand...
Thanks for those links super interesting.

It looks like the Moe tic tac toe can be beaten by the human sometimes, even with the A strategy, top Right page 62 of the article.


But it does have the option for machine or player to start first.

The link to the RCA report, amazing ASTRC-1 machine. It appears though, it was designed so that its circuits are initially reset, and the human starts first to initiate the machines first response. I would have to study it more to find out, whether the machine could be beaten at times, or not.

My machine was built with the brief:

1) Can never be beaten.
2) Either machine or human can start first.
3) Wins against human maximized.
4) Machine makes a random start when it is its turn to start. (it could have picked the same start every time but that would be boring)
5) devoid of temporal issues or timing dependence, being a static state computer with no intermediate data storage.
6) Is easy to verify the machine's response for any player board condition when it is the machine's turn to make a move. (this is because the design brief "had to prove it worked")
 
There are only a few win or tie strategies, when you consider flips and rotate. There just are not that many. You can make the first play in only 3 meaningful places. You can start in a corner, edge or center. Every thing else is just flip and rotate.
For each starting strategy there are only a one basic counter move that must be played on the first opposing play ( remember flips and rotates don't count as unique plays) . After the first play, if the second play is not a counter play, the person that plays first will win. The best that the second player can do is force tie, with the exception of the first player making a mistake and going off strategy with a mistake.
The first player will always win or tie unless they give the game away by using a non-winning strategy. There is no strategy that can't be blocked but remember, it must be blocks on the first counter play. Also remember, there really is no top right corner being different than any other corner for the first play. There are really only 3 first first plays, all the rest are flips and rotates.
Dwight
 
Dwight Elvey said:
There are really only 3 first first plays, all the rest are flips and rotates.
Dwight
Click to expand...
Yes, but that statement simplifies the required task to gain the correct output.

Each of the squares that the machine has to choose, in its response to a pattern of play, has a unique identity related to the board pattern, regardless of flips and rotations which can occur to generate that pattern, from some other basic start.

For the machine to do its job properly, it still requires an output to play the correct square (that is if the machine cannot be beaten and takes every opportunity to take advantage of the human going off strategy).

So there was no escaping the fact that over 800 different board patterns (to allow for both cases of who started first) still had to be analysed from a player board with 9 unique places (even if many patterns were in fact mirrors & rotations of other configurations) to produce the correct machine responses stored in ROM.

There would have been even more output data nibbles required, however, ignoring flips & rotations a number of board configurations converge quickly on the same pattern and created duplicates that way. I found that the idea of creating duplicates from the flips and rotations (which would have required address value rotations to calculate the output) might have been more prone to error, certainly doing it manually like I did. So I decided simply to not do those, and that way I could easily inspect the final data base and board play diagrams (135 charts) I created to be 100% certain the response was correct.
 
Last edited:
......one other thing that appears to be the stumbling block for a correct machine response, in the human starts first scenario I mentioned was:

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 often responds on the basis of rules and takes the center square with their O because that maximizes their tactical advantage.(But AI's don't always do this)

But the human then decides to take the opposite square on the diagonal from their first choice, creating a diagonal line XOX, seemingly a poor move, as they played a blocked row with no obvious advantage (yet), but its a future advantage.

The machine's rule based system (if that is what it is running) tells it to take an available corner as that has more tactical advantage than a middle side square. As soon as that happens the machine is destined to lose later, because it cannot see ahead, into a future board pattern, to the point that when the human responds and takes the corner to block the two diagonal aligned machine O's . The human has now created two way 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.

The only way for the machine to avoid this trap and make a draw is to force the human's move away from a corner, by the machine choosing a middle side square, which has a low tactical advantage, at that point in the game. However it forces the human to have to block it on another center side square and the human cannot set up the trap.

Generally also, the player, playing second, doesn't get the opportunity to set up this trap (unless their opponent helps them with very ill considered moves).

This particular move sequence in TTT, is one that resembles the much more complicated scenarios seen in Chess, when a move at one point in the game play appears to have minimal advantage and look non-threatening, but turns out after more play, to be very clever. Requiring a look into the future if you like, or an imagination of the way things could turn out later for the player (or machine) to avoid being beaten.

It is interesting how some Tic Tac Toe games on the net as apps can be beaten by the human with the above trick, but interestingly, not the ones based on an AI (which doesn't fall for the trap) but only in the case that the AI is set for max difficulty. My machine cannot be beaten by any human move sequence, because as mentioned, every single possibility is accounted for, so it works equally as well as the AI in max difficulty mode.
 
Last edited:
You must log in or register to reply here.
Back
Top