A REVERSI engine from high school
Photo by Paul 012 on Wikimedia Commons .
In 1992, when I was in senior high school, our computer science class received a project assignment: write a fully functional Reversi game in Pascal.
Not a collection of exercises. Not a half-finished prototype that could place a few discs on a board. A complete game, built by our team, in which a human could play against the computer.
This was my first software team project — and, I assume, the first one for everyone else in the group. We divided the program into modules and spent considerable effort planning the interfaces between them. Then each of us went away and implemented a part.
When we finally plugged everything together, something unexpected happened: it worked.
The program compiled after about an hour. There were several bugs, but we could trace each of them to the responsible module and fix all of them within a day. We were delighted, and frankly rather surprised, that the pieces fitted together so smoothly.
We had no version control, no continuous-integration pipeline, and no automated tests whatsoever. We exchanged Pascal source files and relied on the interfaces we had agreed upon beforehand. By modern standards, this sounds rather reckless. Still, the project was a resounding success.
There is a useful lesson in this: tools matter, but clear interfaces matter as well. A CI pipeline cannot rescue a system whose modules make contradictory assumptions about each other. Conversely, even rather primitive development practices can produce a working result when the responsibilities and interfaces are small, explicit, and understood by everyone involved.
More than three decades later, I have returned to my part of that program: the computer player’s move engine.
Play the engine
I ported the original Pascal engine to ClojureScript and connected it to a modern browser-based user interface.
You can play against it here:
The application also contains a conventional minimax engine for comparison. The important part, however, is the old engine. Its ideas and limitations are essentially those of the Pascal program I wrote as a teenager.
What the move engine does
Reversi has simple rules. A move places one disc on an empty square and captures opposing discs enclosed between the new disc and another disc of the same colour. The difficulty is not finding legal moves. The difficulty is deciding which legal move will produce a good position several turns later.
The obvious approach is to construct a game tree:
- Generate all legal moves.
- Apply each move to obtain a new board position.
- Generate the opponent’s possible replies.
- Continue until the configured search depth is reached.
- Evaluate the resulting positions.
- Choose the move that leads to the best result, assuming that the opponent also chooses well.
My engine implements this as a depth-limited negamax search. Negamax is a compact variation of minimax based on the fact that Reversi is a zero-sum game: a position that is good for one player is correspondingly bad for the other. Instead of maintaining separate maximizing and minimizing functions, the algorithm changes the sign of the returned score whenever the player changes.
The idea is elegant. Unfortunately, elegance does not make the game tree smaller.
At the configured maximum depth of three, the engine considers my move, the opponent’s reply, and my following move. That is useful, but hardly profound strategic foresight. Searching more deeply would increase the number of positions substantially, especially because the original implementation has neither alpha-beta pruning nor sophisticated move ordering.
Once the search reaches its depth limit, the engine must decide whether the current board position is good or bad. It cannot simply count discs. In Reversi, having many discs early in the game is not necessarily an advantage. A player who occupies too much of the board may give the opponent many possible moves and lose control of the edges and corners.
My evaluator therefore assigns different positional values to different squares. Corners are particularly valuable because a disc in a corner can never be captured. Edge positions near an occupied corner can also become useful. The engine combines this positional score with the material score—that is, the difference in the number of discs.
This was a sensible start. It also explains why I remembered the engine as being rather strong.
The source code
I still have the source code of the complete school project. However, I do not want to publish other people’s work without their permission. I therefore provide only my own contribution:
The name BEREZUG is short for berechne Zug: “calculate move”. German
variable names, Pascal include files, and rather terse documentation
were apparently my idea of a pleasant software-development environment
in 1992.
Asking Codex for a review
I asked OpenAI Codex to review the old source code. I was curious whether it would discover anything substantial or merely congratulate me on a historically interesting school project.
It did not choose the diplomatic option:
The assessment is accurate. More importantly, it identifies two different kinds of weakness.
The first is a normal programming error. If the board is full, Wert
is used without being initialized. Pascal did not protect me from
this, and I did not protect myself with a test for terminal
positions. The result depends on whatever value happens to be
present. That is not a subtle strategic weakness. It is simply a bug.
The other weaknesses are limitations of the algorithm.
Alpha-beta pruning, for example, would allow the engine to ignore branches that cannot affect the final decision. It would still calculate the same result as the corresponding minimax search, but it could search more deeply with roughly the same amount of work—provided that useful moves are examined early enough.
A better evaluation function would also consider mobility: how many legal moves a position gives each player. Frontier discs, which border empty squares, are often vulnerable. Stable discs cannot be flipped for the remainder of the game. Parity becomes important near the end, when control over who moves into the last remaining regions can decide the result.
My engine knows almost none of this. It likes corners very much, counts discs a little, and looks ahead three levels. This is not an absurd strategy, but neither is it a particularly strong one.
Was it a good engine?
That depends on the comparison.
Compared with a serious Reversi engine, no. The search is too shallow, the evaluator is too simple, and there is even an uninitialized variable in the terminal-position calculation.
Compared with what I had written before the project, it was quite sophisticated. It generated legal moves, simulated future positions, handled passes, evaluated the board, and selected a move through adversarial search. Most importantly, it worked well enough to play an actual game.
I had remembered it as a strong engine because it was strong relative to my own abilities at the time. Codex evaluated it against the body of knowledge available today. Both perspectives are reasonable, but they answer different questions.
Still, it is slightly intimidating to receive an immediate and largely correct code review of one’s teenage work from an AI system. In 1992, access to such feedback would have required finding someone who understood Pascal, game-tree search, and Reversi strategy – and who was willing to study a high-school student’s include file. Today it takes one prompt.
On the other hand, Codex did not write this program in 1992. We did. We had to decide how to divide the work, define interfaces, turn the rules of the game into data structures and algorithms, and make independently written modules cooperate. The old code has flaws, but it represents real understanding rather than a generated answer pasted into an editor.
That distinction still matters.
Returning to old code
Porting the engine to ClojureScript was not primarily an attempt to build the strongest possible Reversi opponent. If that had been the goal, preserving a depth-three search from 1992 would have been a rather peculiar starting point.
The interesting part was making the old work executable again.
Source code can survive for decades and still become practically inaccessible. The compiler disappears, the user interface depends on an obsolete platform, and the original executable no longer runs on current systems. The algorithm may still be understandable, but it has turned into an archaeological object.
By moving the engine into a browser application, I can once again observe its decisions rather than merely read about them. I can compare it with another engine, inspect its weaknesses, and let other people play against it. The port gives the old source code a working context.
It also preserves something more personal: an early project in which a group of students discovered that careful interfaces could make separately written software fit together. We did not have the tools I would insist on today. Somehow, and with a little luck, we still built a working game.
Have fun playing against it. And if the engine makes a baffling endgame move, I may already know which uninitialized variable to blame.