Colossal Gardner, ch. 38


We close out Games and Decision Theory with The New Eleusis. The game Eleusis was invented by Robert Abbott, then an undergraduate at Colorado University, in 1956. Abbott had been studying the “Aha!” moment when people make discoveries, and Eleusis, named after the ancient Greek Eleusinian Mysteries, is a good simulation system for this. Abbott released the full rules for the game in his book Abbott’s New Card Games (1963). Martin D. Kruskal, a mathematical physicist, made improvements to it, releasing his rules in the monograph, Delphi: A Game of Inductive Reasoning (1962). Gardner himself introduced Eleusis in his column in Scientific American in 1959, and because it had evolved so much over the years, he decided to write the current chapter as an update.

For the newest (at the time of the writing for this chapter) version, you need 4 to 8 players, and two standard decks of playing cards (sometimes a round lasts long enough that you need a third deck). A full game consists of one or more rounds, and players take turns dealing each round. Because the players are attempting to divine the thinking processes of the dealer, that player is often given the titles God, Nature, Tao, Brahma, the (Delphi) Oracle, or simply Dealer. The dealer’s first job is to think up a “secret rule.” This rule defines what cards can be legally played during a player’s turn. The players have to determine this secret rule, and the faster one of them does, the higher their score. One key part of the game is that the dealer gets scored too, so it’s to their benefit to create a rule that is not too easy or too hard.

An example of a rule that’s too easy: “Play a card of a color different from the color of the last card played.” Gardner’s suggestion for a better rule is: “Play so the primes and non-primes alternate.” But, depending on the players, this rule could be too hard or too simple. A rule that’s too difficult would be: “Multiply the values of the last three cards played and divide by 4. If the remainder is 0, play a red card or a card with a value higher than 6. If the remainder is 2, play a black card or a picture card… etc.”

Martin offers 3 example rules for use with inexperienced players.
1) If the last legally played card was odd, play a black card. Otherwise, play a red one.
2) If the last legally played card was black, play a card of equal or higher value. If red, play a card of equal or lower value (face cards are numbered 11, 12, 13. Ace = 1).
3) The card played must be either of the same suit, or the same value as the last card played.

“The secret rule must deal only with the sequence of legally played cards.” It cannot include things like the sex or ages of the players, the time of day, or whether Dealer scratches his/her ear, etc. The secret rule must be written down for later confirmation, and it is ok for Dealer to give a hint, such as “Suits are irrelevant to the rule,” or “The rule depends on the two previously played cards.”

After recording the rule, Dealer shuffles the double deck and deals 14 cards to each player and none to themselves. They then place a “starter card” face up on the table to the extreme left of the playing surface. To determine the starting player, Dealer counts off the value of the starting card, going around the players from Dealer’s left. The indicated player begins play, which continues clockwise around in the circle. A play consists of placing one or more cards on the table. To play a single card, the player takes a card from their hand and reveals it to everyone. If the card is playable according to the rule, Dealer says “Right,” and it is then placed to the right of the starter card on the “main line.” (The main line is the list of correctly played cards extending horizontally to the right. See below.)

If the card doesn’t fit the rule, Dealer says “Wrong,” and it’s placed under the last card played. Vertical columns of cards are called “sidelines,” and consecutive incorrect plays extend the same sideline downward. Dealer gives that player 2 more cards, expanding their hand, as a penalty. If a player thinks they know the rule, they can play a “string” of 2 to 4 cards at once, overlapping the cards slightly to preserve their order and to show them to everyone. If the full string is correct, Dealer says, “Right,” and they are added to the main line as normal. If any one card is wrong, Dealer says “Wrong” to the entire string, and deals out twice as many penalty cards as there are cards in the string. The below illustration shows an example of all the rules explained so far. The secret rule is: “If the last legal card is odd, play black, otherwise play red.”


(All rights belong to their owners. Images used here for review purposes only. Example New Eleusis game in progress.)

Players get better scores by getting rid of as many of their cards as possible, and it helps to guess the secret rule to do that. If a player thinks they know the rule but they don’t have any further cards to play, they can declare “No play” and show all their cards to everyone. If Dealer says, “Right” and the player has 4 or fewer cards left then the round ends. If the player has 5 or more cards and is right, their cards are returned to the deck and they are re-dealt 4 fewer cards than they’d been holding and the round continues. If the Dealer announces “Wrong,” Dealer takes one of the correct cards and puts it on the main line, and deals that player 5 more cards as a penalty. Therefore, if a player hasn’t figured out the rule but thinks they have no legal play, it’s better if they just play a card at random instead of saying “No Play.”

Alternatively, if the player thinks they know the secret rule, they can declare themselves a Prophet under the following conditions:
1) They have just played (correctly or incorrectly) and the next player hasn’t played yet.
2) There’s no Prophet yet.
3) At least two other players besides themselves and the dealer are still in the round.
4) They have not been a Prophet before in this round.

