Odd king tours on even chessboards, revisited

Almost 30 years ago this year, a former student Michael Fourte and I wrote a combinatorics paper (original paper, 1997) with the title above, eventually published in the now defunct Journal of Recreational Mathematics 31(2003)173–177.That paper was a pleasure to write, but was it correct?

With AI tackling open math problems left and right, I asked AI to review our paper and correct it, if any errors were found. In fact, I expected no errors but it turns out the main theorem was not as carefully stated as it should be, and some conjectural statements were not formulated in the best way (though our proofs were correct). A corrected version, made with the help of AI, can be found here: 2026 corrected version. An AI-written report on the paper with some possible directions for further research is here: 2026 AI-written report/review.

“Invariant distributions on the n-fold metaplectic covers of GL(r,F), F p-adic”, revisited

Over 25 years ago I wrote a paper with the pretentious title “Invariant distributions on the n-fold metaplectic covers of GL(r,F), F p-adic” (J. Fourier Anal. and Appl. 7(2001)343-358.). In fact, it was on such invariant distributions restricted to a very special class of functions where everything was much simpler to describe.

Inspired by a blog post of Professor Alonso Castillo-Ramirez, I asked AI to look over this paper. Here, by AI I mean using both chatGPT-Sol and claude-Fable or claude-Opus, teaming one up against the other (so they had to find my errors and, if any, also those of the other AI agent). Apparently, my “simple” argument was a bit confusing to the AI I used. This in turn confused me, until I started to remember the argument. Then I explained the argument to AI, and it got back on track. None-the-less, I’m happy for the diversion because it helped AI look into generalizations. Anything leading to more interesting mathematics is a positive thing, IMHO.

The long story short here is that I was sloppy with some definitions and some hypotheses, and I apologize for that. The usual excuse is that family and work obbligations are to blame but in fact, I love hunting down new and interesting mathematical arguments but I’m less enthusiastic about double-checking details. So, it’s really my fault. However, the overall results are more-or-less correct and even appear (if you believe AI) to generalize significantly. I have not pursued these generalizations. Nor will I, as I’ve been retired and out of that field for some time and no longer have access to the needed literature. For anyone interested, available are the original 2000 paper, the AI-aided corrected paper (2026), and AI-generated notes on generalizing these results are also available. Just email me.

Zeros of some self-reciprocal polynomials, revisited

Inspired by a blog post of Professor Alonso Castillo-Ramirez, I asked AI to look over an old survey paper I wrote in 2012. Long story short, ChatGPT-Sol (OpenAI) and Claude-Fable (Anthropic) found and corrected several errors. Embarrassing. (For the full mea culpa, see the abstract of the pdf of the corrected version.) AI even proved a conjecture I made in the paper and pointed out that another conjecture I made was a consequence of an Annals of Math paper published in 2020 . It’s embarrassing making a mistake, especially in a survey paper (apologies to the original authors!), but there is a rainbow at the end of the road.

On the teaching philosophy of Euphemia Haynes

I’m not an expert on her teaching philosophy but John Stigall is (the author of John Stigall, Euphemia Haynes’ philosophy of mathematics and mathematics education, Journal of Philosophy of Education, 2026). He pointed me to some of Euphemia’s work on the philosophy of teaching. The video below is inspired by, and based on, some of Dr. Haynes’ lectures, research and scholarly work. I could not have made it without AI (mostly Claude).

It’s titled “Euphemia Lofton Haynes – Mathematics as an open door”

Related posts:

Translating Phillip’s 1860 memoir on the mathematics of telling time

In 1860, a French mining engineer named Édouard Phillips published a 54-page memoir in the Journal de mathématiques pures et appliquées that (among other things) solved a problem watchmakers had been attacking by trial and error for nearly two centuries: what shape should the ends of a balance spring have, so that a watch keeps the same time whether its mainspring is freshly wound or nearly spent? The answer — two clean geometric conditions on the center of gravity of the spring’s terminal curve — is still the design rule behind every Breguet overcoil made today, and its modern descendants are etched into silicon hairsprings.

As far as I can tell, the memoir has never been translated into English. It now has been, and this post describes both the mathematics and the somewhat instructive process of producing the translation.

The problem

