MENACE (Matchbox Educable Naught and Crosses Engine) is an unbeatable self-learning Tic-Tac-Toe AI game written in python proposed by Donald Michie in 1961 and 1963.
MENACE consists of a matchbox for each possible board state.Each matchbox contains a number of coloured beads, for each possible move from that particular board state. We need to draw a bead at random from the matchbox corresponding to the current board state, which will determine the move to be played by the machine. After every game, beads are added or removed from the matchboxes to reinforce or punish decisions of Menace.