When a player declares themselves to be a Prophet, they put a marker on their last card played (a black chess king or queen). They keep their cards but stop playing them until they are overthrown. The play continues clockwise, skipping the Prophet. When a player plays a card, the Prophet says “Right” or “Wrong”, and Dealer validates or invalidates the call with “Correct” or “Incorrect.” If correct, the played cards are placed on the main or side lines as before. If the Dealer says “Incorrect,” the Prophet is immediately overthrown and declared a False Prophet. Dealer removes the False Prophet’s marker from the table, and deals out 5 extra penalty cards. The False Prophet cannot become a Prophet again in that round, but any other player can. Abbott has said there’s an amusing analogy with science here: “The Prophet is the scientist who publishes. The False Prophet is the scientist who publishes too early.” Martin adds “It is the fun of becoming a Prophet and overthrowing a False Prophet that is the most exciting feature of New Eleusis.”

After a Prophet fails, Dealer takes over as Dealer again, completing the play that overthrew the Prophet, placing the card or string on the main or side lines. If the play was wrong, Dealer does not give the last player any penalty cards. This exemption rewards players for taking daring plays to overthrow the Prophet. In the words of Karl Popper, it “encourages scientists to think of ways of “falsifying” a colleague’s doubtful theory.”

Things get a bit complicated if there is a Prophet and a “believer” declares “no play.” If the Prophet says “Right,” or the Prophet says “Wrong” and Dealer says “Incorrect,” play continues as described above. However, if the Prophet says “Wrong” and Dealer says “Correct,” then the Prophet has to select what they think is a correct card from the player’s hand. If they do this right, then they deal out 5 penalty cards to the current player and play continues as normal. If they pick the wrong card from the player’s hand, they’re overthrown, and Dealer takes over again as before.

If thirty cards have been played and there’s still no Prophet, players get expelled from the round if they make a wrong play. The expelled player still receives penalty cards for the wrong play, for scoring purposes. If there is a Prophet, then expulsions are delayed for at least 20 cards after the Prophet’s marker. Pawns are used to show that expulsion is possible; if there is no Prophet then white pawns are set down every 10 cards on the layout. If there is a Prophet, black pawns are placed every tenth card following the Prophet’s marker. When a Prophet is overthrown, the black pawns are removed with the Prophet’s marker.

For scoring:
1) The greatest number of cards held by anyone is called the “high count.” Each player (including the Prophet if there is one) subtracts the number of cards still held in their hand from the high count, and the difference is their score. Players with no cards get a bonus 4 points.
2) The Prophet, if there is one, gets a bonus of the number of main line cards that follow their marker, plus twice the number of sideline cards after their marker. I.e. – one point for each correct card, and two points for each incorrect one.
3) The dealer’s score is the highest score of any player. However, if there is a Prophet, count the number of cards (right and wrong) preceding the Prophet’s marker and double this number. If the number is smaller than the highest player score, use the smaller number.

If you have time for another round, then you choose a new dealer, and hopefully everyone at the table will get their turns. However, some rounds can take several hours, so when you finish playing, add up all the scores at the end of the rounds played and give 10 points to anyone that hadn’t been a dealer as compensation.


(Full sample round, left half.)


(Full sample round, right half.)

In the above game, we have the main line and 9 side lines. White pawns are used to mark every tenth card. This was a 5-player game. Martin’s example is: “Smith was the dealer. The round ended when Jones got rid of her cards. Brown was the Prophet and ended with 9 cards. Robinson was expelled when he incorrectly played the 10 of Spades; he had 14 cards. Adams had 17 cards at the end of the game. The high count is 17. Therefore Adam’s score is 17 minus 17, or 0. Robinson’s score is 17 minus 14, or 3. Jones receives 17 minus 0, or 17, plus a 4-point bonus for having no cards, so her score is 21. Brown gets 17 minus 9, or 8, plus the Prophet’s bonus of 34 (12 main line and 11 sideline cards following his marker), making a total score of 42. This is the highest score for the round. Twice the number of cards preceding the Prophet’s marker is 50. Smith, the dealer, receives 42 because it is the smaller of the two numbers 42 and 50.”

In the addendum, Martin mentions two new games that came after Eleusis and Delphi – Sid Sackson’s Patterns, and Robert Katz’s Pensari. Also, Robert Abbott has developed some Mad Mazes (1990, Bob Adams).

A simplified version of Eleusis, called Eleusis Express can be found at logicmazes.com.

Puzzle: What is Smith’s rule in the above game?

Advertisements

Penrose, Turing Machine 1


For being such a simple concept, trying to write my first Turing machine turned out to be more of a challenge than I’d expected. To recap, the basic Turing machine consists of a read/write head, an infinitely long tape, and a stepper motor for moving the tape under the head one position to the left or right. The data read from the tape will then cause the machine to do something based on its current state (i.e. – it’s a “state machine”). One example algorithm hard-coded into the machine could be:

Line 1: 00 -> 00R
Line 2: 01 -> 11R
Line 3: 10 -> 01STOP
Line 4: 11 -> 11R

