THE OBSESSIONS ISSUE
The week of September 20, 2015
Obsessions_SmallestChessProgram_JLongo_2500px

The bitter rivalry behind the world’s smallest chess program

By Chris Stokel-Walker

“You only have one life and so many minutes in your day—in your life—to accomplish things and to focus on things that matter,” Olivier Poudade says. His heavily accented voice comes crackling down the line from his cellphone, bounced and beamed from Savoie, in the French Alps, where he’s vacationing and visiting his mother. While overlooking the mountain ridges of the Tarentaise Valley, the 44-year-old Frenchman is talking about the things that matter in life, and how the time in which we have to do them is finite and always diminishing, ticking away whether or not we spend it wisely.

With his time—he figures about 600 hours over three months—he wrote a computer game called BootChess. It’s a chess game crammed into an impossibly small 487 bytes of code; the Wikipedia page explaining the rules of chess, in contrast, runs 53,162 bytes, more than 109 times larger. When he released BootChess in January 2015, it broke a 32-year-old record for the smallest computer implementation of chess on any platform. (That’s the claim, anyway; there’s some debate over rules like castling and en passant being sacrificed in the name of space.)

For Poudade, this was an accomplishment that mattered. News outlets like the BBC and Mashable covered his program as something of a curiosity, comparing its length to that of a pair of tweets and noting how supercomputer chess machines like Deep Blue can topple grandmasters, while BootChess plays at the novice level. Poudade, though, ignores the caveats. He’s after something closer to a pure intellectual exercise, a trial of code optimization and programming elegance. And, in some ways, his is a tale of man versus machine: “What you see now is people who have cellphones but they don’t control the technology; the technology controls them,” he says.

Why would someone someone obsess over writing the world’s smallest chess program? Poudade has a complicated answer, involving paying his respects to a long-ago programming genius, drawing attention to his own coding group, and proving a thing or two to young-whippersnapper coders. That’s what motivated him to devote hundreds of hours to code what is ultimately a tiny black-and-white grid of text and numbers. Poudade’s chasing something like the Platonic ideal of computer chess programs.

He did something that mattered; he had the record. But, as they say, records are made to be broken.

boot-chessBootChess | Photo via Olivier Poudade

• • •

In mid-1982, a small quarter-page advert appeared in a computer hobbyist magazine. For just £5 (about US$26.50 today), the ad’s pixelated block text promised a computer chess program with “absolutely flicker-free display” and an opponent who would make its move on average just six seconds after yours. “Sensational 1K ZX 81 Chess,” claimed the copy, and ignoring that today-inexplicable numerical assemblage, the important points are “sensational” and “chess.”

SinclairUser00300061

The sensation was that you could play chess on a cheap, underpowered wedge of plastic and chips called the Sinclair ZX81 (which, despite its limitations, nevertheless sold more than 1.5 million units). At the time, computers were closer to science projects than the sleek consumer electronics we know today; they often shipped as kits to be assembled by the buyer. Peter Jennings coded the first game program for home computers, Microchess, which was sold for the Kim-1 in 1976. He remembers computing in those days as almost a test of will: “You want to do something? That’s the tool you’ve got. You do it.”

Poudade’s after something closer to a pure intellectual exercise, a trial of code optimization and programming elegance.

An article in Scientific American about the state (not very good) of chess-playing computer programs inspired Jennings to try his hand at one. In fact, the idea of a chess-playing computer went back to Claude Shannon, one of the pioneers of information science; British mathematician Alan Turing, in 1951, was the first to publish a computer program that could play a full game of chess. By the late 1970s and early 1980s, the first generation of game programmers working with home computers needed clever workarounds and pristine, concise code to push the available technology to meet their ambitions.

That included chess games, and that’s what made 1K ZX 81 Chess so sensational. The sole programmer, an Englishman named David Horne who listed an address in Crowborough, a quaint town in the county of East Sussex, had crammed a working chess game into the 1KB of space available on the Sinclair ZX81. By most accounts, computer chess at the time was in a pretty sorry state, but Horne’s work later became known as the “greatest program ever written” (according to a kuro5hin.org thread) and “history’s greatest game programming feat” (according to a Retrogaming Times Monthly column). Horne had brought chess to the ZX81, and he’d done it in 672 bytes. Horne—the departed champion whose record went on to taunt and inspire Olivier Poudade in equal measure—incidentally, could not be located for this article.

