JikChess

Version history

Changelog

Version 0.02

• Extended futility pruning
• Some tweaks in parameters of reductions
• Some minor bug fixes and speed improvements

Version 0.01

First version.

Downloads

• JikChess 0.02 — A zip package containing Windows and Linux binaries and README file.
• README — Information and instructions
• jikchess-0.02 — Linux executable, 64-bit, requires a hardware popcount instruction
• jikchess-0.02.exe — Windows executable, 64-bit, requires a hardware popcount instruction
• jikchess-0.02-nopopcnt — Linux executable, 64-bit, does not require a hardware popcount instruction
• jikchess-0.02-nopopcnt.exe — Windows executable, 64-bit, does not require a hardware popcount instruction
• The 32-bit version seems to be much slower than the 64-bit version; the Elo difference seems to be about 100 in blitz. If you publish any results, please state that you're using the 32-bit version, to avoid any confusion with different playing strength in different lists:
• jikchess-0.02-32 — Linux executable, 32-bit
• jikchess-0.02-32.exe — Windows executable, 32-bit

Old versions

• JikChess 0.01 — A zip package containing Windows and Linux binaries and README file.
  • README — Information and instructions
  • jikchess-0.01 — Linux executable, 64-bit, requires a hardware popcount instruction
  • jikchess-0.01.exe — Windows executable, 64-bit, requires a hardware popcount instruction
  • jikchess-0.01-nopopcnt — Linux executable, 64-bit, does not require a hardware popcount instruction
  • jikchess-0.01-nopopcnt.exe — Windows executable, 64-bit, does not require a hardware popcount instruction
• JikChess 0.01 32-bit — A zip package containing 32-bit Windows and Linux binaries and README file. (New 2014-12-12)
  • The 32-bit version seems to be much slower than the 64-bit version; the Elo difference seems to be about 100 in blitz. If you publish any results, please state that you're using the 32-bit version, to avoid any confusion with different playing strength in different lists.

Current version (0.02)

See the Downloads section.

Main features

• XBoard/WinBoard protocol version 2
  • Protocol version 1 is not supported. Interfaces using only version 1 may not work.
• Can be configured to use Gaviota tablebases (supports only cp4 compression format)
• Can be configured to use PolyGlot opening book
• Transposition table (hash table) size, pawn evaluation table (pawn hash) size, and endgame tablebase cache sizes can be adjusted
• Ponder, analyze

Known bugs

• With fast time controls, such as 1 second for 40 moves, the Windows version loses on time approximately once in 30 games. With longer time controls, such as 30 seconds for 40 moves, there is no problem. With the Linux version, this problem does not seem to occur at all.

License and acknowledgments

• Gaviota tablebase probing code by Miguel A. Ballicora is directly used as such. It is distributed under the MIT license; see the license text at the end of the readme file.
• Algorithm for reading PolyGlot opening books is based on the description by Michel van den Bergh
• Some initial ideas with board representation were initially taken from Winglet.
  • Only a few trivial ideas were directly copied as such
• Chess Programming Wiki and TalkChess.com forum have been good resources of ideas.

Development history

• 2013-01-10: First line of code
• 2013-12-16: First complete game
• 2014-11-26: First published version
• 2015-10-21: Version 0.02 released
• The last change to the program code that made it to this version was done in 2014-12-27, and no simple new ideas seemed to work, so it took a while before I decided to publish the new version.

Some graphs generated by GitStats

Note that these graphs count not only the source code of the engine itself but all test utilities and other scripts I have programmed for the development. It might be nice to compare this to a similar graph of the rating of the engine (obviously starting from the point where it actually could play a game).

Lines of code

Cumulative number of commits

Technical details

The program is written in C++11 from scratch. If you have questions about my algorithms or implementation, you can always ask.

Search

• Aspiration search at root node
• Alpha-beta with PVS search
• Null-move pruning
• Late-move reductions, extended futility pruning
• Only captures and promotions (no non-capturing checks) are generated in quiescence search, but if a move gives a check, the qsearch falls back to standard search with depth 1.
  • This does not sound like the best idea, but it seems to be better than the easy alternatives I've tried.
• Check extension
• A very small fractional extension in every PV node
  • The effect of this is very minimal but it seems to be positive.
