Month: November 2017

PyMENACE – Simple Machine Learning

While browsing YouTube, I came across the video “MENACE: the pile of matchboxes which can learn.” The video goes on to detail MENACE, or Machine Educable Noughts And Crosses Engine, in which there is a matchbox for every possible state of Tic-Tac-Toe. In each box, there are beads corresponding to the possible moves the “computer” can make. On the computer’s turn, the player finds the correct game state and draw a random bead. After the game ends, if the computer won, every move the computer made receives three more beads of the correct color. If the player won, the beads the computer played are simply removed from play. In this way, the computer eventually learns to play Tic-Tac-Toe by trial and error.

Now I found this concept fascinating and as such I wanted to give it a try! However, I’m pretty lazy and didn’t want to make 304 matchboxes nor did I have 200+ people to help it learn. So I programmed it! To start with, I wanted to get the knowledge “map” made. This means I had to generate every possible board state, well not all of them, just the ones where it is MENACE’s turn. After doing that, each board state is initialized with probabilities for each possible play position.

Now that I had the knowledge map, I put together the functionality for actually making a move. Both MENACE and the player make a move with the same function, the player just has to provide their move as an argument. Every move MENACE makes is stored in a list that is then referenced my the learning function. When a winner is detected, MENACE goes through every move it made and adjusts accordingly. (Win: +4, Tie: +3, Lose: -1)

After the basic functionality was there, I put together a simple QT GUI wrapper and hooked MENACE to it. Now, this isn’t the worlds best Tic-Tac-Toe game, but it does learn as you play. If you want to give it a try, you can check out the code on my GitHub, or you can try to make it yourself! Either way, I hope you enjoyed this cobbled together mess of a post.

~T

Posted by Tanner in Posts, Programming Projects