In words, for line 1, if the machine is in “state 0”, and a “0” is read from the tape (i.e. – “00”), set the machine to state “0” again, write a “0” to the tape, and then move the head one position to the right.
For line 2, if the machine is in “state 0” and a “1” is read from the tape (“01”), set the machine to state “1”, write a “1” to the tape, and move the head one position to the right.
For line 3, if the machine is in “state 1”, and “0” is read from the tape (“10”), set the machine back to state “0”, write a “1” to the tape, move the head one position to the right, and then STOP the machine (AKA: R.Stop).
For line 4, if the machine is in “state 1”, and “1” is read from the tape (“11”), set the machine state to “1”, write a “1” to the tape, and then advance the head one position to the right.

Syntax:
for: state & ‘bit read’ -> ‘new state’ & ‘write bit’ & direction

The above algorithm reads a string of leading 0s on the tape, essentially ignoring them. When it hits the first 1, it changes state, then keeps reading 1s. When it hits the next zero (end of number marker), the machine writes a 1 to the tape, moves the head to the right one last time, then stops. The value generated by this machine is calculated by adding up all the 1s to the left of the head. This is a “unary” number, and the algorithm simply adds 1 to the starting number on the tape. If there were six 1s on the tape when we started, there will be seven 1s to the left of the head when we finish.

“0000111111000” – Starting data string
“00001111111” – What gets printed out before the Stop.

We can have two “stop” instructions – an R.Stop and an L.Stop. They indicate which way to move the read/write head before stopping. But, because we’re reading the output from the left of the head, there’s no point to using L.Stop, and R.Stop can then be simply abbreviated to “Stop”.

I use VBscript because it’s free, and I already know how to write in it. To emulate the tape, I just use a text string. If the read/write head reaches either end of the string, I append a “0” at that end and keep running the program. I could treat the algorithm as a series of if-statements, but for the moment I prefer to use Select Case. The main reason for this is that I’ll be changing the program structure soon anyway to make a universal Turing machine. And, it’s easier to adapt hard-coded algorithms as Case statements if I want to write a new machine.

The only real inconvenience was in having to write a function for emulating the write head, for changing characters in the middle of the string. Note that the formatting below sucks because wordpress strips out excess spaces.

‘ Turing Machine 1 – Unary Add 1
‘ Penrose program: UN+1

”””””’

tapeReel = “0000000111110000”
headPos = 1
machineState = “0”
RStop = false
tapeChr = 0

wscript.echo tapeReel & ” (” & countOnes(tapeReel) & “)”

while Not RStop
tapeChr = mid(tapeReel, headPos, 1)
fullStatement = machineState & tapeChr
action = “”

Select Case FullStatement
Case “00” action = “00R”
Case “01” action = “11R”
Case “10” action = “01STOP”
Case “11” action = “11R”
Case Else wscript.echo “No instruction provided for |” & fullStatement & “|”
End Select

if(instr(action, “STOP”) > 0) then
dummy = writeToTape(headPos, mid(action, len(action) – 4, 1))
headPos = moveHead(headPos, “R”)
RStop = true
else
machineState = left(action, len(action) – 2)
dummy = writeToTape(headPos, mid(action, len(action) – 1, 1))
headPos = moveHead(headPos, right(action, 1))
end if

wend

wscript.echo “Ping: ” & left(tapeReel, headPos – 1) & ” (” & countOnes(left(tapeReel, headPos – 1)) & “)”

Since I’m treating the tape as a text string, I need some way of marking where I am in the string (headPos), and then some function for “transporting” the head one position left or right (headPos +/- 1). Finally, I have to deal with boundary conditions. That is, what happens if I’m at the left end of the string (headPos = 1) and I have to move left, or I’m at the right end (headPos = len(tapeReel)) and I have to move right. I handle this by checking the boundaries first, and adding “0” to the end of the string as necessary to “go to the next part of the infinite tape.” I should check that I’m not exceeding VBscript’s limit on string length (64K), but that’s not a real concern for what I’m doing with this program. Either way, the tape head “moves” by incrementing or decrementing headPos.

Function moveHead(hp, dir)
ret = -1
if(hp = 1 AND dir = “L”) then
tapeReel = “0” & tapeReel
ret = 1
elseif (hp = len(tapeReel) AND dir = “R”) then
tapeReel = tapeReel & “0”
ret = hp + 1
elseif (dir = “L”) then
ret = hp – 1
elseif (dir = “R”) then
ret = hp + 1
else wscript.echo “Direction ” & dir & ” not recognized.”
end if
moveHead = ret
end Function

The more piddly part was in handling the “write to tape” section. If I was using an array (or, C++ and treating the string as a character array), I’d just overwrite the old value at wherever headPos is pointing in the string. However, VBScript doesn’t work that way, and doesn’t have a built-in function for this. So, I have to break the string in two, on either side of where headPos is pointing, then recreate the string as leftPart & newValue & rightPart. Again, though, I have to worry about the boundary conditions, where I’m at one end of the string, and if using the built-in left() or right() functions will bomb in an error.
Note that I’m using writeToTape as a procedure instead of a function. Unfortunately, VBScript requires a return value at the end, so I’m just forcing it to “true” and storing it to a dummy variable in the calling routine.

