<p>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.</p>

CC BY-SA 4.0
2019-03-18T21:49:52.437Z
2019-03-18T21:49:52.437Z
JacKeown
<p>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 <a href="http://brainwagon.org/2011/08/28/donald-michie-alan-turing-martin-gardner-and-tic-tac-toe/" rel="nofollow">description</a>:</p>

<blockquote>
  <p>...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.</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2012-12-24T20:43:10.457Z
... brute force?
Lev Reyzin
CC BY-SA 3.0
2012-12-24T21:41:25.977Z
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 [cs.se] which has a broader scope than this site or for [stats.se].
Kaveh
<machine-learning>
What kind of reinforcement learning is MENACE?
Felix Goldberg
# What kind of reinforcement learning is MENACE?

(Asked by: username_0 on 2012-12-24)

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](http://brainwagon.org/2011/08/28/donald-michie-alan-turing-martin-gardner-and-tic-tac-toe/):

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

**Tags:** machine-learning
> **Comments:**
> **username_1**: ... brute force?  
> **username_2**: 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 [cs.se] which has a broader scope than this site or for [stats.se].  

---

## 1 answers

### Answer by username_3 on 2019-03-18. Score: -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.


---