Huygens invented the spiral balance spring in 1674 (built by the horologist Thuret, with priority disputed at the time by Hooke and by the abbé Hautefeuille). Paired with a balance wheel, it forms a torsional oscillator — the timekeeping heart of every mechanical watch. The trouble is isochronism: the period should not depend on the amplitude of oscillation, but in practice it does, because the spring does not behave as an ideal torsion element. Pierre Le Roy discovered empirically in the eighteenth century that isochronism could be coaxed out of a spring by choosing its endpoints suitably. Nobody knew why, and nobody had a theory: the exact equations of a deformed elastic spiral are hopeless to integrate directly.

Phillips — an elastician who came to horology from the theory of railway carriage springs — found the way around. His memoir was examined for the Académie des Sciences by a commission of Mathieu, Lamé, and Delaunay, whose report praised it for making it possible “to substitute simple rules for the trial-and-error by which the makers of chronometers seek to obtain the isochronism of the oscillations of the balance.”

What Phillips proved

The engine of the whole memoir is one identity. Clamp both ends of the spring (as the collet and stud in fact do), rotate the balance through an angle \alpha, and let M be the flexural rigidity of the blade, L its length. Cutting the spring at an arbitrary point and balancing moments, then integrating along the blade, Phillips obtains

M\alpha = GL + L(Yx_1 - Xy_1),

where G is the restoring couple, (X, Y) is the reaction force at the balance pivot, and (x_1, y_1) is the center of gravity of the spring. If the second term vanishes, the torque law is exactly linear, G = M\alpha/L, and the swing time comes out as

T = \pi\sqrt{AL/M}

(A = moment of inertia of the balance) — independent of amplitude. Isochronism, then, reduces to killing the term L(Yx_1 - Xy_1), and Phillips identifies two sufficient conditions: keep the spring’s center of gravity on the balance axis, or make the pivot reaction vanish. He then proves a lovely equivalence: the pivot reaction vanishes if and only if the change of curvature is uniform along the blade — circles deform to circles, the coils “breathe” concentrically, exactly what one observes in a good chronometer spring.

The centerpiece is the terminal-curve problem: shape the end curve of the spring so that, under this uniform-curvature deformation, the center of the body coils stays put for every working \alpha. After a page of integration by parts and a linearization in \alpha, four conditions collapse to two statements about the center of gravity G of the terminal curve alone. If the curve has developed length \ell and joins the coils (radius \rho_0) at the point C:

  1. OG \perp OC — the center of gravity lies on the radius perpendicular to the junction radius;
  2. OG = \rho_0^2/\ell — its distance from the axis is the third proportional to the curve’s length and the coil radius.

These are the Phillips conditions. Along the way he proves that a circular arc can never serve as a terminal curve (explaining why the old practice of simply using a piece of the last coil had been abandoned as “vicious”), and he shows the conditions are independent of the blade’s cross-section, of the total spring length, and of the relative placement of the two end curves — which is precisely what leaves Le Roy’s length-adjustment method available as a final regulating trim.

