The Dresden server, plus rewriting Othello

I recently found that the Dresden server is up and capable of hosting round-robin matches again. (It doesn't have a hostname at the moment, and I don't want to link directly to an IP address, so reach it via the first link on this page.)

The Dresden server is different from Tiltyard in that it has a wider variety of games, somewhat less curated than Tiltyard's selection in terms of the GDL and ease of processing the game descriptions. Unlike Tiltyard, Dresden will have gamers play pretty much every game it has.


I've found it to be a good stress test in terms of making sure that a gamer won't crash under a wide variety of conditions. One game in particular, laikLee_hex, has a tendency to crash not only my propnet generation code, but my simplest theorem-prover-based rules engines as well. Ultimately, I added a feature to blacklist the game and prevent Alloy from trying to play it at all!

I put Alloy back on the site with its new cross-process framework in a new configuration, and I'm already seeing some stability issues worth figuring out. A few of its crashes so far have involved the two remaining versions of Othello on the site. It looks like most of the issues boil down to: 1) the propnet for the game is very large; and 2) the state computations are very slow.

There are no doubt solutions I can find to keep my player more responsive and improve, but given the success of rewriting checkers, I thought I'd give Othello another go. The new version is called Reversi.

Here are the performance gains this time, in the same format as last time (average state changes per second, during 60 seconds of random playthroughs):

Rules engine	othelloSuicide	reversi
Prover	1	10
Tuple-based prover	14	71
Propnet	320	10,500

Note that, like last time, the choice of rules engine matters more than the choice of game description. Even so, we see a huge increase in performance with the new GDL, even moreso than last time: the speedup is between 5 and 30. (Propnet generation now takes 5 seconds instead of 2 minutes, and the result is about 1/35th the size; this is mainly due to the piece count computation dealing with one player at a time instead of both.)

I believe forward-chaining rules engines have a large advantage on Othello because of the heavy use of recursion. When a player plays a tile, the engine has to compute every tile that must be flipped as a consequence. In a forward-chaining rules engine, this computation can start at the tile that was played and expand outward, only covering the relevant tiles. In a backwards-chaining rules engine, we instead have to start at each tile on the board and ask, "Can I get from this tile to the tile that was played?" This is a recursive question that will often require looking at multiple tiles. (We could speed this up by checking immediately if the tile and the played tile are on the same line or diagonal, but only if the prover precomputes all constants, which the ProverStateMachine does not.)