BishBosh

Problem

Chess is a black & white issue, nothing except perhaps the choice of opponent & whether they have the first move, is left to chance.

It's an interesting programming task, because in contrast to Bridge, it's a game of complete information, which makes the task of move-selection more tractable. In principle, one can merely generate all immediately available legal moves, & for each, examine one's opponent's counter-moves, then rinse, repeat …, until one discovers a route to a position of strategic advantage, perhaps check-mate. In practice, the exponential complexity of this procedure, limits such analysis to just a few plies, & how does one quantify strategic advantage.

Chess-programming is also attractive to me, since as a player I stink. So, having watched War Games, I concluded that The only winning move is not to play.

In a world where chess-programs are both free & strong, why would one bother to burden the world with another ? Well I could claim with some credibility, that it's the journey, not the destination, but I had an idea about removing that rinse, repeat … step, which had to be tried.

Analysis

It seems to me that chess can be looked at two ways; no, not the opposing sides of the board. It's either a game of near infinite possibilities, or the opposite, a constant (like Π is). By that I mean that, as each player stares at the board wondering where their position deteriorated, they have typically ≈30 legal moves from which to choose. Whichever choice they make, their opponent is presented with a position which leaves them with another set of move-options. Taking a step back, this can represented conceptually as a tree of moves spreading from the unique starting position at the apex, down to all possible draws or victories. This tree is so large that one will probably always navigate a different route than has ever been taken, by anyone, however foolish, but it doesn't alter the fact that being solely defined by the fixed rules of the game (ignoring occasional minor changes), the tree is completely defined; it's a really big constant. As players, we're all navigating down the same tree, which could given an enormous piece of paper, be drawn. Though the order in which branches sprout from any node, is arbitrary, this doesn't change the topology of the tree.

While this constant move-tree is a useful mental model, a chess-program can't simply implement one. There are estimated to be at least 10¹²⁰ different games, which would require 400-bit addresses. Consequently, a chess-program typically dynamically generates the available moves, from positions as they're encountered. It then dynamically evaluates the fitness of positions resulting from various move-permutations. The positions it evaluates include not just those which can be reached on the next move, but for several moves into the future. After taking the first move in the direction of the optimal position discovered, & observing its opponent's counter-move, it must restart its analysis, potentially revisiting nodes on the tree.

Implementation

Luckily, there is an alternative … lazy evaluation. By evaluating the tree-structure on demand, & pruning branches as they become inaccessible, the size is manageable. Whilst the structure of the tree defines the legal moves available from any position, one could hold additional information at each node, like an assessment of the fitness of that position, or a hash of that position to facilitate searches for identical positions elsewhere in the tree. One could also statically sort the branches emerging from each node, to promote earlier discovery of strategic positions.

BishBosh implements chess in Haskell, as a lazy rose tree of all possible moves … from any position … in any legal game:

• Each node of the tree contains an evaluation of the position's fitness, based on a weighted-mean over various criteria:

  • Material.
  • Mobility.
  • Piece-square Value.
  • Castling-potential.
  • Defence.
  • Doubled pawns.
  • Isolated pawns.
  • Passed pawns.

  The weighted-mean is also lazily evaluated, so if any criterion-weight is zero then the corresponding criterion is never evaluated, nor is it evaluated even if its criterion-weight is non-zero, until the fitness is demanded.
  N.B.: the fitness of a position isn't used to statically sort the branches sprouting from a node, to prevent premature evaluation of fitness.

• Each node also includes a Zobrist hash (a unique representation of the position) to facilitate detection of transpositions (identical positions reached by an alternative sequence of moves).

• Capture-moves, are statically sorted by either:

  • MVV-LVA.
  • SEE.

• Moves are statically sorted according to the frequency of their occurrence in standard-openings.

  This is an undocumented algorithm, but seems to be effective.

Tree-construction is now decoupled from subsequent tree-traversal, & whilst nodes may be revisited, they're never re-evaluated.

Search

Archived standard-openings, are searched to see if one can match:

• the current move-sequence.
• the current position (regardless of the move-sequence); i.e. a transposition.
• the colour-flipped position.
• any position reachable by the next move.

If more than one match is located in the archive, then those which resulted in victory for the matching player, are preferred. If there's still a choice, then it is made randomly.

On failure to locate a useful match amongst archived standard openings, the tree is searched using Alpha-beta (which yields the same result as an exhaustive search, but eliminates the majority of nodes as provably suboptimal), for the optimal position which can be reached in a fixed number of plies.

• Moves (the branches of the tree to be searched) are dynamically sorted using the Killer heuristic.
• Moves are dynamically re-sorted by leveraging any positive results from searches previously conducted from transpositions of the current position in sibling games. N.B.: this doesn't completely obliterate any previous sort of the same branches, because the sort-algorithm used is stable. This move-sorting is conducted on all the nodes of the tree until the end of the move-sequence previously discovered. Only rarely is the previously discovered result reusable as the optimal position reachable from the current position, because;
  • the previous search was aborted.
  • the previous search-depth was insufficient.
  • the alpha-beta solution-bounds differ.
• Whilst the requirement for lazy evaluation of the move-tree, prevents static removal of cyclic move-sequences to form a directed acyclic graph, tree-traversal can be dynamically terminated on encountering repetitions in the move-sequence of the game under investigation, since the repetitive result is, by its nature, predictable.

By predicting one's opponent's counter-move, their thinking-time is leveraged to ponder a subsequent move. The premise of this pondering is invalidated if one's opponent proves annoyingly unpredictable, but otherwise one can jump the starting-pistol for one's next turn.

Conclusion

A pure functional implementation of chess presents a considerable challenge, since a successful implementation is critically dependent on speed, & there's a significant overhead in repeatedly copying the board-representation (BishBosh uses an immutable array) as moves are applied. Whilst one might expect there to be a compensating ability to massively parallelise the search for the optimal position, the Alpha-beta algorithm is inherently serial; imperative implementations typically use concurrent pondering already. Consequently, it's not currently competitive with imperative implementations; an exhaustive search of more than five plies takes too much time & space.

The original idea was to eliminate duplicated effort in both the generation of the set of moves available from any position, & the quantification of the fitness of the resulting positions. Such duplication occurs after one's opponent has moved & one re-traces some of the branches of the move-tree that were covered on one's previous turn, just starting two plies further down the tree. In reality, such duplicated effort is small, since the tree is reduced ≈30-fold after each move, & therefore has been reduced ≈30²-fold by one's next turn, so most of the previously analysed tree is now inaccessible, & therefore can't be re-evaluated.

The clarity of the implementation resulting from decoupling tree-construction from tree-traversal, makes it an interesting platform on which to test chess-algorithms. While it plays a respectable game, it's unlikely to satisfy any desire for a strong game.