Table of Contents
First of all let's point to Appendix C, Bibliography for further reference.
A really strong and fast engine is needed. The general program design decides about the speed and therefore its strength (besides hardware issues).
An engine written in a high level, procedural way serves only as a crude concept. Instead a more machine-like computation will speed things up - therefore the underlying mathematical structures involved must become clear though.
At the moment the engine is implemented in Java™. But there exist parts where bytecode might become slower (even with JIT™) than native code. GCJ™ offers an alternative (see bin/gcj_auto_trial.sh) nowadays running with speed comparable to the standard VM (improvements to garbage collector, inlining etc. might provide enhancements in the future). Another way is to use JNI and implement the critical parts of the engines in the C language.
For now especially the Chess variant engine has been implemented to greater extent within XiStrat™.
There exist a simple multi-player functionality and a more specialized version for the standard case of two opponents.
In the latter a (nominally) depth-limited alpha-beta negamax algorithm in fail-soft mode with iterative deepening, transposition tables and thereby simple 'best-first' move ordering is used (in failing hard bound info wouldn't be achieved, couldn't be saved and later reused). Due to some odd / even effect we should perhaps restrict the described guessing of values to those with the same parity of depth.
Of course, if one could sort perfectly, then no search at all would be needed anymore. The evaluation function for horizon nodes is fully programmable and does for now nothing else than applying some rule-of-thumb material counting (Static State Evaluation). A contempt factor is used to avoid a cat-plays-with-mouse scenario where the engine can capture the opponent's king but doesn't because it's not urgent.
We use some hash key (built from the board position information) and additionally store the complete situation as well in order to be able to avoid any unjustified use of former results. But probably a more advanced two-level hashing should be implemented.
Some standard tricks (quiescence etc.) in this field of computer science will improve the performance in the future. So far it's still only a proof-of-concept engine, at the moment we reach (depending on board and position) search depths up to 11 plies.
While there are pathological cases where the opposite is true (see [Nau83] and [Pea84]), in general a deeper search gives higher strength.
One should be aware of search inconsistencies (for example during search values in the HashTable change whereas they were assumed to be constant when justifying some tricky algorithm) as a theoretical possibility, but in practice we just don't care (under the assumption that some problems of our current implementation can be settled in the future :-).
At the moment we have a simple random engine. If you lose too often against it, then your attitude towards the game Go is perhaps a little bit problematic; please keep in mind it is a game to enjoy :-)
See [CGT] and [Ber94] for aspects of combinatoric game theory.
Before trying to produce a complete engine, perhaps it's a good idea to concentrate on single aspects of the game when starting a computational treatment.
For example capturing races (semeai) can be treated by the following formula: An n point nakade shape filled by m opponent stones is equivalent to (n2 - 3n)/2 + 3 - m outside liberties.
Other topics could be recognizing secure territories, life and death, patterns, endgame and so on.
Besides the standard treatment compares the nodes by a single value, and thereby different aspects are valued against each other but actually aren't comparable. Partial order evaluation is a way to take this into account.
At the moment Go programs can't win against professionals whilst in Chess machines can compete with the world champion. So it is often said that Go is much harder (whilst having simpler rules) than Chess. But actually the bigger search space is achieved by a larger board, and there are some rare cases where some rulesets differ, so definately the rules are not that easily falling from heaven! And the complexity class for Go (EXPTIME-complete, see Chapter 19, Complexity Theory) is only achieved when taking the Ko rule into account, whereas in Chess you don't need this (but one could use such a rule as well of course). Perhaps the most important problem for a Go engine is the evaluation function. In Chess one can focus on the material balance and use extensions for hot situations thus achieving a decent algorithm already (regarding speed while still making sense). In Go on the other hand, estimating secure territory or the status of a group of stones are perhaps not that easy. We'll see!