Menace: A Machine-Educable Noughts and Crosses Engine (2016)

This is a great video demonstration by Matt Parker of Parker Square fame: https://www.youtube.com/watch?v=R9c-_neaxeU

The rules seem weird - Martin Gardner had the same matchbox self-learning robot for playing hexapawn https://en.wikipedia.org/wiki/Hexapawn It had less states so it could fit on 20+ matchboxes that were filled with candy, but the rules are: 1. If it wins, nothing is changed 2. If it loses, you take the last move that has been made that resulted in the loss, and eat the candy, thus cutting this move from the possible move graph

This way every game lost improves the engine 100%, while in this Menace example the draw introduces unnecessary noice by bringing back moves, and the punishment for a loss seems unnecessarily harsh - removing EVERY MOVE played, which may cut out the best strategy

I remember trying to build something similar in my teen years after reading about it in one of the Martin Gardner's book. I don't remember the details, but the number of boxes needed was definitely nowhere near 304, 30+ IIRC.

I'm not sure what to take away from this. If you already enumerated all possible board positions (modulo flips/rotations) and had a long look at each one to determine unique moves (i.e. which moves result in distinct board states), you might as well assign drawn/losing/winning to each position. It's conceptually different but not really more work...

Obligatory xkcd: https://xkcd.com/832/

I would also consider it interesting that, in the original version, you could guarantee to win 75% of the time (given knowledge of the algorithm).