Checkpointing Checkers

Checkpoints are a technique for improving a program's fault tolerance by preserving the program's state. Checkpoints can be used to recover after a program crashes or used to save the state for later analysis. They are literally dumps from the program that are sufficient to reconstruct the program's current state.

The Powerful Wizard Marcus was traveling to the city of South Atlantis for the annual World Checkers Championships. The competition was legendary, and it attracted all of the best checkers players in the known kingdoms. This year the heavy favorite was Jennifer "King Me" Stratovarious. She had won thirteen of the major competitions in the last six months. Some people said that she was unbeatable. Any match where she played was guaranteed to be exciting. And, Marcus had front row tickets to the finals.

However, Marcus realized that there was a problem as soon as he arrived at the preliminary rounds. The players were playing a frantic pace. They almost looked panicked.

"What is going on?" Marcus asked King Fredrick, who had also journeyed to South Atlantis to watch the world championships.

"They are playing checkers." answered the king.

"I can see that. But, why are they playing so quickly? It almost looks as though they are trying to race through the game."

The king shrugged and returned to watching Jennifer quickly destroy a young novice from South Patagonia. Marcus had never seen a game won in so few moves. Or, for that matter, played so quickly.

Unfortunately, all too soon he understood the reason behind the players' urgency. South Atlantis happened to be the windiest city in the world. Twenty-three minutes into the preliminary round, the entire building started to shake with the force of an industrial paint mixer. Despite the strong walls and shuttered windows, wind swept through the hall. The oil lamps swayed dangerously, people fell down, and the checkers slid off the boards.

After only half a minute, the wind stopped and the contestants began to gather their pieces off the floor. The contestants that had been winning groaned and griped loudly. "This is unfair!"

"Why are they hosting the tournament in such an awful location?" And, in contrast, the contestants who had been on the losing end of the game smiled quietly, for they now had a new chance to win. Only three games had finished before the wind-storm. The winners of those games smiled broadly; they had beaten the disaster.

"Unbelievable," proclaimed King Fredrick. "All those games were lost."

"Bah." declared Marcus. "Inefficient and stupid."

"What can they do? All of those checkerboards crashed to the floor before the games were finished. There was nothing that they could do." Insisted the king.

But, Marcus had stopped listening. Instead, he was wandering down to the nearest competition table.

"Excuse me, there. Why do you make them replay the game?" Marcus asked the judge at that table. "Why not use checkpoints?"

"Checkpoints?" asked King Fredrick, who had followed Marcus down to the floor.

"Yes. Write down the entire state of the board after each move. That way, if the pieces are upset, you can reproduce the entire board from the most recent checkpoint. It would save your games from being lost." explained Marcus.

"HA! Checkpoints?" cried Jennifer "King Me" Stratovarious from behind. "That would be too slow. Have you ever seen how fast I can play checkers?"

Marcus had indeed seen how faster she could play. He had to admit that checkpointing every move could only slow down someone of her caliber. In fact, Marcus was surprised the even a judge could keep up with her.

Marcus grinned widely. "Perhaps I can be of service." he offered. Then, without any more explanation, he picked up the table's timing clock and waved his hands over it. After a moment he set it back down.

King Fredrick looked at the clock. It appeared mostly unchanged, except that it now had two additional buttons "Save" and "Restore".

"May I?" inquired Marcus. Then, without waiting for an answer, he pressed the "save" button. The clock chirped once like a bluejay. Marcus smiled widely at the assembled crowd and, with a quick flick of his hand, knocked the table's board onto the floor. Checkers flew everywhere. The judge and both players scowled at him.

"Now, observe." commanded Marcus with his best wizard's voice. He reached over and pressed the "Restore" button. Magically, all of the pieces flew up off the floor and reassembled themselves on the board. In less than a second, the full state for the board had been restored.

Everyone gasped and burst into applause.

"Woah." King Fredrick said.

Then, Marcus felt a tap on his shoulder. Behind him stood four hundred and ninety-nine other table judges. Each judge held their table's timing clock out toward Marcus and looked at him expectantly. As he took the clock from the nearest judge and started his spell again, Marcus suddenly regretted having felt the need to show off.