The memoir then keeps giving. The terminal-curve conditions automatically place the center of gravity of the entire spring on the axis, by an elegant moment cancellation (m = m' = 2\rho_0^2\sin\tfrac{\beta}{2} for every opening angle \beta). Pushing to second order yields two further integral conditions, which Phillips converts — via the theorem of Pappus–Guldin — into statements about volumes of revolution that a draftsman can check from a drawing: a numerical-verification protocol, vintage 1860. There is a fully practical chapter on constructing compliant curves graphically, an analysis of the flat (watch) spring showing it can be isochronous only for small arcs unless terminated by a curve brought back toward the center — the mathematics of the Breguet overcoil — a proof that the work of deforming the spring depends only on its volume and the imposed strains, a temperature chapter showing the conditions are preserved under thermal dilation (and that thermal stress at the attachments vanishes if the terminal curve springs from the axis itself), and a closing analysis of Coulomb friction proving the beautiful classical result: friction shortens the outgoing half-swing and lengthens the return by exactly equal amounts, so the period between equilibrium passages is unchanged — friction decays the amplitude (linearly, a hallmark of dry friction) without perturbing the rate.

My favorite passages are the last ones, where Phillips confronts the theory with the workshop literature — Moinet, Saunier, the Tribune chronométrique — and shows the accumulated craft lore falling out as corollaries. A chronometer-maker in Dieppe, M. Jacob, found that one of Phillips’ theoretical curves was identical to a curve he had reached by trial and error a dozen years earlier and had used in instruments delivered to the navy. Theory recovering craft, then extending it with drawable rules.

The translation, and what it taught me about AI and old mathematics

The memoir is freely available on Numdam, but only in French, and only as a scan whose OCR text layer mangles the mathematics badly — 1860s typography, accents, braces spanning multiple lines. The translation was produced in collaboration with Anthropic’s Claude (the Fable 5 model), and the workflow turned out to be a case study in what such tools can and cannot do.

What the AI did well: the prose translation (Phillips’ mathematical French is formal and regular), the LaTeX typesetting, and — importantly — rederivation. Where the OCR was hopeless, the model reconstructed equations from the surrounding argument and verified the reconstructions symbolically (in SymPy); several nontrivial checks, such as the exact reduction of the two brace-grouped expressions for the moment (m) at equation (46), or the endpoint conditions on \int s^2 \cos(\theta_0'' - \theta_0)\,ds, were confirmed this way.

What it could not do, even when told the OCR was wrong: faithfully read a multiline displayed equation from the original. Every reconstruction was mathematically coherent, but coherence is not fidelity — the model substitutes derivation for transcription, and the result can differ from what Phillips actually printed (a missing equation here, a sign convention there, a coefficient absorbed into the wrong factor). In this project, essentially every displayed equation spanning more than one line required checking against the page images and manual retyping, and several equations present in the original had to be restored outright. The division of labor that finally worked: machine for derivation, symbolic verification, and typesetting; human eyes on the actual page for everything the page says. If you are contemplating a similar rescue of an old mathematical text, budget for that human pass — it is not optional.

The current version of the translation runs to about 36 pages: all fourteen sections of the memoir, all 89 numbered equations under their original numbers, the original figures, translator’s notes where conventions need flagging, and an appendix with annotated diagrams decoding Phillips’ notation (his accents mark evaluation at the endpoints, not derivatives; the letters A, G, and D each do double duty).

Links. The original: J. Math. Pures Appl. (2) 5 (1860), 313–366, on Numdam. The translation: PDF and a 12 page summary summary of Phillip’s memoir, including many details left out of this blog post.

A dice game of the Arapaho Indians as a coin-tossing game

In Stewart Culin’s Games of the North American Indians, one of the games he describes is an Arapaho women’s basket dice game. The original game uses five two-sided dice-like pieces tossed in a basket. A simple mathematical way to understand it is to model it instead as a coin-tossing game with 2 nickels and 3 dimes.

This is not meant to say that the Arapaho players literally used coins. They did not. Rather, the coin model is a convenient combinatorial translation of the game. Two of the original pieces are of one type, and three are of another type. That makes the game mathematically equivalent to flipping two coins of one denomination and three of another denomination, then scoring according to the pattern of heads and tails.

A historical game made modern

Culin describes the game as using a small yucca-fiber bowl and five “dice” made of bone or plum stones. Two of the five must match each other in shape and marking, while the other three form another matching set.

The coin model

Suppose we replace the five original pieces by:

  • 2 nickels
  • 3 dimes

Let heads mean “marked side up” and tails mean “blank side up.” Then one throw of the Arapaho basket becomes one simultaneous flip of the 2 nickels and the 3 dimes.

Define:

  • N = the number of nickels showing heads, so N can be 0, 1, or 2
  • D = the number of dimes showing heads, so D can be 0, 1, 2, or 3

So each flip produces a pair (N, D). The important point is that the score depends on the distribution of heads between the nickels and dimes, not merely on the total number of heads. That is why this is not just a five-coin game with all coins interchangeable.

Scoring rule

A convenient mathematical version of the scoring is:

  • 8 points if both nickels and all three dimes are heads: (2,3)
  • 3 points if:
    • both nickels are heads and the dimes are not all heads: (2,0), (2,1), or (2,2), or
    • both nickels are tails and all three dimes are heads: (0,3)
  • 1 point if:
    • all five are tails: (0,0), or
    • exactly one nickel is heads and all three dimes are heads: (1,3)
  • 0 points in all other cases

If a flip scores, the player continues flipping. If a flip scores 0, the turn ends and the basket passes. As Culin says, a successful throw earns another throw, a failed throw passes, and a game is commonly played to 100 points.

The full outcome table

Nickels (N)Dimes (D)ProbabilityScore
001/321
013/320
023/320
031/323
102/320
116/320
126/320
132/321
201/323
213/323
223/323
231/328

Probability distribution of the score

Assuming the coin model uses fair independent coins, the probabilities are:

  • P(score = 8) = 1/32
  • P(score = 3) = 8/32 = 1/4
  • P(score = 1) = 3/32
  • P(score = 0) = 20/32 = 5/8

So the probability that a single flip scores anything at all is:

P(score > 0) = 12/32 = 3/8.

That means a player succeeds on 37.5% of flips and fails on 62.5% of flips.

Expected score

The expected score on a single flip is:

E(score) = 8(1/32) + 3(8/32) + 1(3/32) = 35/32 ≈ 1.094.

Because a player keeps flipping after a successful result, the expected score in one uninterrupted turn is larger. If we let T be the expected total score of one turn, then:

T = E(score) / (1 – P(score > 0)) = (35/32) / (1 – 3/8) = 7/4 = 1.75.

So in this idealized coin-tossing model, the average value of a single turn is 1.75 points.

References

  1. Stewart Culin, Games of the North American Indians (1907), Bureau of American Ethnology. Internet Archive edition: https://archive.org/details/gamesofnorthamer00culirich
  2. Text version of Culin’s work, including the discussion of dice games and the Arapaho women’s basket dice game: https://archive.org/stream/in.ernet.dli.2015.31459/2015.31459.Games-Of-The-North-American-Indians_djvu.txt
  3. This blog post draft was prepared with assistance from ChatGPT by OpenAI: https://openai.com/chatgpt

Hans Berliner – a life built around chess

Lacking a suitable reference, here is a short bio of this fascinating researcher compiled by claude.

Early Life and Emigration from Germany

Hans Berliner was born in Berlin, Germany in 1929, into a family with a remarkable technological heritage. His great-uncle, Emile Berliner, was the inventor of the gramophone and held the patent on the disc recording format—a technology that would eventually prove superior to Thomas Edison’s cylindrical records and become the ancestor of all subsequent disc-based media formats, including hard drives and modern optical discs. The Berliner family had been involved in telephone technology at the turn of the century, with Emile owning the patent on the carbon receiver for the telephone and establishing a telephone company in Hanover, Germany.

Young Hans entered the German public school system just as Adolf Hitler was rising to power. The first hour of each school day was devoted to “religion” (meaning Christianity) and National Socialism—activities in which Berliner was not permitted to participate. He was also excluded from joining his friends in the Hitler Youth. “I was told that I was Jewish, and they didn’t want me,” Berliner later recalled. “That was quite a shock, and I guess that’s one of those things that sort of grows you up a little bit.”

Despite the oppressive political atmosphere, Germany in the 1930s remained a stimulating environment for a child interested in science. Berliner remembered it as “probably the best place in the world” for such interests. “The Germans were full of inventiveness and managed to produce things that were very, very good,” he recalled. He particularly remembered a metal wind-up toy car equipped with a working servomechanism that could sense when it was about to run off a ledge and automatically steer away—a sophisticated device for a child’s toy in 1935. German kindergarteners were reportedly “three years ahead” of their American counterparts in mathematics, and these formative years had a lasting positive effect on Berliner’s intellectual development.

The family’s fortunes changed dramatically in 1936 when two visitors from the United States came to stay with the Berliners. Seven-year-old Hans soon learned that the family would be leaving Germany. A nephew of Uncle Emile, Joseph Sanders, had arranged for approximately ten members of the extended family to emigrate to America. In 1937, the Berliner family arrived in the Washington, D.C. area, speaking very little English and with thick German accents.

Berliner’s father held a master’s degree in electrical engineering, while his mother had essentially no education beyond high school. Berliner would later describe his home environment as not particularly intellectual, with his parents “more just interested in surviving.” However, one of the most formative experiences of his life occurred before he was three years old, when his grandmother gave him a chalkboard with letters and numbers around the edges. He began making words and doing sums, and from that point on, learning came naturally. “I just wanted to know everything about everything,” he recalled.

Education and the Discovery of Chess

Berliner doggedly pursued his studies at Henry D. Cooke Elementary School in Washington, eventually graduating with the top grammar marks in his class. One of his fellow students was Carlos Fuentes, who would become a famous Mexican novelist and essayist. Fuentes vividly remembered Berliner as the “extremely brilliant boy” with “deep-set, bright eyes—a brilliant mathematical mind—and an air of displaced courtesy that infuriated the popular, regular, feisty, knickered, provincial, Depression-era sons-of-bitches.”

At age 11 and 12, Berliner read every book in the adult section of the library about astronomy, developing what he felt was phenomenal knowledge of the subject. He even reached the point where he recognized that certain theories about the formation of the solar system were patently wrong because they violated physical principles he understood. However, there was no outlet for such precocious knowledge—no school could handle a 12-year-old with advanced expertise, and no special programs existed for gifted children at that time.

Into this intellectual vacuum came chess. At age 13, Berliner was at a summer camp when rain forced everyone indoors. He noticed other children playing a game on a board that wasn’t checkers. He asked about the rules, learned them, and by the end of the day was already beating one of the other players. “Chess seemed a natural,” he recalled. “In a way, I sometimes thought maybe that was not the best path to go, but that was the one that presented itself.” Chess offered something that astronomy could not: a domain where a young person could immediately compete in the adult world.

Berliner progressed rapidly in chess, becoming a master by 1949 or 1950. He would later represent the United States at the 10th Chess Olympiad in Helsinki, Finland in 1952, where he met his future wife, a Finnish woman whom he married in 1954.

Academic and Professional Struggles

After high school, Berliner entered George Washington University to pursue a degree in physics with ambitions of becoming a top-notch physicist. However, he had no understanding of the academic path required—the need for a Ph.D. and years of study. He was one of the top physics students, but he grew bored with the program and began “majoring in bridge” rather than attending classes. Before long, his grades had plummeted, and the draft beckoned. He entered the U.S. Army in early 1951 and served with the German occupation forces. Throughout his tour of duty, Berliner continued to play chess, including one exhibition where he simultaneously played eight games against one of the top German teams—and won them all.

Upon his return to civilian life, Berliner was reluctant to return to college. It was Isador Turover, a fellow European immigrant and former top U.S. chess player who had become a successful lumber magnate in Washington, who set Berliner straight. Turover, whom Berliner had met through chess circles, told the younger man in no uncertain terms, “You will finish your degree.” He hired Berliner into his lumber company so he could earn money to pay his way through college, since there was no family money for education and Berliner had never secured a scholarship.

Unable to return to physics due to his low grade point average, Berliner switched to psychology, naively believing that with a psychology degree he could “hang out a shingle as a psychologist and start counseling people.” Again fate intervened. A classmate who worked at the Naval Research Laboratory told Berliner, “We need people like you where I work.” This led to a position in what was then called “human engineering” or “engineering psychology”—a predecessor to modern interface design and human factors research.

Early Career and First Encounters with Computers

Starting at the Naval Research Laboratory in 1954, Berliner worked on human engineering problems, such as ensuring that Navy pilots didn’t pull the wrong lever and eject themselves when trying to lower the landing gear. During this period, he had his first brush with computers. A colleague at the lab was helping to build NRL’s own computer—one of very few computers in existence at that time—and suggested they might write a chess program together. They talked about it and even did a few preliminary things, but the project never got off the ground. Berliner had read the foundational articles by Claude Shannon and by Newell and Simon about computer chess in Scientific American, but he “didn’t have the foggiest notion how to implement it.”

From the Naval Research Lab, Berliner moved to Martin Company in Denver, then to General Electric’s Missile and Space Vehicle Division in Valley Forge, Pennsylvania—which he described as “one of the finest places I’ve ever operated,” with more talented people than perhaps even Carnegie Mellon—and finally to IBM in Bethesda, Maryland. Throughout these moves, his specialty remained human factors work, which he did not consider particularly fulfilling. “My pay was skyrocketing, but I had an awful lot of spare time,” he later recalled.

Rise to Chess Prominence

hroughout the 1950s, Berliner’s chess ranking continued to climb. He became a Senior Master with a rating in the 2420-2440 range, placing him among the top ten players in the United States. He played regularly in the U.S. Invitational Championship, and in the year Bobby Fischer won the title for the first time, Berliner finished fifth and drew with Fischer.

His reputation became especially strong in correspondence chess—games played through the mail—where his systematic approach and analytical mind could shine without the time pressure of tournament play. From 1965 to 1968, Berliner served as World Correspondence Chess Champion, winning his first championship with a remarkable record of 12 wins and 4 draws in 16 games, a margin of victory three times better than any previous champion. He remained the top-ranked U.S. correspondence chess player until 2005, long after he stopped competing.

Murray Campbell, who would later work on IBM’s Deep Blue, observed that Berliner wasn’t a “star” player in the mold of Bobby Fischer or Garry Kasparov, but achieved chess greatness “using a very systematic approach and a lot of hard work.” Berliner “had competitive fire” and an analytical mind that enabled him to beat players “who might very well have been more talented than him.”

Carnegie Mellon and Computer Chess Research

While at IBM in the late 1960s, Berliner began thinking seriously about computer chess. He had never written a program in his life, so he had to learn programming while developing his first chess program. Called “J. Biit” (an acronym for “Just Because It Is There”), it was written in PL/1 and played in the first U.S. Computer Chess Championship in 1970, finishing around the middle of the field.

In 1967, Berliner met future Nobel laureate Herbert Simon at a technical meeting. Simon, who in 1956 had famously predicted that within ten years a computer would become world chess champion, was still interested in chess-playing computers. He offered Berliner a job at Carnegie Mellon University, but Berliner turned down the position of researcher. “If I’m going to come there, you’ve got to put me on the student track,” he insisted. At nearly 40 years old, feeling that he wanted to do “something worthwhile” with his life, Berliner was accepted into CMU’s Computer Science Department as a doctoral student in 1969.

Berliner found CMU to be a “good” but “chaotic” environment, with the department “up on wobbly feet.” The founding department head, Alan Perlis, was “an amazing, wonderful person” with “a desire for progress and truth that was very, very commendable.” Newell allowed Berliner to begin his thesis work on computer chess even before completing the rigorous qualifying examinations.

For his doctoral dissertation, titled “Chess as Problem Solving,” Berliner developed a chess program called CAPS that incorporated what he called the “causality facility.” This mechanism dragged back descriptions of tactical events through the search tree, allowing the program to reason about why certain moves failed and what characteristics a move would need to prevent similar failures. The program could figure out how to block threats without trying every possibility, simply by reasoning about what was required.

However, even as Berliner refined CAPS, he became convinced that rule-based approaches had fundamental limitations. “I had a set of rules that were limited,” he explained. “They were the most important things—maybe 80 percent—but that’s nothing. The other 20 percent includes the things the top players know how to do. That’s why they’re the top players.” Newell and Simon kept encouraging him to create more rules, but Berliner recognized that something crucial was missing: the intuitive understanding that allowed grandmasters to evaluate positions at a glance.

The B* Algorithm and Backgammon

While searching for new research directions, Berliner learned backgammon from his father-in-law and decided to write a program for this simpler game. His initial attempts encountered a familiar problem: the program would reach a certain point and then bog down, “trying to optimize things that it should have forgotten about.” At some point, when a player was clearly winning, the strategy should change—the program needed to recognize when transitions were coming.

Berliner hit upon the idea of using fuzzy logic—still a novel concept in the 1970s—to assign different rules “weights” or “application factors” based on their relative importance at each stage of the game. The resulting program, called BKG, began winning games it would have previously lost. In July 1979, BKG became the first computer program to defeat a reigning world champion in any board game when it beat backgammon champion Luigi Villa.

One of the highlights of Berliner’s research was the B* (“B-star”) algorithm, designed to emulate what he called the “jumping around” process in human thought. Rather than using traditional best-first or depth-first searches with arbitrary termination criteria, B* assigned an “optimistic” and a “pessimistic” score to each node. The algorithm continued searching a branch as long as the pessimistic value of the best node was no worse than the optimistic value of its sibling nodes. B* found paths that were sufficient for a task rather than theoretically “perfect” ones—emulating how a human chess master stops searching when finding a move that seems clearly best.

As Andy Palay, one of Berliner’s students, observed, B* represented “a much more directed search toward what appear to be the most promising paths” compared to simple best-first searches.

HiTech: A Chess-Playing Machine

In 1983, Berliner embarked on what he would later describe as one of the best periods of his professional life. His student Carl Ebeling proposed building a chess-playing machine using the then-novel technology of very-large-scale integrated (VLSI) circuits. Ebeling custom-designed a processor to generate chess moves, and the resulting machine, named HiTech, used 64 of these processors—one for each square of the chessboard—operating in parallel.

The enthusiasm for HiTech was extraordinary. “Everyone wanted to know what the latest developments were, and if they could help,” Berliner recalled. Volunteers from inside and outside CMU’s Computer Science Department took turns wire-wrapping connections in a third-floor lab in Wean Hall. With a hardware budget of only about five thousand dollars, the team scavenged parts and bought 32K memory chips at twenty or thirty dollars each.

A working prototype was completed in 1984. HiTech could consider 175,000 positions per second—compared to the one or two moves per second a top human player might examine. The machine also incorporated pattern recognizers that Ebeling designed to identify specific positional features, such as trapped bishops, pawn structures, and king safety issues. These pattern recognizers “sat like gargoyles on the edge of the thing watching the positions go by,” detecting problems and opportunities that pure calculation might miss.

“From the very beginning, I could see that it had the potential—maybe not every single time—it had the potential to play better than any device that existed,” Berliner recalled. The team worked hundred-hour weeks, with Monday morning meetings to discuss progress and problems. “Every week it got better. Every week the machine played better than it did the week before; now that’s incredible, that’s truly amazing.”

In October 1985, HiTech won Pittsburgh’s Gateway Open chess competition, earning the rank of “master.” That same year it won the ACM tournament for chess programs. The machine went on to win the Pennsylvania State Championship three consecutive years—something Berliner himself had never achieved as a human player. By 1987, HiTech was ranked 190th in the United States and was the only computer among the top 1,000 players, with a rating around 2440—Senior Master level.

One particularly memorable achievement was a four-game match against grandmaster Arnold Denker, which HiTech won 3.5 to 0.5. “It outplayed him in every game, in every single game. It completely beat him,” Berliner recalled.

Rivalry and the Road to Deep Blue

While Berliner’s team was developing HiTech, fellow CMU graduate students Feng-hsiung Hsu and Thomas Anantharaman began work on another chess-playing computer called ChipTest. Like HiTech, it relied on VLSI technology, but it was significantly faster—by 1987, ChipTest was searching 500,000 moves per second.

Daniel Sleator, a CMU professor who had founded the Internet Chess Club, noted that having two competing chess systems developed simultaneously at CMU “reflects a number of important things about the culture in the Computer Science Department. For one thing, there is a tremendous amount of respect for the work of graduate students. The faculty gives them the benefit of the doubt, and in many cases, including this one, it pays off.”

However, the relationship between the teams deteriorated over time. “There was some tension that never got resolved, and there were some hard feelings in terms of the competition between the two groups,” Campbell acknowledged. ChipTest evolved into Deep Thought, which won the World Computer Chess Championship in 1989. IBM subsequently hired Hsu, Campbell, and Anantharaman, and the machine that became Deep Blue eventually defeated world champion Garry Kasparov in 1997.

Legacy and Perspective

In retrospect, Berliner was characteristically blunt about the field he helped pioneer. Computer chess was “a research dead-end” as far as artificial intelligence was concerned, he concluded. “The whole AI thesis was wrong. AI researchers thought more knowledge would do everything.” Instead, more powerful processors and machine-learning techniques powered by statistical analysis, rather than human-devised rules, proved capable of cracking data-intensive problems in speech, image analysis, and data retrieval.

However, those who studied Berliner’s work disagreed with his self-assessment. “He covered a lot of ground, and he achieved excellence in all of those areas,” said Campbell. Jonathan Schaeffer, a professor at the University of Alberta who led the team that created the unbeatable Chinook checkers program, noted that Berliner “has a legacy of excellent papers that contain insights, algorithms and new ideas that aren’t as common today as they should be. People continue to reference his work when they realize there are other ways to do things, and then they point at Hans.”

Schaeffer observed that “most scientists aren’t willing to take the kinds of risks that Hans would take. But that’s why his papers are still around, while the papers of his contemporaries are long gone and forgotten.”

Berliner’s willingness to question conventional wisdom led to controversy, including his accusation that Russian computer scientist and chess grandmaster Mikhail Botvinnik had committed fraud by manipulating published results. Schaeffer and others reviewed Berliner’s evidence and concluded that Botvinnik had indeed massaged his results. Similarly, Berliner’s 1999 book The System: A World Champion’s Approach to Chess attracted sharp criticism from some reviewers, but the attacks left him unbowed.

His former students remembered not just his demanding standards but his generosity. “Working with Hans was a lot of fun,” recalled Palay. “There was a great deal of graciousness, both on a personal level and a professional level. He was very much concerned with making sure that he was treating me well, not just as his student, but as a person.” Ebeling noted that Berliner “led by example more than anything else. There was a constant attention to detail, and he was always thinking, looking out for the next idea that might work.”

Berliner retired from Carnegie Mellon in 1998. His advice to students: “Learn all the substantive knowledge that you can. In the final analysis, all knowledge hangs together, and the more you know, the easier it will be to make good decisions in the future. Learn something that has value—something quantitative, hopefully. Have something you can do that someone else will want to pay you for—a product. If you don’t have that, it’s going to be tough for you.”

Hans Berliner passed away on January 13, 2017, at the age of 87, leaving behind a remarkable legacy as a world chess champion, a pioneer in computer game-playing, and a scientist who was never afraid to challenge conventional wisdom in pursuit of truth.

Main References

Interview with Gardner Hendrie on 2005-03-07, Oral history of Hans Berliner, CHM Reference number X3131.2005, Computer History Museum, 2005.

J. Togyer, The Iconoclast, in The Link: The Magazine of the Carnegie Mellon University School of Computer Science, May 7, 2012.

The shell algorithm and a new book

A Peek Behind the Curtain

One feature of my forthcoming book with Caroline Melles, Exploring Graphs via Harmonic Morphisms, is its computational emphasis. Many of the examples and insights emerged not from pure contemplation, but from extensive experimentation using SageMath. This post gives a glimpse into the algorithmic machinery that made this exploration possible.

The fundamental problem I faced in generating examples was this: given two graphs Γ₁ and Γ₂, find all harmonic morphisms φ: Γ₂ → Γ₁. This approach is direct—a brute force algorithm that constructs all possible “color lists” (vertex labelings that encode potential morphisms) and tests each one for the harmonic property. Straightforward? Yes. Fast? Definitely not.

However, when the target graph Γ₁ is a path graph, one can do better. The “shell algorithm” exploits the geometry of distance in the source graph. Starting from a chosen vertex v₀, one builds outward through successive neighborhoods—vertices at distance 1, then 2, and so on—assigning colors constrained by distance from the starting point. At each stage, one checks necessary conditions before proceeding, pruning impossible branches early. The automorphism groups of both graphs then generate equivalent colorings, and after removing duplicates, one has a complete enumeration of the harmonic morphisms.

That’s what was done for various choices of small graphs, printing computational data to a file whose name used notation or terminology for the graphs \Gamma_1 and \Gamma_2. Months of computer searches resulted in a number of conjectures that were used to shape the material in the book.

The Elevator Problem

You are on the bottom floor (floor 0, lets call it) of an apartment building with no basement. There are n elevators, which we index 1,2,…,n. Assume the elevators are on floors f1, f2, … , where fk > 0 is the floor elevator k is currently on, 1 <= k <= n. Assume you only like one of the elevators, elevator e.


The way the elevator logic works is this: When you press the elevator button, one closest to you ( = one on floor number min(fk, k>0)) is told to go to 0. If there is a tie then, of those on the same lowest floor, the elevator with the smallest index is told to go to 0.
Move: If you press the button and some other elevator than elevator e arrives, you can tell it to go to any floor you wish.
Taboo: You can press the elevator button if and only if no elevator is moving down.
Goal: You want to use elevator e (for some fixed e=1, 2, …, n).

Problem: Is there a finite sequence of moves that allows you to ride in elevator e?

My plan is to post the answer sometime later, but have fun with it!