Function writeToTape(wttHP, wttVal)
lstr = “”
rstr = “”
if(wttHP = 1) then
rstr = right(tapeReel, len(tapeReel) – 1)
elseif (wttHP = len(tapeReel)) then
lstr = left(tapeReel, wttHP – 1)
else
lstr = left(tapeReel, wttHP – 1)
rstr = right(tapeReel, len(tapeReel) – wttHP)
end if
tapeReel = lstr & wttVal & rstr
writeToTape = true
end Function

I wrote countOnes() as a built-in function to the Turing machine. That is, I want the machine itself to tell me how many 1s are in a given strip of the infinite tape instead of making me count them manually. This is really useful if the input number is 138 digits long.

Function countOnes(coStr)
ret = 0
for i = 1 to len(coStr)
if(mid(coStr, i, 1) = “1”) then
ret = ret + 1
end if
next
countOnes = ret
end Function

Ticktacktoe Game Theory SMBC


I would like to propose a new law. Hoffmann’s Law says that if you go through Zack Weinersmith’s Saturday Morning Breakfast Cereal archives far enough, you will find a comic on whatever topic you are currently discussing.

 

Colossal Gardner, ch. 37


Who would have thought, that after the matchbox ticktacktoe computer that there’d still be enough material in the game leftover for another, completely dedicated chapter? But, that’s what we get in the Games and Decision Theory section, with Harary’s Generalized Ticktacktoe. Turns out that a much older variant of ticktacktoe used a 3×3 board and three counters each for the two players. The players took turns putting their stones on the board, and then moved the stones from cell to cell until one player got them in a straight line. According to Martin, “moving counter ticktacktoe is the basis for a number of modern commercial games, such as John Scarne’s Teeko, and a game called Touche.” He goes on to say that ticktacktoe can be generalized to larger fields, such as with Gomoku, or to play it on three or more boards for 3-, or higher, dimensions.

In 1977, Frank Harary (1921-2005), then mathematician at the University of Michigan, found a way to generalize ticktacktoe. He was known as “Mr. Graph Theory”, founder of the Journal of Combinatorial Theory and Journal of Graph Theory (yes, mentioned in the chapter on Ramsey Theory) and the author of the definitive book, Graph Theory. He wrote over 500 papers on the subject. Originally, Martin called the game Harary ticktacktoe, but Frank requested it to be named “animal ticktacktoe.” To start with, we can look at standard ticktacktoe as a two-color graph game, an “achievement game.” Use dots for the 9 cells, and connect them with lines as shown. You still have the two players, but they are each assigned a color, and they take turns coloring the points on the graph. First one to color a straight line of 3 points wins.


(All rights belong to their owners. Images used here for review purposes only. Graph theory approach to ticktacktoe.)

Now ask the question, “What’s the smallest square on which the first player can force a win by coloring a straight (non-diagonal) three-point path?” Answer, a square of two sides. Harary called this the board number, b, of the game, and it’s related to the Ramsey number in graph theory. After getting the board number, b, we can then ask, “In how few moves can the first player win?” Answer (try drawing this out yourself): three moves. This is the move number of the game, m. According to Gardner, “a player wins in standard ticktacktoe by taking cells that form a straight, order-3 polymino that is either edge- or corner-connected.” Below are the polyminoes of orders 1 through 4. Solomon Golomb developed the polymino terminology, but Harary preferred the usage of some of the earlier papers, and called them “animals.”


(Animal polyminoes of orders 1 through 4.)

Now comes Harary’s generalization: Pick an animal of any number of square cells (the order) and say that forming that animal is the goal of a ticktacktoe-like game. You don’t have to color the dots and lines shown above; using x’s and o’s is fine, or you can color the cells red and blue as you’d color the edges of a Ramsey graph game. The animal can be in any rotation or mirror image. Ok, now how we get the animal’s board number, or the length of the smallest square for which the first player can force a win? If the board number exists, that animal is considered to be a “winner,” if not, it’s a “loser.” If the animal IS a loser, the second player can force a draw, but can not win. Next, we want the value for m. If you have a one-cell animal, b and m are both 1. When b and m are the same value, the game is called “economical,” because the first player doesn’t have to waste a move to win it. For the domino, the only 2-cell animal, b and m are both 2. For the two 3-celled animals, the El is economical, and b = m = 3; the tic has b = 4 and m = 3, but this is for games that don’t allow diagonal lines.


(Order 5 polyminoes, grouped by winners and losers.)

The below illustration includes the proof that the Fatty of order 4 is a “loser” (games played rationally always result in a draw.) If you have the tiling at the top left, the first player first needs to draw a domino. To prevent this, the second player just has to take the other cell of the domino. If the first player can’t make a domino, they’ll never be able to draw a fatty, either. The rest of the illustrations show the other loser animals. Gardner adds that the proof that the straight 5-cell animal is a loser also bears on the game of Gomoku. On a 5-cell board, you want to draw a straight line. But, the second player can always force a draw if diagonals are not allowed. If diagonals ARE allowed, the first player can usually win.


(Visual proof that the fatty is a loser (second player can force a draw).)