Olivier_Poudade1Olivier Poudade

Horne later explained how he’d crammed so much functionality into so few bytes. (Fittingly, he did it in fewer than 1,000 words.) More than 30 years later, in October 2014, Poudade’s daughter, who he has custody of as a single father, was playing chess. That got Poudade thinking: Wouldn’t it be incredible if today, people could boot a PC, any old crappy thing, and play chess quickly and easily while using less than 1K of information? What if that were possible?

Horne had proven in 1982 that it was possible, but in 2014, it seemed like a masochistic pursuit. After all, the average smartphone can run a chess app light-years more advanced than 1K ZX 81 Chess. Feng-hsiung Hsu, who designed the IBM machine that beat Garry Kasparov in 1997, wrote in 2007 that humans don’t stand a chance against computers playing chess. “The iPhone,” Peter Jennings says, “could be beating grandmasters, no problem.”

“What you see now is people who have cellphones but they don’t control the technology; the technology controls them.”

Poudade wasn’t interested in building another Deep Blue or rehashing any of the hundreds of chess apps already out there. And while he likes chess (though he’s admittedly not that great at it), he also wasn’t that interested in getting beaten by another chess app. “There’s no point to play and lose all the time against a computer,” he says. “It’s fun to sometimes win if you put your mind to it.”

He was looking for a project that would matter. Something worth his time. “I was looking for a challenge, which is always the initial part,” he says. “It helps to alleviate burdens, daily burdens, and allows you to escape.”

So he escaped into his project, looking to code the smallest chess program yet. At first, he was stymied. “I looked, and it seemed impossible, because there were no shortcuts,” he says, “and David Horne had nailed it so much already.” Three decades on, Horne’s code held up.

But Poudade pushed on, snatching hours after work and after his daughter had gone to bed. He had other motivations, too: the upcoming 30th anniversary of Red Sector Inc., a coding club he belonged to, an occasion he wanted to mark with something special and attention-grabbing. Mostly, though, he simply admired Horne’s code, and his program became, in part, an enthusiastic homage to such efficient work.

“I retook some of his techniques,” he admits. “I did.” He simply couldn’t improve on them. For example, in BootChess the king’s moves don’t have their own logic; instead, it’s a copy of the queen’s move logic, but limited to a single square per turn. He credits Horne’s work in a lengthy history he’s written on the creation of BootChess, and in the NFO file of the program. So while creating the world’s smallest chess program was an act of competition, for Poudade it was also an act of appreciation—a way to recognize superior skill.

He gave the absent David Horne all due credit. That was part of the rules he’d established for himself. So when a new challenger arrived, with a smaller chess game and, Poudade believes, insufficient credit given to the coders who came before—well, you can understand why Olivier Poudade isn’t the biggest fan of Óscar Toledo Gutierrez.

• • •

Like any 5-year-old kid, Óscar Toledo Gutierrez wanted to mimic his father, a computer programmer also named Óscar. He sat on his father’s lap while his dad punched code into their home PC. “I wanted to put my hands on the computer,” he says, remembering the compulsion, “but I was not allowed to do that because he was writing an important program.”

“I was looking for a challenge. It helps to alleviate burdens, daily burdens, and allows you to escape.”

Now 36 and living in Mexico State, Mexico, he follows in his father’s footsteps, working for the family firm, Familia Toledo. He writes operating systems and applications—but no games. “You can say my hobby is to write games,” he says.

OskarToledoÓscar Toledo Gutiérrez | Photo via Chess Programming Wiki

Like Poudade’s, those games are very small. He can’t explain why, can’t quite articulate this compulsion. “It’s not easy to write a small program,” he ventures. “It’s easy to write a big program, but a small program is not easy.” (Like Pascal once wrote, “I made this letter very long, because I did not have the leisure to make it shorter.”) His
personal website lists all the small chess programs he’s written: in Javascript, in C, in Pascal. And like Poudade, he’s made coding sacrifices. “I can put all the moves in chess, but the intelligence of the computer is less,” he says.

