Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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: 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.

share|cite|improve this question
... brute force? – Lev Reyzin Dec 24 '12 at 20:43
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. – Kaveh Dec 24 '12 at 21:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.