For various DokChess modules, game situations on the chess board (so-called positions) must be provided and exchanged between them. Do we make the associated data structure changeable or unchangeable (immutable)?
During a game, the position changes when the opposing players move their pieces. In addition, the engine performs possible moves in its analysis, tries to counter the moves of the opponent, evaluates the outcoming positions, and then discards moves. The result is a tree that contains many thousands of different positions, depending on the search depth.
Depending on whether the position is immutable as a data structure or not, algorithms are easier or more difficult to implement, and its execution is efficient in a different way.
All modules depend on the position interface. A subsequent change would affect all of DokChess.
The starting point is domain-driven classes for square, piece and move (→ 8.2 Chess Domain Model). These classes are realized immutable as value objects (the e4 field always remains e4 after it’s construction).
For the position, two alternatives are considered:
// Pseudocode Position p = new Position(); // starting position, white side to move p.performMove(e2e4); // king's pawn advances two squares, black to move p.takeBackLastMove() // starting position again ...
Position p = new Position(); newPosition = p.performMove(e2e4); // p keeps unchanged ...
The following table summarizes the strengths and weaknesses of the two options, they are explained below.
| (1) changeable | (2) unchangeable | |
|---|---|---|
| Implementation effort | (-) higher | (+) lower |
| Efficiency (memory consumption) | (+) more economical | (-) higher demand |
| Efficiency (time behaviour) | (o) neutral | (-) worse |
| Suitability for concurrent algorithms | (-) bad | (+) good |
| Table: strengths and weaknesses of the two options |
(+) Positive Arguments
The position with its extensive state is not copied in each move. This saves memory and CPU time, and it treats the garbage collector with care. For analysis algorithms, however, it is necessary to implement functionality that takes back the effect of moves (“undo”). This Undo also takes time, hence the neutral rating (o) for the time behavior.
(-) Negative Arguments
The implementation of an Undo-functionality is complex. Not only does it have to set up captured pieces back on the board, the castling rule and en passant require special treatment as well. The Gamma+94 Command pattern suggests itself as an option. The use of that pattern within algorithms is also more complex because the latter must explicitly call methods to take back the moves.
Finally, changeable state has drawbacks related to concurrency.
(+) Positive Arguments
When you perform a move, the position is copied. It does not change the original. This eliminates the implementation of move reversal (Undo). Clients can simply store the old position as a value. This saves effort in the implementation compared to option (1).
Immutable objects offer significant advantages in concurrent algorithms.
(-) Negative Arguments
Copying the state for each new position takes time. When analyzing situations, it covers many positions, which can take a lot of time.
Beyond that, copying the state for each new position costs memory. The implementation of search algorithms with backtracking at least prevents complete game trees from ending up on the heap. Nevertheless, more memory is required, and the garbage collector has more work to do.
Both points have a negative effect on efficiency.
The decision for the unchangeable position (option 2) was made in early 2011 due to the advantages in terms of ease of implementation and the prospect of exploiting concurrency. All the disadvantages of option 2 are related to efficiency.
Due to the risk of failing to achieve the objectives with respect to the playing strength in an acceptable computing time (attractiveness, efficiency), prototypes of both versions have been implemented and compared in a mate search (Checkmate in three moves) with the minimax algorithm. With option 2, the search took 30% longer, assuming you implement copying efficiently. But this option met the constraints still well.
Further optimization options could reduce the efficiency disadvantage compared with option 1, if necessary. But they have not been implemented in the first run in order to keep the implementation simple.
These options included the use of multiple processors/cores with concurrent algorithms. In the meantime (with DokChess 2.0), this was illustrated with a parallel minimax example.