## Monday, October 06, 2008

### KND's game of 15

Kashi Nath Dey (KND) is a professor of University of Calcutta in the Department of Computer Science and Engineering. He teaches Artificial Intelligence (AI) to us. In his last class before the Puja Vacations, he showed us the following interesting game that he has invented. The game has no formal name, so I took the liberty of calling it "KND's game of 15".

## The Game

This is a 2 person finite game with the following simple rules:

1. 2 players take alternate turns in selecting a number from the set 1 to 9
2. A number once selected, is not available for further selection
3. If any 3 numbers from each player's selected number sets have a summation of 15 then that player is declared as winner
4. Play continues, till any one of the player wins OR the number set is exhausted, in which case the game is declared to be a draw

As with any new game, we tried our hands at it in no time. Here are a few games that we played:

 KND 2 6 8 1 W Class 9 7 5

KND won the game as 6+8+1 = 15. If you notice carefully, its very easy to see a pattern in KND's game. He started with 2 and then for every move made by class, he just put 15 minus the number. However, this is just a coincidence as we will see in the next game:

 KND 8 2 4 9 W Class 6 5 3

This time too, KND won the game as 2+9+4 = 15. What is more important to note is that our last strategy was not what he had followed in this game. By this time our class mate Sumeet was convinced that whoever plays first would win, so in the next game, KND took the second move:

 Class 5 8 7 9 D KND 6 2 3 1 D

The game was a draw. So the player playing first does not always win. Somehow, I was feeling that there might be a strategy that allows the first player to win every time he plays.

## My Analysis

The game is no doubt, very interesting. A careful study of it would soon reveal many facts which would help a lot in the gameplay. The first task in analyzing would be to jot down all such 3 number combinations which total in 15:

 1 6 8 1 5 9 2 4 9 2 6 7 2 5 8 3 4 8 3 5 7 4 5 6

Next we do a simple frequency analysis and get the following result:

 Number Frequency 1 2 2 3 3 2 4 3 5 4 6 3 7 2 8 3 9 2

I did both of these steps in class and arrived at the conclusion that 5 is the most frequently occurring number, so the player who chooses it first has a distinct advantage over the other. Next in priority were the set {2,4,6,8,} all of which have frequency of 3. Last comes the set {1,3,7,9}, all of which have the frequency of 2.

## My Strategy

So I deduced a strategy that try and capture the numbers in that order, and then from the 2nd number onwards try to block your opponent's chance of winning by capturing the number that would get him a total of 15, and simultaneously look out for numbers that would get me a total of 15.

## KND's Explanation

I used my newly formulated strategy to get a draw in the last match and was feeling quite happy with myself. Then, KND offered an alternate and much simpler explanation of the game. He first drew a 3x3 magic square:

 8 1 6 3 5 7 4 9 2

As with any magic square this one also has a constant summation over rows, columns and major diagonals. In this case, the summation happens to be 15. Now what KND has done in this game is to merge it with popular children's game of Tic-Tac-Toe. So selecting a number implies putting a 0 or X in that position in this 3x3 board. What follows is a simple game of Tic-Tac-Toe.

## Conclusion

The explanation is very elegant and simple. I liked it very much, both the game and the explanation behind it. It just shows how some apparently very different problems can be mapped in to one another. Interestingly, I knew all of the things that he required to explain the logic behind the game:

• Magic Squares, and how to generate them. I even knew the 3x3 square by heart and managed to remembered that the constant was 15 !!
• Tic-Tac-Toe

The key to arriving at the correct explanation is to think harder for simpler explanation. In fact looking back, it was easy to guess that there was some simple strategy as KND did not take much time to make his moves, which he would require if he followed my type of complicated strategy.

For the last few days I have showed this to some of my friends. With the same result, all of them tried to think of a complicated strategy. Sometimes I introduced a minor variation of showing the same thing with 9 playing cards, which makes it a card game.