2
$\begingroup$

I recently read about the “computer” built out of matchboxes designed by Donald Michie that could teach itself how to play tic tac toe. Here is the Wikipedia article about it:

https://en.m.wikipedia.org/wiki/Matchbox_Educable_Noughts_and_Crosses_Engine

I thought it looked interesting, so I decided to make a digital version in Python for fun and practice. It works well against random moves (I just ran it on the data from ≈10,000 games, and it won 4757 out of 5353) but it still looses often against me.

Here are some points that a perfect answer would address:

  • How many games will it take for a “matchbox computer” that works exactly like the one Michie designed to start playing perfectly?

  • Did the original computer with actual matchboxes ever reach perfect play?

  • Will the computer ever reach perfect play if trained against only random moves?

This question is not asking for help with the code, but if someone was interested, my including the code could possibly be a help. Here is a link to a GitHub repository I created so I could share it:

https://github.com/ACertainArchangel/Recreation-Of-MENACE-Tic-Tac-Toe..git

Sorry, I know it's not very good and doesn't obey conventions; I've only been coding a couple of months :)

$\endgroup$
4
  • $\begingroup$ How is it performing against random moves? My thinking is that if it plays only against random moves, it will learn to be strong against such a random player. Some positions might be a "non-robust" loss, in the sense that there are only few sequences of moves that make it a losing position for the matchbox computer, and a random opponent is unlikely to stumble on one of these sequences. The matchbox computer would have very little incentive to avoid these positions against a random opponent, while a smart opponent like yourself can exploit this weakness. $\endgroup$
    – Tassle
    Commented Mar 25 at 14:36
  • $\begingroup$ I just updated the question to include more information. Thank you for the insightful comment! $\endgroup$ Commented Mar 26 at 19:12
  • 1
    $\begingroup$ Please don't use "EDIT: more stuff", and don't just append more things. Instead, revise the question so it reads well for someone who encounters it for the first time, with information integrated at the appropriate location in the post. See cs.meta.stackexchange.com/q/657/755 $\endgroup$
    – D.W.
    Commented Mar 27 at 2:30
  • $\begingroup$ I will keep this in mind. Thank you. $\endgroup$ Commented Mar 27 at 4:00

2 Answers 2

2
$\begingroup$

Let me illustrate with a hand-wavy argument on a very simple game why convergence to optimal play might be very slow, and not even guaranteed, when training against a random opponent.

Consider the following game: Player A first picks a color, either red or blue. Then player B picks a number between $1$ and $100$. If player A picked blue, they always wins. Otherwise, player A wins except if player B picked $1$. The optimal strategy for player A is obviously to pick blue.

Now say that player A is the matchbox computer, and player B is a random opponent. Suppose in the first 5 games, player A picked red and player B didn't pick $1$ (this is not that unlikely). Player A won each time, being rewarded $3$ red beads for every victory. At this point (assuming the matchbox computer started with one bead of each color), we have $16$ red beads and $1$ blue bead.

With probability $\frac{16}{17}\cdot\frac{99}{100} \approx 0.93$, Player A picks red again and wins, thus gaining an extra $3$ red beads. If this happens, the probability of it happening again in the next turn will be even higher than that ($\approx 0.94$), and this will snowball.

Now you might still get lucky at some point and get a streak of losses with red getting rid of all the red beads, or pick blue enough times by pure chance to make the blue beads take over. I haven't tried to work out the probabilities, but empirically I get situations where, starting with one bead of each color, after $10\ 000\ 000$ games the red beads represented more than $99.95\%$ of all beads. Meaning the matchbox computer learned the opposite of the optimal strategy!

$\endgroup$
3
  • 1
    $\begingroup$ I don't have enough rep to upvote but I will when I do. Thank you! $\endgroup$ Commented Mar 27 at 3:59
  • $\begingroup$ By the way, I asked this question on Stack Overflow too (the programming side,) and I would like to answer the question with a link here and some explanation if it's okay with you. Please feel free to answer that question if you would rather do it than me. See here: $\endgroup$ Commented Mar 27 at 13:55
  • $\begingroup$ stackoverflow.com/questions/78219696/… $\endgroup$ Commented Mar 27 at 13:55
0
$\begingroup$

To add to what Tassle said, I just tried training the AI against another copy of itself, and this produced slightly better results. I tried Increasing the number of beads taken from the matchbox on a loss (and making sure the total wouldn't fall below zero), which also helped make sure the computer wouldn't get "stuck". I am now happy with how it is working.

Swapping between AI and random for a lot of games to see if perhaps the AI would find ways to exploit weaknesses developed by random training, and then random having random training "shake things up" again made a very big difference in performance too. The program now only looses once in a blue moon).

Increasing the number of beads taken from the matchbox on a loss (and making sure the total wouldn't fall below zero) also helped make sure the computer wouldn't get "stuck". I am now happy with how it is working.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.