Tofiks 1.3.0

New release not even a full month after the last one.

I am happy that my engine is now being tested and ranked in CCRL Blitz. It's currently ranked quite low #544 out of 699 but that has given me even more motivation and another goal to strive for.

What's new?

New looks!

Given GoLang's Gopher mascot I commissioned some custom artwork for Tofiks the chess playing dog engine.

I think it looks absolutely adorable and compared to the old AI generated logo this guy seems like he knows what he is doing. Which is fair given how much it has grown ever since.

Score from 32bit to 16bit and Move from 16bit to 32bit

I decided to change up the types of the data my engine uses internally. I shifted 16bits from evaluation score used by the search towards the move type. 16bits is plenty to calculate scores for search with more than sufficient granularity. However, certain actions like finding the bitboard of the piece moved or determining if the move is a capture take significant calculation. This information is now also included in the Move type along with flags for isCastling, isDoublePawnPush.

While this change significantly slowed down my move generation it did speed up the make move functionality. The trade-off advantage for now seems minor but there are probably more potential speed up's available to be discovered. Also I still have 10bits unused from the 32.

Threefold repetition downgraded to twofold repetition

Threefold repetition I believe is just a human rule so that games do not accidentally and abruptly end in a draw when they shouldn't. But logically it does not make sense. If we assume we always play the best moves and the best moves only then if a position repeated itself twice there should be no logical reason it should not repeat itself thrice. Checking for 2-fold repetition is of course significantly cheaper than 3-fold. But I also discovered that the engine could not see three fold repetition draws from a distance because the transposition table would not permit the same position to be played out thrice. When we first repeat a position that is by definition a transposition to the initial position and a transposition table should be able to see that. So I noticed that I never hit the threefold repetition rule. I tested this in a completely lost position where the only way out is to check the enemy king any other move leads to instant mate. While the engine saw the mate and avoided it by delivering checks it could actually not determine that it was actually a draw but gave the evaluation still as favoring the opposition.

Tests, tests, tests... and fix some bugs

Like the threefold to twofold repetition bug was discovered by a test, some other bugs were too. I found a small inconsistency where white bishops would be valued more than black bishops. This is due to having a bug in eval - I entered a lot of positions which I evaluated without any further search. Flipped the colors and the side to move to represent the same position with swapped colors. And I found that in some circumstances the symmetry was broken and there was a bias in the colors.

Overall I had neglected tests for too long in my development. I have built a small and non-comprehensive list of tests:

• Perft 6 positions from Chess Programming Wiki Perft results
• Mate a small collection of mates from mate in 3 to mate in 6
• PV correctness - check if the reported PV actually represents valid moves
• Draw by repetition and forcing a draw in a otherwise lost game
• Evaluation symmetry
• Fuzz testing for encoding and decoding information to the transposition hash table

This is a small list and there positions in each are not exhaustive but it still has helped me with development speed due to the ability to making bold changes and simply re-running the tests and giving me a baseline confidence that it still functions mostly as it should.

Results

I played a round robin tournament with versions 1.0 through 1.3 to determine their relative strengths.

Rank Name                          Elo     +/-   Games    Wins  Losses   Draws   Points   Score    Draw   White   Black 
   1 tofiks-1.3                    182      27     600     378      89     133    444.5   74.1%   22.2%   74.8%   73.3% 
   2 tofiks-1.2                    108      25     600     315     134     151    390.5   65.1%   25.2%   69.2%   61.0% 
   3 tofiks-1.1                    -28      24     600     202     250     148    276.0   46.0%   24.7%   46.3%   45.7% 
   4 tofiks-1.0                   -304      35     600      57     479      64     89.0   14.8%   10.7%   15.3%   14.3% 

Given 3 weeks of development I am quite happy with the progress I have made.

What's Changed (auto-generated)

• feat(uci): set infinite when no time settings by @likeawizard in #51
• feat(test-suite): use infinite to find fastest mate by @likeawizard in #52
• feat(ttable): add age to ttable, add fuzz tests for ttentry by @likeawizard in #55
• 53 move score type rework by @likeawizard in #56
• 53 move score type rework by @likeawizard in #57
• feat(eval): remove bishop diag eval, should be covered by PST's by @likeawizard in #59
• feat(search): change threefold to twofold draw detection, add tests. by @likeawizard in #60

Full Changelog: v1.2.0...v1.3.0

Tofiks v1.2.0

It's not as major of a change as from 1.0 to 1.1 but still plenty of things have changes and without waiting for a year. I started development on a more robust test-suite. If I can think of any testable scenario to test I add it. It currently validates if a PV output by the engine is consists of valid moves (in response to a bug). It tests some basic mate positions. Also verifies the move generator against known perft positions.

I also focused on things like optimization. There were attempts made to make the make-unmake more efficient. Now it is simply done via copy-make principle. Where the current position is copied a move is made and if it needs to be taken back the position if overwritten with the copy. The idea was to save some irreversible changes (castling rights, captured pieces) and unmake the move based on the current board position, the move and the saved irreversible state. Initial testing showed a serious performance downgrade so that approach has been abandoned.