When he heard about BootChess, he had a simple reaction: “Ah well, another guy who has his 15 minutes of fame.” Then he set to work. He wrote a chess program again—this time in assembly, a low-level programming language that typical produces more efficient code. He sat down this year on Jan. 28 at 9pm and by 6:17pm the next day he had a finished program. After another half-day of debugging, he had his program: Toledo Atomchess, 481 bytes, 1.2 percent smaller than BootChess.

Poudade wasn’t happy. But he didn’t think he’d simply been beaten. He thought he’d been cheated. “Either this guy has an IQ of 17 Einsteins, or he’s insulted three months of [work] every night, five hours after putting the kids to bed and having to wake up in four hours,” he says. “Do you understand? Three months on one side, and on the other side … two days. What does that say to you? It’s bad.”

Poudade thinks Toledo Gutiérrez stole his code, then optimized it and rebranded it as Toledo Atomchess. “If you steal my code and you don’t put my name on it, or say it was inspired by this guy and this guy’s work, then you are a code ripper. That’s very badly seen for 30 years. Very badly seen,” he says. He contrasts it with his own respect for the previous record-holder. “Even if I didn’t copy anything from David Horne, I gave him credit; I honored his memory,” he says. “That’s what people do.”

He’s publicly called out Toledo Gutiérrez, writing that his work was “just blatant code-ripping.” And now the comments of his BootChess code include this dig:

Screen Shot 2015-09-18 at 11.30.31 AM

Gutiérrez vehemently denies any copying. “I didn’t see his code on purpose” to avoid prejudicing the work, he says, adding that Poudade brought the challenge on himself. “I didn’t have any plans to write my chess in assembler code,” he says. But friends pointed him toward the BootChess readme file, where Poudade writes that before him, nobody had matched David Horne’s record, “despite numerous false and misleading claims.” Immediately after, he singles out two of Toledo Gutiérrez’s earlier chess games. The implication is clear. And so, it appeared, the gauntlet had been thrown.

Unlike in chess itself, there’s no checkmate to be had, at least not yet, and perhaps not ever.

I ask Gutiérrez how he felt. He pauses for a long time, carefully choosing his words.

“Well, it was a lack of respect.” He laughs awkwardly. “When I saw the mention, I didn’t like it, so I had to write something better.”

• • •

It’d be hyperbole to say Olivier Poudade and Óscar Toledo Gutiérrez hate each other. Even “enmity” would be too strong a word, particularly on the part of the Mexican, with his calm, easygoing demeanor. And though they’re in competition—and though the accusation of code-ripping comes very close to insulting a programmer’s honor—they have a grudging respect. “I respect his work, because it took a lot of effort,” says Toledo Gutiérrez. “Let’s not put the guy at fault, because he is worthy,” says Poudade. “I respect what he did as a programmer. I like what he does; a lot of people like what he does. He started his own kingdom. The small chess thing was his.”

That’s true: Toledo Gutiérrez wrote his first chess program in BASIC around 1986, when he was 8. He was at a friend’s house, itching to play but without a chessboard. So he wrote a program. “At this point I have the whole algorithm in my head,” he admits.

But Poudade can’t simply offer his respect. He needs to psychoanalyze his competition. “On his page he tries to be a young brilliant person,” he says, “a wizard, a genius, like Einstein.” He remembers a 14-year-old programmer who attended a computing challenge Poudade had organized, wowing everyone with his prowess. But when the Frenchman took him aside, he realized the student didn’t understand how the algorithm he used actually worked. “He had learned it like a poem,” he says. “I felt that he had immense pressure from his father to appear as a unique, bright person among his peers. This is what this guy Toledo appears on his page like.” But again, Poudade says he respects Toledo Gutiérrez.

He still wanted the title of smallest chess champion, though. “I removed the row and header just like him, just to gain back the record,” Poudade says. His revised program, initially 487 bytes, and undercut by Toledo Gutiérrez’s 481 bytes, is now just 468 bytes.

Unlike in chess itself, there’s no checkmate to be had, at least not yet, and perhaps not ever. How small can the code get, and is a chess program still really a chess program if ever more rules and features are sacrificed for size? Their rivalry continues, and now it’s Toledo Gutiérrez’s move. “I still can make it smaller,” he says, “only I need to dedicate more time to it.”

Illustration by J. Longo