The famous MENACE matchbox computer for playing tic-tac-toe, invented by Donald Mitchie, is an early example of a reinforcement learning algorithm. Here is a description:

...an interesting machine for playing tic-tac-toe. It was made entirely out of matchboxes, each one of which had a tic tac toe position on the top. Inside was a collection of colored beads. Each color specified a possible legal move for the position on top. The idea was that you’d play a game by drawing these beads from the appropriate box, and making the appropriate move. At the end of the game, you’d remove the bead from the last box that sent you along the losing path. Eventually, all the losing moves get removed, and the machine plays perfect tic-tac-toe. Gardner showed how this same idea could be used to create a matchbox computer to play hexapawn, a simple game played with six pawns on a 3×3 board.

My question is: what kind of algorithm is this, in modern parlance? Is it policy iteration? Q-learning? Or sooething else? I am a bit new to the subject and can't figure it out for sure.

  • 4
    $\begingroup$ ... brute force? $\endgroup$
    – Lev Reyzin
    Dec 24, 2012 at 20:43
  • 2
    $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). I am not sure if your question is a research-level question in TCS. Please see the FAQ for more information on what is meant by this. Your question might be more suitable for Computer Science which has a broader scope than this site or for Cross Validated. $\endgroup$
    – Kaveh
    Dec 24, 2012 at 21:41

1 Answer 1


I found this question because I was searching for an answer to it myself...so take my answer on this with a grain of salt...but I believe that it's similar to policy gradients. In policy gradients you increase the probability of taking actions when you see a large reward which followed those actions...that seems to be the idea behind MENACE as well.


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.