Martin spends about a page talking about higher order animals, and then says that these variants can be fun ways to pass the time, if one or both players don’t know how to force the win. If you do try to select animals and then draw them ticktacktoe-like, it’s best to use a board that is b-1 (which is the smallest Ramsey graph where player 1 can’t force a win). You can also try misere versions, where the first player to draw the animal loses. These are “avoidance” games, and are actually harder to analyze. Martin spends some time giving examples. He also says that you can take the 2D forms and make them 3D or higher, as with polycubes or hypercubes.

In the addendum, Martin makes the statement, “if the first player always wins on a board of a certain size, he also wins on any larger board.” However, this is only true for square boards, not arbitrary graphs. The below graph was developed by A. K. Austin and C. J. Knight, mathematicians at the University of Sheffield, in England. On the left is a graph where 3-in-a-row wins. The first player wins by taking A. The second player has a choice of taking a point in either the larger or smaller triangle. No matter what B chooses, A counters by picking a corner in the other triangle. Player B has to block the threatened win, and A wins by taking the remaining corner of the same triangle. Ok, so expand the board by adding the two points shown on the right side below. The second player can get a draw by playing at B. If player one doesn’t start at A, player two can force the draw by taking A themselves.

No puzzles this week. Just a challenge to try playing these variants of the game yourself.

Penrose, Initial Comments (Part 1)


(All rights belong to their owners. Images used here for review purposes only.)

The third book I asked for as a Christmas present was Roger Penrose’s “The Emperor’s New Mind” (ENM). After seeing Penrose’s name show up so often in the Gardner book, and in reference to Penrose tiling, I figured I might as well see what he’s written himself. As I was surfing Amazon, I noticed that a lot of the customer comments on his books were that he’s very dense and difficult to understand as a writer and mathematician unless you’re at the grad student level. That seemed like an interesting challenge, and I finally settled on ENM because I did at one point want to write an SF novel involving AI.

Douglas Hofstadter’s book, “Godel, Escher, Bach,” (GEB) came out in 1979, and it placed him firmly in the “strong AI” camp (i.e. – as a proponent of the argument that we could eventually get computers that think like humans. Douglas has since moved on from that level of research into other things.) Penrose’s position is that there are various reasons why strong AI is impossible, and ENM (1989) was his first foray into explaining why. It generated a strong backlash from the strong AI people, including Marvin Minski, which resulted in two follow-up books: Shadows of the Mind (1996) and The Large, the Small and the Human Mind (2000). ENM was reprinted by Oxford University Press in 2016. One of the more controversial ideas is that quantum mechanics is involved in the human thought process, which doesn’t have much of a following yet.

Roger Penrose (Aug. 8, 1931 -) created the idea of the tribar, a 3D triangle with a twist at one end that turns it into an impossible object (kind of like a Mobius strip). He and his father (psychiatrist and mathematician Lionel) turned the idea into the “impossible staircase,” which M.C. Escher used for “Waterfall” and “Ascending and Descending.” Roger is an English mathematical physicist, mathematician and philosopher of science, Emeritus Rouse Ball Professor of Mathematics in the University of Oxford, and Emeritus Fellow of Wadham College, Oxford. He won the 1988 Wolf Prize for physics along with Stephen Hawking for their contributions to cosmology. So, he knows some stuff.

The problem with reviewing any science or math book written so long ago is that the material is going to be out of date, and you have to look at it strictly from the point of view of when it came out. So, naturally ENM is going to not have anything on strings or m-branes, and the quantum physics may be incomplete as we know it now. But, that’s kind of immaterial when looking at the history of AI research. Plus, there’s a lot on the historical side that’s still relevant and fun to learn about. I’m only 60 pages in, and the book is a full 440 pages. Right now, I’m on the chapter for the Turing machine, which is why I started writing this blog entry.

First, Roger talks about algorithms – what they are and how they’re used – and he gives Euclid’s process for finding the greatest common divisor as one of the earliest known algorithms. The process is simple (although I’d never seen this one before, which is why I like it). Take two numbers, call them x and y. Let z = abs(x – y). Then replace the largest of x and y with z. Repeat until x = y (if you go a couple more steps, both x and y go to 0) and then you have your GCD.

x = 144, y = 54, z = 90
x = 90,  y = 54, z = 36
x = 36,  y = 54, z = 18
x = 36,  y = 18, z = 18
x = 18,  y = 18, z =  0

It’s really easy to write this in vbscript, although you have to write your own functions for min() and max().

‘ Euclid’s Greatest Common Divisor algorithm

wscript.echo “Euclid’s GCD: ” & cstr(euclidGCD(144, 54))

function euclidGCD(x, y)
while (x <> y)
z = abs(x – y)
x = min(x, y)
y = z
wend
euclidGCD = x
end Function

function min(x, y)
ret = x
if (y < x) then
ret = y
end if
min = ret
end Function

The reason, though, for Roger to offer this algorithm is that he intends to implement it as a Turing machine. I’ve seen mentions of Turing machines before, but they never had examples of runnable code. And, for some reason, the computer science class pages I found on the net while preparing for this blog entry don’t seem to agree on why Alan Turing came up with his machine in the first place, which is why I like Penrose’s explanation. According to Roger, Turing wanted to work on a challenge first proposed by mathematician David Hilbert in 1901. Hilbert wanted to know if there was a purely mechanical, deterministic way to find all possible math theorems.

