Problems for Creative Computing By Water Koete The problems to be discussed in this column are those that seem particularly well suited not just for computing, but for creative computing. They will cover a wide variety of topics and subjects, and all are intended for both students and teachers - for anyone turned on by challenging problems, games of programs. Your reactions will be very much appreciated. Suggestions for future columns, solutions to problems discussed, new problems, extensions and experiences with problems discussed are all solicited. Please address all correspondence to Walter Koetke in care of Creative Computing. The challenge of creative thought is before all of us - this column is intended for those who choose to demonstrate that creative thought is also behind them. I hope you find the ideas rewarding. Tac Tix and the Complications of Fallibility The Game of Tac Tix was created by Piet Hein, also the inventor of Hex, in the late forties. A first impression of the game is likely to be that it is indeed simple, but first impressions themselves are over-simplifications aren't they? The rules of Tac Tix are few, a desirable characteristic of games to be used in the classroom. Each game begins with 25 markers arranged in a 5 x 5 square formation as in the diagram. I I _ 1 Two players then alternate turn. On each turn a player may take as many markers as he chooses from any single row or column, provided that the markers are next to each other. For example, markers 1 and 3 cannot both be removed on a single turn unless marker 2 is present and is also removed with others. The player who removes the last marker is the winner. STOP READING this article. Put it down and take a few minutes to analyze the game. The first player has an easily described winning strategy. Can you find it ? Assume that the first player can play without error. On his first turn he should remove marker 13, the center marker. On each subsequent turn he should remove the markers symmetrically opposite those removed by his opponent. By playing in this manner he is assured of winning the game. After the center marker is removed, a typical game might be: Second Player First Player 2 - 5 21 - 24 15, 20, 25 1, 6, 11 8 - 10 16 - 18 7 19 14 12(wins) When playing this game, an equally infallible second player is likely to be bored to death. Since Tac Tix is played on a small board, has only a few easily stated rules, and requires only a short time to play, it is a very good game to implement on a computer. Writing a program that will play Tac Tix with a user by following a well defined strategy is an excellent problem at two different levels. First, try a program in which the computer is the first player. To do this, one must be able to create a program that: represents the 5 x 5 board using single or double subscripted variables; makes symmetrical moves; determines if the second player is making a legal move; and realizes that the games is over. When writing the program one faces many of the likely difficulties encountered in far more complex problems. Second, try a program in which the computer is the second player. If all users were infallible, then this really isn't worth writing. However, some-where there may be a student or teacher who occasionally makes an error. Assume that you're writing the program for him. By considering this small bit reality, a trivial case in the world of perfect has become rather challenging, interesting problem. Consider each of the following opening plays of the first player. What is the best counter play for the second player? Opening Play Counter Play 3, 8, 13 ? 16 - 18 ? 11 - 15 ?