• Move ordering
  • Transposition table
  • Captures are ordered using SEE
  • Killer moves
  • Internal search with depth/2 (internal iterative deepening) if transposition table move is not found

Evaluation

• The evaluator is tuned by optimizing how well it predicts the outcome of a game given a single position, much like the "Texel tuning method" or similar methods.
  • It's interesting to see which game sets produce the best results. I'll probably post some results one day.
  • The evaluation of a position can be written as a linear combination of numerical positional features of the position.
    • When tuning, the evaluation function is used only to extract these numbers, after which the problem becomes simply the problem of optimizing a function, which can be done with standard methods without using the engine at all.
    • Small regularization factor (or, in Bayesian terms, a prior distribution) can be added to the target function, to encourage unimportant parameters to become zero; this allows skipping the calculation of these features in the evaluation.
    • An interesting thing is that terms like A(N+BM)², where N and M are some features of the position and A and B are tunable parameters, get the form DN²+ENM+F². We get one extra parameter to be tuned, but on the other hand, the extra parameter E then shows if N and M actually act together in the evaluation (E is high) or whether it is better to consider them separate (E is zero, and the original form A(N+BM)² was not good).
    • In "tapered evaluation", the evaluation is weighted average of two evaluations which using parameters adjusted for middlegame and endgame. If x is the game phase, the term xA_midgameN + (1-x)A_endgameN can be written as A_midgame(xN) + A_endgame((1-x)N), where xN and (1-x)N can be thought of as two separate features of the position by the tuning algorithm.
  • With the data sets I've used, this tuning method seems to produce some very interesting values:
    • The piece values are interesting: knight is worth 4.31 pawns, bishop is worth 4.66 pawns, rook is worth 5.38 pawns, and queen is worth 13.64 pawns. However, depending on the position, some bonuses are added or subtracted to these piece values, so these values probably do not mean the same as they do in many other engines.
    • Another exmaple is that in middle game, a pawn on 2nd to 4th ranks becomes weaker if it becomes passed. This is probably not true. So it might be a hint that there is correlation with another feature of the position that the evaluator does not currently have. (That is, in many positions where a pawn on 2nd rank is passed, the opponent has huge compensation but the evaluator does not detect the feature of the position that gives the compensation. Therefore, the tuning determines that a passed pawn on 2nd rank is bad.)
    • The king safety values are particularly interesting. Some of the coefficients seem to mean that the king actually likes to live in danger, which probably can be seen in some games. This either means that I don't have enough attacking games in my dataset, and the parameters are unreliable, or that I've chosen the features that represent king's safety badly.
  • Pawn ending evaluation is completely separate with separate parameters. The "winning probability" interpretation of evaluation allows tuning pawn ending parameters completely independently to other parameters.
  • After tuning, the parameters are scaled such that the variable PAWN_VALUE is 100, because the protocols specify that the unit should be a "centipawn", whatever that means. However, the choice of this is a bit arbitrary: if I determine that a strong pawn is worth 1.25 times a weak pawn, I don't know whether I should say that pawn value is 100 and a strong pawn gets a 25 bonus, or that pawn value is 100 and a weak pawn gets a 20 minus.
• Pawn structure data is stored in a hash table to speed up the search a bit.

Random thoughts

I have no specific goals, like "write a top engine", "write an engine with an interesting playing style", or "write as good engine as possible using this algorithm". I'm doing this simply because I think it's fun. For example, my philosophy in adding new features could be described as "quantity over quality": while quality is good, quantity is more fun, and I think fun is better than good. Of course I do test every new feature to make sure it improves the engine and tune the parameters, but I don't spend too much time on such things if it reduces the fun. Maybe one day I'll write another engine with the aim of being as good as possible, because competing is also fun.

During the two years between starting the project and publishing the first version, I haven't come up with a good name, so I decided not to waste my time trying to. The current name is boring, but at least it seems to be unique. "Jik" is my nickname that simply comes from my initials, and it is pronounced /jik/.

I haven't published the source code because I don't think anyone would benefit from reading it. On the other hand, one of my dreams is to learn to write code that is readable by other people, so perhaps I could benefit from making the code publishable. Obviously in the very unlikely case my engine becomes a decent contestant for the top places in the world, I'll need to let at least some people read the source code to prove that the engine is not a clone.

About me

My FIDE rating of was 1939 in the October 2015 rating list. I also enjoy mathematics and programming.