To do this, Turing proposed a simple machine. This machine would consist of a read-write head, infinite tape, and the ability to move the tape one position left or right. The tape would start with some string of 1’s and 0’s. This machine, called a “state machine,” would read the number on the tape directly under the head, and then make a decision for what to do next based on its current state. The starting state is “0”. For example, for state 0, if the number read is “0”, then write 0 back to the tape, keep the state at “0”, and move the tape one position to the right. If the number is “1”, write 0 to the tape, change the state to “2”, and move the tape one position to the right. and keep doing this until reaching a stopping condition.

There are a lot of issues to resolve before the machine can do anything useful, such as how to represent numerical values, and how to separate numbers. Since all we have are 1’s and 0’s, the easy way to represent numbers is as unary values – just a long string of 1’s, separated by a 0. 5 = five 1’s in a row; 100 = one hundred 1’s in a row. This makes for a long, slow program, but the tape is infinitely long, so we can hold any data we want. Alternatively, we can go binary, and use key values to represent separators, and other operators (that comes later).

Roger provides programs for adding 1 to a unary number, and for performing unary math to find Euclid’s greatest common divisor. He also has the binary algorithms for GCD and multiplying two binary numbers. And this is one reason I really like this book, so far – usable code.

Now, one point. At least one of the states is going to have a Stop instruction, and we can build the machine so that it pings, or gives some other indication that it’s hit the Stop. Then, to find out what the answer is from the machine, we read the number to the left of the head (by convention). This means that until we get the ping, the machine’s not done and the answer isn’t ready yet. One implication of this is that when people suggest using a Turing machine for calculating PI, e, or 1/3, we’re never going to get output out. These are infinitely long numbers, and there’s no “final” digit to output, so the machine never stops and we never get that ‘ping.’ On the other hand, we could rig the machine to pause when the next digit is calculated and to ping then. After reading the new digit, we could press the “continue” button and the machine would do the next set of calculations. But, there’d still never be a “final” digit for PI.

This then gets us to the halting problem. It’s easy to write a bad algorithm that never stops. But, how can we tell, from the outside, that the machine isn’t simply working on a really big number, or is in the middle of a really deep loop? In fact, this is kind of like working on the Mandelbrot fractal set; certain data points can generate incredibly small complex numbers without actually reaching zero. We can put a counter on the number of times we do the calculation and break out of the loop after 50 iterations, 100, 1,000, etc., but that’s a conscious decision we have to make in advance, and it’s completely arbitrary. With a Turing machine, reaching loop count = 1e^100 could either be because it entered an infinite loop, or simply because it’s not done generating the answer yet. From the outside, we can’t tell. And that’s the halting problem in a nutshell – is there a way to tell if any arbitrary algorithm will halt, or not, for any randomly selected range of input data (the algorithm for calculating the final digit of PI will never halt). If you know the answer, the Clay Mathematics Institute would like to talk to you.

Answer Sprouts


Puzzle: Why is Brussels Sprouts a joke?

Because the game must end in exactly 5n – 2 moves.
In standard form, the first player wins for an even number of starting crosses, the second player for an odd number. In misere play, it’s the opposite. If you introduce a beginner to Sprouts, you can then try talking them into betting money on the outcomes of Brussels Sprouts games.

Colossal Gardner, ch. 36


Sprouts and Brussels Sprouts.
The original pencil and paper game of Sprouts originated in Cambridge around 1967. It was co-invented by John Horton Conway and Michael S. Paterson (then a graduate student working on abstract computer programming theory). The game consists of putting n spots on the sheet of paper, and players take turns drawing lines between any two spots, and adding one new spot anywhere on the new line. The line may have any shape, but it can not cross itself, cross another line, or pass through a previously made spot. No spot may have more than three lines emanating from it. The game ends when one player is unable to draw the next line. The last player to make a legal move is usually the winner, but there is a misere version where the last player loses.


(All rights belong to their owners. Images used here for review purposes only. 3-spot Sprouts game.)

According to Gardner, 3-spot Sprouts is harder to analyze than ticktacktoe is, so beginners are advised to start with no more than 3 or 4 spots. An example game is shown above, starting with 3 spots and ending on the seventh move. According to Conway, the number of moves per game is within the limits of 2n and 3n – 1. The possible opening moves for a 2-spot game are shown below. The first player can always win the normal 3-spot game, and the second player can always win the 3-spot misere version.


(Initial spots and first player’s possible moves.)

A couple of pages in this chapter are given to descriptions of who can win the higher levels of the game, and a short history of how it came to be created. Then we get Brussels Sprouts, so-named because Conway thought it was a joke version of the game. Brussels Sprouts uses crosses instead of spots, and one move consists of extending one arm of one of the crosses to any other free arm, then adding a crossbar anywhere on the new line to make a new cross (two of the arms of which are already dead). Otherwise, the rules for winning and losing are the same. See below for an example game. Below that are some of the regular patterns that show up in a typical Sprouts game.


