[kufstdwm] alpha-beta with transposition table as a library function

transposition table is the other elegant improvement to minimax (after alpha-beta).  elegant in principle, hairy to implement in practice.

consider a generic implementation of alpha-beta game tree search with transposition table, generic enough to be applicable to any user-specified game.  what should be its API?  what features should it provide?

evaluate to infinite depth (possible because of transposition table), returning game value and line (principal variation).  intended for small games.

return the transposition table so that it can be reused for subsequent moves.

evaluate to given depth.  or, user-specified predicate of whether to stop searching, e.g., quiescence search.  quiescence search wants access to the transposition table.

ambitious: because of the many ways game tree search can be customized (for many examples, albeit often poorly described, see the chessprogramming wiki), structure the algorithm as a collection components each of which can be modified and hooked together in various ways.  I have no idea what language or framework could enable this kind of software engineering, though functional programming languages seem attractive as the first thing to try.  but beware that a pure functional programming language such as Haskell easily leaks space for this kind of task, and threading state, the transposition table, though the computation may be awkward.

common customizations sacrifice accuracy (correctness or completeness) for speed.  for example, if two different evaluated positions have the same key (for example, a 64-bit Zobrist hash in chess), one can optimize by doing no transposition table collision resolution; the second position gets ignored, assumed to have already been evaluated.  the default algorithm should not do such optimizations, but allow the user to specify safe and unsafe optimizations.

allow the search to be augmented with various statistics gathered along the way that get consumed by other user-specified parts of the algorithm.  for example, the move generator could order moves based on values of similar moves already evaluated in other parts of the tree.

provide visibility into how your customizations are working, ways to evaluate whether or not they are worth it.