As far as chess playing goes:

• Late Move Reductions (LMR) - try to reduce depth at which moves are being searched later in the move order.
• Delta Pruning - in quiescence search when a side is down a lot of material there is little hope to improve so the branch is abandoned. Hopefully, pruning a lot of nodes where the difference between totally losing and completely losing makes little difference and focus can be shifted on more interesting branches.
• Minor bug fixes and code clean up has seen some small improvements and performance gain.

Results

Rank Name                          Elo     +/-   Games    Wins  Losses   Draws   Points   Score    Draw   White   Black 
   1 tofiks-1.2                    189      34     400     260      62      78    299.0   74.8%   19.5%   76.0%   73.5% 
   2 tofiks-1.1                     53      30     400     183     122      95    230.5   57.6%   23.8%   59.8%   55.5% 
   3 tofiks-1.0                   -268      40     400      48     307      45     70.5   17.6%   11.3%   19.5%   15.8%

What's Changed

• feat: test suite for invalid pv, minor fixes by @likeawizard in #41
• Test suite by @likeawizard in #42
• Mate reporting fix by @likeawizard in #43
• Remove dead code by @likeawizard in #45
• frat: delta pruning by @likeawizard in #46
• LMR - Late Move Reduction by @likeawizard in #47

Full Changelog: v1.1.0...v1.2.0

Tofiks v1.1.0

Again it's been not quite a year but a lot of time has passed since v1.1.0 in November 2022. There have been a lot of bug fixes, refinements and performance tweaks. Most notably the addition of an Aspiration Window during the Iterative Deepening Search which allows for a narrower search window and increases overall performance. Improved MVV-LVA and added History and KillerMove heuristics allow for better move ordering and that enables Late Move Pruning - when at depth the search will only look at the most promising moves ignoring moves late in the order.

There were also some failed experiments. Like LazySMP or implementing some Texel tuning for Piece-Square-Tables. While failed and shelved, lessons were learnt and I hope to revisit both of them soon. There also seems to still be some bugs with the PV line sometimes containing errors. I was not able to track it down but my guess is it has to do with some Transposition Table shenanigans. Before moving onto LazySMP that needs to be fully resolved as it relies heavily of an efficient use of Transposition Tables. Texel - I want to overhaul the evaluation part before I go into investing time into optimizing its values.

I also want to add more search heuristics like Late Move Reductions - looking at moves later in the move order at reduced depth. Some search extensions for most promising moves could also be investigated.

So that's all talk. How does it actually compare to v1.0.0 in its chess playing ability?

I ran a 200 game match between the two versions with a time control of 10s+0.5s and positions from the Arasan.pgn book with 10ply depth.

Score of tofiks-v1.1 vs tofiks-v1.0: 139 - 32 - 29 [0.767]
...      tofiks-v1.1 playing White: 66 - 14 - 20  [0.760] 100
...      tofiks-v1.1 playing Black: 73 - 18 - 9  [0.775] 100
...      White vs Black: 84 - 87 - 29  [0.492] 200
Elo difference: 207.5 +/- 51.5, LOS: 100.0 %, DrawRatio: 14.5 %
200 of 200 games finished.

So that's about +200 Elo difference and a clear improvement.

Installation

Latest stable version 64-bit binaries can be found in the release section.

Compile yourself

• Clone repository or copy files
• Make sure you have Golang 1.19+ installed
• make build will compile it your native architecture.
• In the Makefile you can change the GOAMD64VERSION variable. The values range from v1 to v4 and include various sets of extended instruction sets. A higher v-value should be expected to have better performance but might have more specific architecture and instruction set extension requirements. Most modern CPUs should be AVX2 compatible which is v3, v4 requires AVX512 support.

Feature Overview

• Magic Bitboard move generator
• MVV-LVA move ordering
• Principal Variation Search with Aspiration Window
• Null Move pruning
• Late Move pruning
• Transposition table
• History Heuristic
• Killer Move Heuristic
• Quiescence search
• Draw detection - repetition, 50-move rule and insufficient material
• Piece-Square-Table evaluation for early game and endgame.
• Pawn structure evaluation
• King safety-activity evaluation
• Piece specific evaluation
• PolyGlot opening book support
• Supported UCI commands and options:
  • uci - 'handshake' initialization by the GUI, engine responds with its id and supported options with their defaults and ranges
  • go - with the following options: wtime, btime, winc, binc, movestogo, depth, movestime, ponder and infinite
  • setoption name <option> value <value>
    • Ponder default false
    • OwnBook default false - if there is a PolyGlot book.bin in the same directory as the executable the engine will try to load it and allow the option to be toggled.
    • Hash - Transposition Table size in MB
    • Move Overhead - lag compensation variable. Works as a negative increment to reduce the alloted thinking time. Crucial for playing over the web where the go time variables might be already outdated when receiving the command and also adjust for the time the for the GUI to receive the bestmove.
