Monday, October 7, 2013

Tic-tac-toe and other games

Dr Pace Nielsen, a professor at BYU, led our most recent math circle.  His focus was games on grids, like tic-tac-toe, but with interesting modifications.

Preparation:  Each student needs a pencil, and two or three sheets of graph paper.

Introduction:  Dr Nielsen reminded everyone how you play tic-tac-toe on a 3x3 grid.  The first player places an X in one of the squares.  The second player places an O.  When one player gets three of their symbol in a row, either horizontally, vertically, or diagonally, that player wins.  If the grid is filled and no one wins, we say "the Cat wins". 

A child was invited to the board to play a couple of games.  The children soon saw that if each player used their best strategy, the Cat would always win in the 3x3 game. 

Activity 1:  Each child received graph paper and a pencil.  With another child, they were asked to play tic-tac-toe, only with modified rules.  Instead of playing on a 3x3 grid, they would play on a 4x4 grid.  The same rules applied:  X starts, O goes second.  The first child to get three in a row, either vertically, horizontally, or diagonally, would win.  Note that even though the grid size is 4x4, the players still only needed three in a row to win.

Example 4x4 Tic-Tac-Toe games played by two children.  Note O won a couple of rounds, until X figured out a strategy....


The children played several rounds for several minutes, switching who played X and who played O.  Dr Nielsen and the other classroom helpers walked around a bit, observing the children's games, sometimes giving hints.  After they had had the chance to play for a while, Dr Nielsen called everyone back to ask about strategy.

"What happens in the 4x4 tic-tac-toe game?  Does the Cat win?"

By now, most of the groups had discovered that someone, either X or O, seemed to always win, although not all the groups had figured out a strategy.  However, one enthusiastic little girl raised her hand high.

"X always wins if they are smart!"

Dr Nielsen then asked the children to help him walk through a strategy that would guarantee that X would win.  First move:  X should start in the middle.  Then the children noticed that no matter where O went, X could go again in the middle, adjacent to their first X, to have two in a row with empty squares on either side.  Then O could not block X from winning the next turn.

Winning strategy for X in 4x4 Tic-Tac-Toe. 

Activity 2:  Now that the children understood 4x4 tic-tac-toe, the rules were mixed up again.  Everything was the same, except they played on a 3x4 grid.  Who would win this time?

After a few minutes of playing, switching between X and O, again a couple of groups had found a strategy where X would always win.  I'm not going to give the winning strategy away this time -- see if you can figure it out.  Hint:  X should start in the middle.

A few 3x4 Tic-Tac-Toe games.


Activity 3:  Infinite tic-tac-toe.  This time, the children were allowed to use a grid as large as they wanted, but they needed to get four in a row.  With a new sheet of graph paper, students played several rounds.


A few minutes into the activity, one girl started jumping up and down.

"We figured it out!  X always wins!"

"OK," said Dr Nielsen.  "Let's play."  He sat down with the girl and they played together.  The first round, he won, but she made a mistake, and wanted to play again.  The second round, he also won.

"But guess what?" he said confidentially.  "You are right!  X always wins."

"If they are smart," said the girl, meaning X wins if they know what they are doing.

Dr Nielsen then gathered the group together then and asked them who wins.  Those who had overheard the earlier exchange knew that X would win, and he told them that was correct.  However, the game was much harder than the others they had been playing. 

"So if you're tired of regular tic-tac-toe, and you want a challenge, play infinite tic-tac-toe instead."

Activity 4:  Angels and Devils.  At this point, everyone got a new sheet of graph paper and we started a new game, called Angels and Devils.  In this game, X and O take turns, just as in tic-tac-toe.  However, rules for movement and objectives are different.  X must start in the middle of the sheet of paper, and on their next move, they can only go into an adjacent square.  O, on the other hand, can go anywhere.  Their goal is to keep X from getting to the edge of the paper.  If X makes it to the edge of the paper, then X wins.  If they are blocked, O wins.

Again the children played for a few minutes.  One group was convinced that X would always win.  Dr Nielsen came to check out their solutions and noticed that they were dividing their graph paper into small blocks.  "Try playing on a much larger grid," he suggested. 

In fact, mathematicians have been able to show that X will actually always lose when the rules are as given above.  (See, for example, this wikipedia page.)  While none of the younger children were able to come to this conclusion in the amount of time available, they had fun drawing X's and O's for a while.  When some of them started getting restless, we switched activities again.

Activity 5:  Tapping fingers.   Before starting the new game, Dr Nielsen had everyone switch tables and pick new partners.  He then called up a student to help him demonstrate the rules of the new game, which was a little different.  This game doesn't require pencil or papers, but just a partner and hands!

Both he and the student held out two hands, with one finger extended on each hand.  The first player tapped one of the hands of the other player with one of their hands.  The player who was tapped needed to add a number of fingers equal to the number that was on the hand of the other player who tapped them.

For example, on the first round, when the first player had 1 finger on the right hand, 1 on the left, and the second player had 1 on the right and 1 on the left, no matter which hand the first player tapped, the second player would end up with 1 finger on one hand, and 2 on the other.

Now the second player takes a turn.  They can either tap the first player's hand with 1 finger or with 3.  If they tap with 1, the first player will add 1 finger to the hand they tap.  If they tap with 3, the first player will add 3 fingers to the hand they tap.

For example, now the second player has 2 fingers on his left hand, 1 on his right, and the first player has 1 finger on each hand.  The second player tapped the first player's left hand with his 2-finger hand.  Then the first player had 3 fingers on the left, and 1 finger on the right.

If a player is tapped by another so that the fingers on the hand add up to 5, that hand is dead, and must go away.

However, if the fingers add up to more than five, for example if a hand with four fingers taps a hand with three fingers, then the 3-finger hand gets all four added as follows:  first add 2 -- now there are five fingers and the hand closes.  Then add the remaining 2.  These stick.  So a hand with 3 fingers tapped by a hand with 4 fingers gives a hand with 2 fingers.  (Is that confusing?  With some help the first time it came up, even the kindergarteners were able to figure it out.)

One last rule.  If one of your hands is dead, but there are an even number of fingers on your other hand (either 2 or 4), you can use your turn to tap your dead hand with your other hand, and split the fingers between the two hands.  So if you tap your own dead hand with a hand with 2 fingers, each hand ends up with 1 finger.  Similarly, if you tap your own dead hand with a hand with 4 fingers, each hand ends up with 2 fingers.

The first player to have two dead hands loses.

Once the rules were explained, and demonstrated, the children paired up and played the game together.  I hadn't been playing the tic-tac-toe games, but this time I got a partner -- a kindergartener named Eleanor.  Eleanor wasn't in a super competitive mood, and neither was I, so we took turns tapping hands back and forth without really killing off any hands.  While we weren't coming up with a winning strategy, Eleanor was still having fun practicing simple addition (and modular arithmetic!), and she was pretty good at it.

Eleanor's mom, who is a friend of mine and apparently somewhat more competitive than her daughter, began giving Eleanor suggestions for how to defeat me.  Eventually, with Eleanor's laughing support, the mom took over Eleanor's hands and began directing operations.  We were having lots of fun, but we still hadn't figured out a winning strategy before time was called...  Cookies!

Because we were having too much fun, I missed Dr Nielsen's concluding remarks.  You will have to figure out your own winning strategy for this game.  

And next time, Eleanor and I are going to gang up on Eleanor's mom.