Marion Tinsley: 20 Years Later

Time is relentless. I cannot fathom that 20 years have passed since the day that Dr. Marion Tinsley -- World Checkers Champion extraordinare -- passed away. Between 1990 and 1994, Marion was my obsession, as my Chinook team battled him for supremacy at playing checkers. His passing left a deep emotional scar on me, as the follow story relates (taken from my book One Jump Ahead, Springer-Verlag, 1997 and 2009).
-------

I talked with Marion Tinsley in January during the Lafferty match. At the time he sounded good, and he was in excellent spirits. He wanted to play Chinook again, possibly as soon as August. “Any time you feel up to it, we’re ready to play,” I told him. The prize money left over from Boston ensured that another Tinsley-Chinook match would happen once Marion’s health recovered. I never mentioned it to him, but the reality of the situation was that there would never be another match like London or Boston. The Boston debacle [the unfortunate ending of the 1994 World Man-Machine Championship] guaranteed that big-name sponsors wouldn’t be interested in sponsoring a high-profile checkers match again.

A few days later I heard that he had suffered a setback. When I called him up to find out how he was feeling, Marion told me that he was good but weak. He described his recent chemotherapy treatment, his last of six, as having “burned my insides.” Just a minor setback on the road to full recovery, he asserted. When I spoke to him a few weeks later, he sounded much stronger and more optimistic about playing competitive checkers again.

I hoped that Marion would write the promised letter to the ACF, [American Checker Federation] but I didn’t want to bother him about it. Obviously, he had more important things on his mind.

In March he decided to go to Houston, Texas, to be near his sister, Mary Clark, and her family. On March 16 I received the bad news: new tests done by the doctors in Houston revealed that Marion had cancer in his bone marrow, pancreas, and liver. The news stunned everyone; for the first time I realized that Marion was dying. One should never take cancer lightly, but somehow I was sure that he would pull through. Marion had fought adversity before, and he had always won. Fighting cancer of the pancreas was a formidable challenge, but from everything Marion had told me, I naively thought that he was winning the battle. Now the painful truth sank in: I’d been living an illusion. Marion was going to die. It was hard to believe. 

Marion Tinsley (1927-1995)

For a week I tried to deny the inevitable. It just couldn’t be happening. But on March 26 Mary Clark told me that Marion’s condition was deteriorating. He was in intensive care and very weak. He had only a few months, or maybe weeks, to live. I heard the words, but I just couldn’t comprehend them. 

In my life I’ve only had to confront the death of a friend or family member a few times. In every case it happened suddenly, and I had no chance to prepare for it. In Marion’s case I now had advance warning. I wanted to see him one more time. Because of my teaching commitments I asked my travel agent to arrange a trip to Houston for the weekend of April 1 and 2. 
 

On March 29, I sent the following e-mail to the Chinook team members: 

Tinsley’s cancer has spread and he is in critical condition in a Houston hospital. He has only a few months/weeks to live. I am flying down to Houston this weekend to see him. I have spent the last 6 years of my life obsessed with catching him. At the end of the rainbow, there is no pot of gold, only the stark reality of the cruelty of life.

Later that day I canceled the trip. I wasn’t able to find a reasonable connection to Houston since most of the flights were already full. I could take a contorted flight path from Edmonton to Houston, spend a day with Marion, and then return via a roundabout way, getting into Edmonton at 2 A.M. on Monday, April 3, just in time for my 8 A.M. class. After a vain attempt to find a better arrangement, I decided to postpone the flight to the next weekend when I would have a better flight connection. 

On the morning of April 1 Mary Clark told me that Marion’s condition was deteriorating rapidly and that time was running out. The promise of a few months from only a few days before was wrong. On April 3 Marion was going to move from the hospital to his sister’s home to die. Now I knew that I couldn’t wait. I arranged to fly to Houston in the early morning of April 4. 

I was in touch with Marion every day now, talking for as long as he had the strength. Whenever I talked to him, he was in good spirits, but his voice was weak. On Sunday, April 2, we talked at length. He sounded good for the first few minutes but his strength ebbed as the conversation carried on. He said that he was “ready to go”; to see Jesus and his friends and family. Before he left, however, he said that he had two more things to do. First, he wanted to write a letter to Bob Bishop  [President of Silicon Graphics, the sponsor of the Man-Machine match] thanking him for his kindness in Boston. Second, he wanted to fulfill his promise to me and write a letter to the ACF setting the record straight about the events in Boston. I told him it wasn’t necessary; there were other things more important right now. But he insisted he would write the letters. 

Marion reiterated several times that he was “ready to go.” He was intrigued about a dream he had had the night before. He wouldn’t tell it to me; he wanted to wait until the next day to tell his mentor, Brother Walden. Apparently it had something to do with “boat people.” He felt that the dream was very important, and he wanted to understand its meaning.

Later that day, Rob Lake talked with Marion:

He was glad to hear from me and we talked for a little over five minutes. At the time he was with his sister and nephew, and a nurse was administering oxygen to him. He sounded weak and he was coughing a lot. He mentioned his main regret during the past four years was not writing a book about his experiences with Chinook. I told him that Jonathan was coming to visit him and he would be bringing something with him that Marion would find very interesting (I did not tell him it was the manuscript for the book Jonathan has been writing about Chinook. We also talked briefly about Dallas and his visit to Edmonton last summer, but at times it was difficult to understand what he was saying.

Mary Clark phoned me in the afternoon of Monday, April 3. She told me that Marion had lapsed into a coma. Brother Walden was to arrive at the hospital that evening. Mary was sure that Marion was using every ounce of strength to hold out until he arrived. 

I was very tired on Monday April 3 and went to bed uncharacteristically early. The telephone rang shortly after 10 P.M., and my hand stumbled in the dark trying to find the receiver. As soon as I heard Mary’s voice, I knew what she was about to tell me. Marion Tinsley, an extraordinary man whom I felt privileged to have known, was gone. He stayed alive long enough for Brother Walden to arrive and give his blessings, and then he passed away peacefully. 

There was no possibility of sleeping now. I left my bedroom to sit downstairs in the dark and be alone with my thoughts. I’d known Marion for less than five years and had met him on only six occasions (Tupelo 1990; Edmonton 1990; Petal 1992; London 1992; Edmonton 1994; Boston 1994), yet he had an enormous impact on my life. I was consumed with my quest to defeat him with Chinook. All I could think about now, however, was his friendship, support, and talent. I went to my computer and sent out the following message to the electronic world: 

From: jonathan
To: ChinookTeam rec.games.chess rec.games.abstract
Subject: Marion Tinsley 1927-1995
Date: Monday April 3 22:48 19

Marion Tinsley passed away quietly tonight after battling cancer for the past eight months. As recently as January, he thought he had won the hardest battle of his life, but a relapse revealed that the cancer had spread.

Tinsley was the greatest checkers player who ever lived and, arguably, the most dominant champion in any competitive sport. Over the last 45 years of his career he remained undefeated, winning every match and tournament he played in. Over the thousands of games played in this period, he lost less than 10. He was as close to perfection as is possible in a human.

As a man, Tinsley was exceedingly kind and loved by everyone. He leaves behind many friends.

He was a great friend of the Chinook team. He could have said “no” when faced with the prospect of defending his world championship title against a computer. Instead he accepted the challenge, relishing the chance to face some tough opposition. We are grateful for the opportunity he gave us, and the privilege of playing the very best.
We shall deeply miss him. Rest in peace.

The last time I saw Marion was when I visited him in the hospital in Boston on August 21, 1994. I had my chance for a last visit with Marion, but I blew it. I wanted to see him again. I wanted to say “thank you.” I wanted to show him the book I was writing on Chinook. I missed my chance. My procrastination will haunt me for the rest of my life.

Maligne Canyon -- 30 Years and Counting

On the January 30th weekend, I organized my 30^th annual Department of Computing Science winter retreat to Jasper in the beautiful Canadian Rocky Mountains. It was a wonderful trip – great company, spectacular scenery, invigorating winter sports, relaxing pools, and, for some, (expensive) shopping.

Jasper in the summer is gorgeous, and the Icefields Parkway that connects Banff to Jasper is considered one of the most scenic drives in the word. I became infatuated with the winter side of Jasper when I visited the town in January 1985 and had my first experience going to the bottom of Maligne Canyon. Having moved to Alberta from Toronto just over a year before, it was a moving experience to behold the beauty of nature in a setting that, quite frankly, does not exist in Ontario (they even call Blue Mountain a mountain – what a joke!). I was hooked, so for the following winter I decided to organize a Department of Computing Science trip to Jasper, ostensibly as a "ski trip". For me personally, the skiing was secondary to a visit to the spectacular Maligne Canyon. At the time, I had no inkling that the trip would catch on and still be going strong after 30 years.

In the spring and summer, Maligne Canyon is the home of a raging river. The water is 50 meters below the ground as it flows through the canyon; all you can do is stand on a bridge and look down at the torrent of water battering its way through the narrow passageway. But in the winter, the river is frozen and it is easy to get down to it and walk on its frozen surface.

Maligne Canyon is part of a long underground cave system. In fact, the Canyon may have once been a cave whose roof fell in. In the spring and summer, melting causes the river to rise as a massive amount of water tries to force its way through the narrow corridor. However, below the riverbed are large caverns. In the winter, there is little water in the river and it drains into the cavern. Hence, in some winters all the water disappears under ground leaving a dry river bed. If there is water flowing, you can easily find places where the water seeps through cracks and disappears into the ground. In the summer it is the reverse; you can find places where the water is spurting out of the ground, the consequence of the underground caverns being full.

A Maligne Canyon trek consists of going to the north end of the Canyon where the walls are the lowest, climbing down onto the river's frozen surface, and then walking back into the Canyon. Along the way you will find frozen and active waterfalls, impressive ice carvings (the artistic side of Nature), large rooms carved out by thousands of years of erosion, and even the odd fossil. At one place you can crawl on your belly into part of the underground caverns.

Jasper in the summer and the winter is a magical place. Most people visit the Rocky Mountains in the summer, and those who come in the winter usually do so for the skiing. Maligne Canyon is spectacular all year round. In the winter one must go to the bottom to see its inner beauty. In the summer from the top you can look down incredulously at inaccessibility of the winter places that you visited.

I have been to the bottom of Maligne Canyon every year since 1985, oftentimes more than once per year. Perhaps my annual winter retreat will hit the 50 year mark. Stay tuned!

 

Looking down 50 meters into the Canyon. In the summer, the canyon is filled with the water of a raging water. In the winter, the water disappears into the underground caverns, leaving the bottom of the gorge walkable in most places. wikipedia.org

A dozen intrepid adventurers ready to start the Maligne Canyon trek.

The “Shower Curtain” waterfall. Some years the mist from the flowing water freezes, creating a thin curtain of translucent ice that covers the entire waterfall (hence the name). Not so this year.

The river surface freezes, and then the water underneath the ice drains way into the caverns below. This creates a cavity, allowing one to crawl underneath the ice and onto the actual riverbed. Here an adventurer is emerging from underneath the ice.

At the bottom of one of the frozen waterfalls.

The foot of the Queen of Maligne waterfall. An intrepid soul (not from our group) is preparing to climb up the face of the waterfall.

Poker Perfection

On June 8, the paper "Heads-up Limit Hold’em Poker is Solved" by Michael Bowling, Neil Burch, Michael Johanson (University of Alberta), and Oskari Tammelin (independent consultant from Finland) appeared in the prestigious journal Science. This paper reports on an outstanding research result: a popular version of two-player poker has been solved by computers. The University of Alberta program, named Cepheus (poker.srv.ualberta.ca), will not lose in the long run against any opponent (and likely will win since humans make mistakes). Computer perfection. This was the culmination of research into computer poker at the University of Alberta that began in 1995!

Many games have been solved before. Tic-tac-toe is a trivial game for which the perfect-play result (draw) and a strategy for achieving that result are known. The most challenging popular game that has been solved is 8x8 checkers (also called draughts). My team started looking at checkers in 1989, became the strongest checker-playing entity in the world in 1994, and achieved perfection in 2007. Perfect play leads to a draw. One of the challenges of checkers is the sheer size of the search space – the roughly 500,000,000,000,000,000,000 (10 to the 21st power, or 500 billion billion) possible positions.

On one dimension, the checkers problem is harder to solve than poker. Two player Texas Hold-em poker has a search space of "only" 10 to the 18th power (a billion billion scenarios). However, poker positions can be classified into so-called information sets, of which there are only 10 to the 13th power to solve.

On another dimension, poker is harder to solve. Poker has to deal with imperfect information (the opponent's cards are hidden) and randomness (the deal of the cards), whereas checkers is a perfect information game (all information about the state of the game is available to both players) without randomness. This distinction has consequences for the computation of the perfect strategy. In checkers, each position could take on only one of three values: win, loss or draw.  In poker, betting decisions are necessarily based on probabilities (because of the unknown information and the random scenarios that can occur). The Cepheus calculations had to iterate on each betting decision, gradually refining the probability of folding, calling, and/or raising. 

From the impact point of view, solving poker has greater potential to change the world. Poker is a microcosm of many real-world problems, including negotiation and strategy applications. Many domains can be couched as "games", including politics, environment, epidemics, and military. In fact, after we solved checkers in 2007, the U.S. government sponsored two workshops on Solving Games of National Importance. As John von Neuman, the father of the modern computer, once wrote: "Real life is not like [checkers]. Real life consists of bluffing, of little tactics of deception, of asking yourself what is the other man going to think I mean to do. And that is what games are about in my theory."

From left to right: Jonathan Schaeffer, Murray Campbell, Michael Bowling, and Gerry Tesauro.
Photo taken at the annual AAAI conference (Austin, Texas) on July 27, 2014.

The picture shows the lead authors of the programs that have solved (real or perceived) popular games. All four have a University of Alberta connection!

• Jonathan Schaeffer -- led the creation of the checkers program Chinook, the first world champion at any game (1994). Solved checkers in 2007. At the University of Alberta since 1984.
• Murray Campbell -- one of the three lead authors of Deep Blue, which in 1997 defeated World Chess Champion Garry Kasparov. Received his B.Sc. (1979) and M.Sc. (1981) from the University of Alberta.
• Michael Bowling -- led the creation of Cepheus, computer perfection at two-player limit Texas Hold'em poker. Joined the University of Alberta in 2003.
• Gerry Tesauro -- developed a landmark machine learning program, TD-Gammon, for backgammon and achieved super-human status in the later 1990s. His program is based on University of Alberta professor Rich Sutton's temporal difference learning algorithm.

And of the future? No-limit poker is harder to solve because of the wide range of possible betting scenarios. And if this is not hard enough, playing strong three-player poker is difficult. So, despite the crowning achievement of almost 20 years of research, the University of Alberta's Computer Poker Research Group has another 20 years of research ahead of it.