• Non-UCI commands:
  • go perft <depth> - perft display number of leaf nodes at depth grouped by legal moves in the position also displays the nodes per second value for performance benchmarking.

Acknoledgments

• Lichess and the Community for nuturing my love for chess and offering a free open source platform for chess. Tofiks can be found playing on lichess under its bot account.
• The authors of Official lichess bot client. It saved a lot of time and headaches adopting a reliable solution to interact with the Lichess API instead of coding all myself.
• The authors of Blunder engine. It is a great reference to practical examples of engine principles and algorithms with its well documented code.
• Everyone on TalkChess.com Forums who have been helpful and patient explainging even very basic concepts to me.
• Chess Programming Wiki and its maintainers for creating a very comprehensive resource for everything chess programming related.

What's Changed

• feat: reduce movegen branching by @likeawizard in #25
• feat: remove metadata from move type by @likeawizard in #27
• feat: lockless TT by @likeawizard in #29
• merge with master by @likeawizard in #30
• 23 lazy smp by @likeawizard in #31
• feat: ttable search fixes by @likeawizard in #33
• feat: aspiration window by @likeawizard in #34
• feat: pv moves from line by @likeawizard in #35
• feat: refactor and safer overhead by @likeawizard in #36
• feat: late move pruning, fixed move ordering by @likeawizard in #37
• History heuristic by @likeawizard in #38
• feat: moveSelector for ordering moves by @likeawizard in #39
• release: updated README.md and version by @likeawizard in #40

Full Changelog: v1.0.0...v1.1.0

Tofiks v1.0.0

Tofiks v1.0.0 is here

It's been almost a year since I started my hobby of chess programming and this is a big milestone. By no means is my engine complete but for the first time I feel everything is in place and nothing major is broken that it can be released as a working version.

Installation

Latest stable version 64-bit binaries can be found in the release section.

Compile yourself

• Clone repository or copy files
• Make sure you have Golang 1.19+ installed
• make build will compile it your native architecture.
• In the Makefile you can change the GOAMD64VERSION variable. The values range from v1 to v4 and include various sets of extended instruction sets. A higher v-value should be expected to have better performance but might have more specific architecture and instruction set extension requirements. Most modern CPUs should be AMX2 compatible which is v3, v4 requires AMX512 support.

Feature Overview

• Magic Bitboard move generator
• MVV-LVA move ordering
• Principal Variation Search
• Null move pruning
• Transposition table
• Quiescence search
• Draw detection - repetition, 50-move rule and insufficient material
• Piece-Square-Table evaluation for early game and endgame.
• Pawn structure evaluation
• King safety-activity evaluation
• Piece specific evaluation
• PolyGlot opening book support
• Supported UCI commands and options:
  • uci - 'handshake' initialization by the GUI, engine responds with its id and supported options with their defaults and ranges
  • go - with the following options: wtime, btime, winc, binc, movestogo, depth, movestime, ponder and infinite
  • setoption name <option> value <value>
    • Ponder default false
    • OwnBook default false - if there is a PolyGlot book.bin in the same directory as the executable the engine will try to load it and allow the option to be toggled.
    • Hash - Transposition Table size in MB
    • Move Overhead - lag compensation variable. Works as a negative increment to reduce the alloted thinking time. Crucial for playing over the web where the go time variables might be already outdated when receiving the command and also adjust for the time the for the GUI to receive the bestmove.
• Non-UCI commands:
  • go perft <depth> - perft display number of leaf nodes at depth grouped by legal moves in the position also displays the nodes per second value for performance benchmarking.

Acknoledgments

• Lichess and the Community for nurturing my love for chess and offering a free open source platform for chess. Tofiks can be found playing on lichess under its bot account.
• The authors of Official lichess bot client. It saved a lot of time and headaches adopting a reliable solution to interact with the Lichess API instead of coding all myself.
• The authors of Blunder engine. It is a great reference to practical examples of engine principles and algorithms with its well documented code.
• Everyone on TalkChess.com Forums who have been helpful and patient explainging even very basic concepts to me.
• Chess Programming Wiki and its maintainers for creating a very comprehensive resource for everything chess programming related.

What's Changed (auto generated)

• refactor by @likeawizard in #1
• feat: basic uci features by @likeawizard in #2
• feat: mate display, ttable, refactor by @likeawizard in #3
• feat: implement clock and minor fixes by @likeawizard in #4
• feat: implement ponder, hardcode magics by @likeawizard in #5
• Pvs by @likeawizard in #6
• feat: null move pruning by @likeawizard in #10
• fix: mate scores by @likeawizard in #14
• feat: add queen promotions to qsearch by @likeawizard in #15
• feat: perft command, bug fixes by @likeawizard in #17
• feat: insufficient material draw by @likeawizard in #20
• fix: draw detection bugs by @likeawizard in #21
• maint: update makefile and README for release by @likeawizard in #22

Full Changelog: https://github.com/likeawizard/tofiks/commits/v1.0.0