(Brussels Sprouts game, and recognized Sprouts figures.)

Puzzle: Why is Brussels Sprouts a joke?

 

The Beauty of Numbers in Nature, comments


(All rights belong to their owners. Images used here for review purposes only.)

The Beauty of Numbers in Nature, by Ian Stewart
Ian Stewart is the Emeritus Professor of Mathematics at the University of Warwick, England. He’s written over 140 scientific papers, including papers co-authored with Jim Collins on coupled oscillators and the symmetry of animal gaits (more on this later), worked with Dr. Jack Cohen and Terry Pratchett on the Science of Discworld books (1-4). He’s also co-written 2 SF books with Cohen – “Wheelers” and “Heaven.” And, he wrote the Mathematical Recreations column for Scientific American from 1991 to 2001. After all of this, I still hadn’t heard of him prior to reading this book. I’d been asked for Christmas gift ideas back at the beginning of December, so I went on Amazon and surfed around for any math and science books that caught my eye. Beauty of Numbers seemed promising, so that was one of the three I settled on (the other two were “Proof: the Science of Booze“, and anything by Roger Penrose).

It was funny, right after I opened Beauty of Numbers, I saw a couple nice animal photos, which I then showed to a Japanese friend that loves that kind of thing. But, she just raised her nose, sniffed, and said that the Japanese science magazine, Newton, does it better. As I continued to read BoN, I kind of had to agree with her. The subject Stewart chose is something that fits in with Newton – examples of symmetry, patterns, chaos and dynamic systems that show up in our universe (from the stripes and spots on animals, fish and birds, to spirals on shells, in weather patterns, and in galactic formations), with accompanying math and physics explanations. Except that Newton would do it in 40-50 pages, while Stewart took 212 pages, and they’d include tons of huge glossy photos and powerpoint graphs to illustrate the point. BoN, in turn, has only a few smaller photos or illustrations per page, and virtually no real math.

Another thing that struck me was that a lot of the topics he picked are also ones that showed up in Martin Gardner’s Colossal Book of Mathematics, (50 of Gardner’s best Scientific American Mathematical Recreations articles), including symmetry, topology, Penrose tiling, Escher paintings, chaos, and Conway’s cellular automata. But with less emphasis on the math and science parts. BoM reads like an updating of Colossal for adults that are curious about nature, but fear equations. The closest he gets to formulas is with an explanation of how to form Fibonacci numbers (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 84…) and how taking the ratio of two successive numbers (55/84, or 84/139) gets you closer to an approximation of the Golden Ratio. It gets kind of maddening after a while, especially when he talks about using mathematical oscillators (above) to explain how to model the way animals and insects walk, without actually saying what the model looks like mathematically. Personally, I would have loved to see a real example of system modelling for a horse versus a centipede, instead of just being told that he’d done work on this kind of thing.

Anyway, Ian starts out by asking “Does being a mathematician ruin one’s appreciation of nature, like knowing how a magic trick works lessens the wonder you feel when you see the trick done?” (Of course, his answer is that knowing how nature works just makes it that much more amazing.) He then uses a story of having seen fern-like frost formations on the window of his room when he was a child to ask “how do snowflakes form?” The famed astronomer Kepler had compiled a book on snowflakes and tried to answer that question himself. Ian then goes on to establish a vocabulary to hang the answers from, starting with the different kinds of symmetry (rotational, translational, reverse, mirror, and time), then moving into how Alan Turing’s work could be applied to show how chemical inhibitors and accelerators in animal skin, plants and seashells can create the spots, stripes, and apparently random patterns we can see in nature. It takes a while to get to Einstein’s theory of general relativity as it applies to gravity on a galactic, and even universal scale to explain how we get spiral galaxies, and a (possibly closed universe), and the discussions of symmetry breaking and chaotic dynamic systems. After all of this, he returns to the snowflake, and how its formation is dependent on factors like humidity level, temperature, symmetry, hexagonal crystal formation, wind speed and direction, and gravity to give us beautiful 6-sided ferns and flakes that all look unique.

Summary: There’s nothing “wrong” with BoN. It’s an easy read, and it does cover a wide range of topics. Names that Ian drops include Feynman, Kepler, Einstein, Alan Turing, Roger Penrose, Conway, M.C. Escher, Newton, and many others that are leaders in their fields. As mentioned above, it’s like an updated edition of Martin Gardner’s Colossal Book of Mathematics, and adding a little more on quantum mechanics, while name-dropping string theory and M-theory. But, it’s somewhat like Proof: The Science of Booze, in that there’s a lot of trivia that may give you something to talk about at parties, but it’s not going to make you feel seriously smarter. If you like Big Bang Theory, you’ll probably like BoN.

Starlings in Formation


I’d just finished reading Ian Stewart’s book on The Beauty of Numbers in Nature (I’ll post the review on Friday), when I saw the above photo in a friend’s Facebook post. This is exactly the kind of thing Stewart discusses in the section on chaos, and time symmetry in dynamic systems. Read the entire article, and check out the rest of the photos Daniel Biber took in the series.

Colossal Gardner, ch. 35


