Operations Research (NL): Zero-sum game theorie – melk – boter – kaas

Zero-sum game theory – melk – boter – kaas

The strategy behind the “melk – boter – kaas” game (tic-tac-toe) might be rather simple, but programming a machine to always make the optimal move is no easy task. The problem is that in a game there is always an unknown factor, which cannot simply be described by a probability distribution. When player A makes a move, there are many possibilities for player B. But player A cannot give a probability distribution for this, because that would mean that player B would, in a certain situation, pick one move in 10% of the cases and another move in 20% of the cases etc. But this is a very unrealistic way of playing tic-tac-toe, player B will always play the move that is most likely to win him/her the game, and sometimes there is one single move that is better than all the others, so player B will always play that move.

Game theory has analysed games like these (tic-tac-toe, checkers, chess), and looked at the question if there is an optimal strategy to employ. For certain games, this is the case. The most simple case is a game between two persons, where the total winnings between both persons are independent of the outcome of the game. This is the case with tic-tac-toe, if you posit that the rules are that the winner gets 1 point, the loser gets -1 point and in case of a tie both players get 0 points. Then every game exactly 0 points are awarded. Therefore these games are also known as zero-sum games.

To devise an optimal strategy, one must first know every possible strategy. This might at first seem like a very difficult task, but using a simple artifice it is possible to set up a sort of table for every game of the same kind, which makes comparison and analysis very easy. The trick is to give the players a list of all of the situations that could happen in a game, and then ask them what their next move would be, every answer is a strategy.

When all strategies are known, a simulation between two strategies can be done, to see which one will be victorious. You could arrange every possible strategy of players A and B, where you could use all rows for player A and all columns for player B. If you index the strategies from player A from 1 to n, and the strategies from player B from 1 to m, then you get a so-called payoff matrix for player A. The payoff matrix from player B would be retrieved by simply turning all of the signs from matrix A, so we have all the information we need in matrix A.

From this matrix, the strategy with the most amount of wins can be found. For a game of tic-tac-toe, this is still relatively simple because of the limited amount of moves, but for a game of chess or the Chinese game Go these matrices would become enormous. But this method still works, even if it can take a lot of computing power.

The tic-tac-toe machine produced by the TNO Physics Laboratory could measure up with humans. It could not be defeated by anyone. A simple example like this machine showed how even problems that might not seem suitable for Operations Research can be tackled by using the right approach.