Sjaak - a general chess-like game playing program
Copyright (C) 2011 Evert Glebbeek (eglebbk@dds.nl)

Getting started
---------------
To compile Sjaak, you will need:
 * A C99 compiler, for instance gcc (standard on Linux and Mac OS X, available for Windows in the form of
   MinGW)
 * CMake, a cross-platform setup and configuration system. Version 2.4 or better.
 * GNU Make. Technically this is optional and you could pick another back-end in CMake.
For optimal performance, you will also need
 * A 64 bit operating system and compiler

Configure Sjaak using CMake, either using cmake-gui, or from the command line. From the top-level Sjaak/
directory, run

 $ mkdir Build
 $ cd Build
 $ cmake ..

Then run

 $ make

This will place all generated files in the Build/ subdirectory, leaving the source tree clean. On Windows,
substitute mingw32-make for "make".
The XBoard interface is called xsjaak.

Castling, en-passant captures and repetitions
---------------------------------------------
In chess, a position is not repeated if the en-passant capture rights are different between the two positions,
even if all places are otherwise in the same position. The same goes for castling rights.
To take this into account, it is necessary to fold the rights into the position signature. Sjaak currently
does not do this, possibly leading to incorrect draw claims.
This will not generally be a problem and it's a lot of hassle to code these things in for the general case. So
it's omitted. For the en-passant square, we'd have to know the type of enemy piece that could capture
en-passant, which in general we don't.


Q&A
---
Q: What is Sjaak?
A: Sjaak is a general framework for playing chess-like games. It is
basically a chess program that can play chess as well as a number of chess
variants.

Q: How do you pronounce that?
A: Similar to French "Jacques". I chose the name because it sounds somewhat
similar to what the common root of chess ("schaak" in Dutch), Chaturanga,
Shatranj or Xiang-qi might sounds like. Appropriate for a program that
plays general chess-like games.

Q: How does it work?
A: For each piece type, you define a number of properties: how it moves, how it captures, whether it is
"royal", how and where it promotes. Sjaak defines a number of primitive movement types: steppers, leapers,
sliders and hoppers.
 * Leapers take steps of (n,m) in any direction. A knight, for instance, is a (1,2) leaper.
   The King is a combination of a (1,1) and a (1,0) leaper. Elephants are (2,2) leapers.
 * Sliders move along a ray (horizontal, vertical, diagonal or anti-diagonal) until they reach
   an obstacle. A Rook is a H+V slider, a Bishop is a D+A slider and a Queen is a H+V+D+A slider.
 * Hoppers are like sliders, except they need to jump over a piece first. The Cannon (in Chinese chess)
   captures as H+V hopper.
 * Steppers move a specified number of squares in any direction (N,NE,E,SE,S,SW,W,NW). White pawns move as N
   steppers and capture as NE,NW steppers. Black pawns on the other hand move as S steppers and capture as
   SE,SW steppers.
Each piece has a "promotion zone", a region of the board, and a list of pieces that it can promote to. When
the piece reaches the promotion zone, all possible promotions are tried.

Q: How do you store all that?
A (technical): Using bitboards! For sliders and hoppers I use table lookups by occupancy number to generate
all possible moves, for leapers I have a table of possible destinations for each square. For steppers, moves
are generated by shifting all available steppers in each particular direction. The idea here is that we can
generate all moves for all steppers using a single shift operation, which is efficient for pawns.
So while a N,NE,E,SE,S,SW,W,NW stepper moves in the same way as a (1,0)|(1,1) leaper, the way in which the
moves are generated is very different.

Q: Is Sjaak based on other programs?
A: The move generator, evaluation function and search function were written from scratch, but the overall
structure of the program and the data structures it uses are very heavily based on those I use in my normal
chess program, Jazz. In fact, the code is so similar that I later copied parts of the code from Jazz to Sjaak
with little or no modification, and so the programs are very similar in many ways. I would say they are
siblings.
The move structure in Sjaak is inspired by a description of the move structure of ChessV on TalkChess. Smooth
scaling of the evaluation when approaching a 50-move draw as well as not using the score from the
transposition table in that case is an idea picked up from Crafty.

Q: Why doesn't Sjaak play atomic/losers/giveaway chess?
A: A number of reasons. First of all there's another unrelated program by the same name that plays thsoe
variants (and I even looked to see whether the name was used before I chose it). Having two programs with the
same name playing the same game would be a bit confusing.
Second of all, I'm really not that interested in these variants.
Third, I'd need to make some modifications to the move generator and the way moves are stored, which I'm not
inclined to do in light of the second point above.

Q: Can Sjaak play Seirawan Chess?
A: No. It can, however, play variants where the player starts with a pieces in holdings, such as Burmese Chess
or Pocket Knight Chess, and it uses "seirawan" as a catch-all name for these variants. Sjaak does not play
real Seirawan because its move representation cannot currently handle the combination of "gate + castle".
There is a woraround for that, but I have other features to add first.

Q: What is Sjef?
A: Sjef is a command-line match-playing program (the name is a pun, but comes from SJaak rEFeree) for chess
variants. It is similar in principle to XBoard, but it allows you to play a match without needing a graphical
window and so is perhaps more suitable for running tournaments on computer clusters or tuning matches in the
background. It uses Sjaak internally to act as a referee for the purpose of judging whether moves are legal or
not and whether the game has ended or not. It works well for many games, but perhaps not so well for a game
like Xiangqi, where Sjaak's interpretation of the chase-rule is too simplistic. It also means that Sjef is
limited to variants that Sjaak understands.