We now enter Game Theory with A Matchbox Game-Learning Machine. The first couple pages look at learning machines as a whole, and more recent computers as well, as threats to the human race. We first get Ambrose Bierce’s excellent Moxon’s Master (1899), about a chess playing machine that loses a game to its creator and kills him in a rage. Then there’s Norber Wiener, math professor at MIT, who expected computers to take on more and more complex tasks and push us into a suicidal war (don’t need a computer for that). Arthur Samuel was the first to program an IBM 704, in 1959, to review past games of checkers and learn from its mistakes. When this chapter was first written in 1962, computer chess programs were just showing up on the horizon, and some chess masters were convinced they could never be defeated by a machine, including American expert Edward Lasker in 1960. My, how things have changed.


(All rights belong to their owners. Images used here for review purposes only. Photo hosted on Flickr of a matchbox computer for ticktacktoe.)

But, the focus of the chapter is on making a matchbox computer. It was invented by Donald Michie, a biologist at the University of Edinburgh. He wrote about it in Trial and Error, an article that appeared in Penguin Science Survey 1961, vol. 2. It was a ticktacktoe learning machine called MENACE (Matchbox Educable Naughts and Crosses Engine), using 300 matchboxes. A drawing of a possible ticktacktoe position is pasted on each matchbox (because the machine always makes the first move only the patterns for the odd moves are required). Glass beads with colors representing possible machine plays from each pattern are placed in the boxes. Donald placed a V-shaped cardboard fence at the bottom of each box so that when you shake it, the beads randomly roll into the corner of the V to determine the next play. First-move boxes contain 4 beads of each color; third-move boxes have 3 beads of each color; fifth-moves have 2 of each color; and seventh-moves have one each. The machine’s move is determined by shaking and tilting a box, opening the drawer and looking at the color of the bead in the corner of the V. Boxes used during the game are left open until the game ends. If the machine wins, it is “rewarded” with three beads to each open box of the color used for that play. If the game is a draw, the “reward” is one bead per open box. For a loss, it is “punished” by removing the bead in the corner of the V. Eventually, the machine repeats winning plays and shuns losing ones. There’s no self-analysis of past games, just a rudimentary form of memory. (There’s a C++ program version at the codeproject.com.


(Hexapawn board setup.)

Gardner didn’t expect anyone else to use 300 matchboxes to make their own machine, so he created a game he called Hexapawn, using only 24 boxes with a 3×3 board and 3 chess pieces on each side. Only two kinds of moves are allowed:
1) A pawn may advance straight forward one empty square.
2) A pawn may capture an enemy pawn by moving one square diagonally. The captured piece is removed from the board.

There are three winning endings:
1) A pawn advances to the third row.
2) Capturing all of the enemy’s pieces.
3) Reaching a position where the enemy can’t move.

Martin called the machine Hexapawn Educable Robot (HER), and the drawings for the boxes are below. It may be difficult to figure out the “colors” of the arrows, but there are up to four moves possible from any given position, so you’ll need 4 different colored beads (or M&Ms or Skittles) maximum in each box. The robot always makes the even-numbered move. The numbers under the boxes represent the turn number (2 possible moves for turn 2, and 11 possible moves for turns 4 and 6 each). Martin included mirror positions in the drawings; otherwise you’d only need 19 boxes.


(Matchbox HER diagrams.)

To play, put inside a single bead for each colored arrow on the box. You make your first move, then pick up the box with the matching diagram, shake it, close your eyes, open the drawer and take out one bead. Close the box, put it down, put the bead on top of the box, and open your eyes. Check the color of the bead, and move the machine’s pawn as indicated on the diagram of that box. Repeat until the game ends. If the machine wins, replace all the beads and play again. If it loses, remove only the bead for its last move, replace the other beads and play again. If a box is empty, the machine has no non-fatal move and it resigns. In this case, remove the bead of the preceding move. The below chart shows HER’s learning curve for the first 50 games.


(HER learning curve over 50 games.)

Martin suggests that you could develop your own rules for rewarding HER, and you could construct a Hexapawn Instructable Machine (HIM) with new rules to play against HER (you’d need to draw new diagrams for the odd-numbered plays for both sides). Stuart Hight, director of research studies at Bell Labs in Whippany, NJ, built a machine called NIMBLE (Nim Box Logic Machine) for playing Nim with three piles of three counters each. Other choices include simplified versions of Go (on the intersections of a 2×2 checkerboard), or minicheckers (below). Martin was of the opinion that the below right mini-chess board is still too complicated to implement, but that it’s within the realm of a computer program.


(Minicheckers and Minichess board layouts.)

In the addendum, Martin mentions a math club that built 2 hexapawn machines, and then told two students that they’d be playing against each other. The two students were put in separate rooms, and the box computers were in a third. The students couldn’t believe who their opponents really were when they were led to the third room at the end of the experiment.

Martin also mentions how many chess players got angry at the idea of machines beating them, and talks about Fritz Lieber’s SF story of a machine tournament, The 64-Square Madhouse (If, 1962).

Puzzle: None.
Challenge: Make your own machine for a 5×5 checkerboard game.

Advertisements