No comments

MadChess 3.0 Beta d143bb5 (Time Management)

  By

I improved MadChess 3.0 Beta’s time management. I added code that increases MoveTimeSoftLimit, a TimeSpan variable that controls how long the engine examines a position (in a timed game) before responding with its move. The code increases MoveTimeSoftLimit 25% each ply (depth >= 9) if the score decreases at least one third of a pawn from the prior ply. In some engines this is known as “panic time.” The engine notices the score dropping and- to anthropomorphize it- panics like a human chess player would, spending more time than usual searching for a move that prevents its position from crumbling.

In MadChess 3.0 Beta, when it’s the engine’s turn to move (in a timed game), it allots time to search for a best move. It calculates MoveTimeSoftLimit by examining the game clock and the current position. It then calculates MoveTimeHardLimit simply by multiplying MoveTimeSoftLimit by four. The soft time limit is examined each ply. If the engine already has used 70 / 128ths of the allotted time (55%) or more, it replies with the best move found so far rather than begin searching the next ply (because it anticipates not having enough time to complete the search). Once MadChess begins searching a ply, it will not interrupt the search unless it’s reached or exceeded the MoveTimeHardLimit.

In addition, I improved code that calculates move time limits when playing a game with a traditional clock (non Fischer clock). Previously, MadChess 3.0 Beta mismanaged time in non Fischer clock games and occasionally lost on time. Now its playing strength in non Fischer clock games is on par with its strength in Fischer clock games. Usually I test MadChess in tournaments that use a Fischer clock (my computer opponent rating lists all use a Fischer clock), so playing games at 20 moves / 1 min (repeating) was special testing I did for this feature- but don’t intend to continue- to eliminate an engine deficiency. Considering “taste and comfort are personal,” as my father says, I recognize other people may prefer games with a traditional clock. So I’ve ensured MadChess plays well in those time controls.

I did not test sudden death time controls. Why? Because time scrambles don’t produce quality chess by humans or computer chess engines. In my opinion, MadChess’ performance in sudden death time control is not worth testing.

This “panic time” code increased the playing strength of MadChess 3.0 Beta by 8 Elo.

 

Feature Category Date Commit1 WAC2 Elo Rating3 Improvement
Time Management Search 2020 Dec 19 d143bb5 286 2521 +8
Crash Bug Search 2020 Aug 29 2d855ec 288 2513 +0
King Safety Evaluation 2020 Aug 16 6794c89 288 2513 +63
Eval Param Tuning Evaluation 2020 Jul 23 bef88d5 283 2450 +30
Late Move Pruning Search 2020 Feb 08 6f3d17a 288 2420 +29
Piece Mobility Evaluation 2020 Feb 01 5c5d4fc 282 2391 +62
Passed Pawns Evaluation 2018 Dec 27 103 279 2329 +119
Staged Move Generation Search 2018 Dec 15 93 275 2210 +39
History Heuristics Search 2018 Dec 03 84 275 2171 +28
Eval Param Tuning Evaluation 2018 Nov 24 75 272 2143 +47
Sophisticated Search
Material and Piece Location		 Baseline 2018 Nov 08 58 269 2096 0
  1. GitHub commit (hash) or Subversion source code revision (integer)
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move
No comments

Smooth Moves

  By

MadChess 2.2 participated in a tournament Graham Banks arranged, named Smooth Moves.

                                1    2    3    4    5    6    7    8    9    0    
1   RookieMonster 1.8.1 64-bit  **** ½½01 1010 10½½ 01½1 ½100 ½0½½ 0111 1½11 11½1  21.5/36
2   KnightX 2.4 64-bit          ½½10 **** 0½11 10½0 ½010 0011 1½1½ ½½11 1110 1½½½  21.0/36  361.75
3   Betsabe II 2020             0101 1½00 **** 0111 01½1 0001 0110 10½½ 1½11 1½11  21.0/36  355.25
4   Velvet 1.0.0 64-bit         01½½ 01½1 1000 **** 1010 1100 ½½½1 ½½01 1½11 1010  19.5/36  339.75
5   Raven 1.10 64-bit           10½0 ½101 10½0 0101 **** 0110 ½½½1 01½1 10½0 ½111  19.5/36  337.50
6   MadChess 2.2 64-bit         ½011 1100 1110 0011 1001 **** ½011 1001 0100 1100  19.0/36
7   Supernova 2.2.1 64-bit      ½1½½ 0½0½ 1001 ½½½0 ½½½0 ½100 **** 0½1½ ½½01 1111  18.0/36
8   paulchen332 0.1.1 64-bit    1000 ½½00 01½½ ½½10 10½0 0110 1½0½ **** 0½1½ 0110  15.5/36
9   Ghost 3.1 64-bit            0½00 0001 0½00 0½00 01½1 1011 ½½10 1½0½ **** 1½00  13.5/36
10  Drofa 2.0.0 64-bit          00½0 0½½½ 0½00 0101 ½000 0011 0000 1001 0½11 ****  11.5/36

Games

No comments

MadChess 3.0 Beta 2d855ec (Crash Bug)

  By

I found and exterminated a bug that caused MadChess to crash in about one quarter of one percent of games. I noticed the engine crashes on line 6 of this code in the Board.IsMoveLegal(ref ulong Move) method.

First Hypothesis : Illegal Move Causing King Capture?

I suspected the crash was caused by kingSquare == Square.Illegal (meaning king not on any square) due to a missing king. Perhaps a move two ply earlier exposed its own king to check, MadChess erroneously considered the move legal, then captured the king the previous ply? If that were true, in the current ply, when MadChess tests whether a pseudo-legal move is legal (doesn’t leave its own king in check) it would crash due to an IndexOutOfRange exception inside the IsSquareAttacked(int Square) method when calling pawnAttackMask = BlackPawnAttackMasks[Square]; (or the white pawn equivalent code). The value of Square.Illegal is 64. The black pawn attack masks array holds 64 values (max index == 63) so attempting to retrieve a value at the 64th index causes an exception.

Logging

To test my hypothesis, I added code that logs the entire sequence of moves leading to a position missing a king. After a few hundred games MadChess logged this bizarre sequence.

The abbreviations in the Played Move line above describe aspects of the move stored in bits of a ulong type. The abbreviations and their bit ranges are explained in the following code comment.

In the above position, the black king moves from g7 to h8 and promotes to a pawn. What the hell? A few hundred games later, MadChess logged another bizarre sequence.

The white king on f5 transforms into a pawn when it moves to e6. What’s going on here?

Kings are transforming into pawns. What’s going on here?

Second Hypothesis : Zobrist Hash Key Collision?

Well, the logs contradict my hypothesis that a previous move was erroneously considered legal, allowing capture of a king on the following move. No, the problem here is not capture of a king. The problem is a king transforming into a pawn. Furthermore, the logs demonstrate while the problem is related to promotion (nonsensically to a pawn) it is not confined to pawns promoting or to moves to the eighth rank. In the second example a king transforms into a pawn when moving to the sixth rank.

In the first log, I noticed the illegal move that caused the engine to crash was marked as a best move (B = True). This led me to believe a Zobrist hash key collision caused Cache.GetPosition(ulong Key) to return an invalid position to the search, and the engine, due to insufficient move validity testing, blindly played the cached position’s best move (illegal in the actual position on the board), corrupting board state (removing a king from the board). This would explain the rarity of the bug (1/4 of 1% of games) because Zobrist hash key collisions (where two different board positions hash to the same ulong value) are highly unlikely. So I enhanced the validity testing done prior to playing any move not generated by the engine (from the move Cache, from a PGN file, from a position UCI command, etc).

The ValidateMove(ref ulong Move) code below serves two purposes.

  1. It asks can this piece reasonably move from here to there? Though as I say in a code comment, it’s not an exhaustive examination.
  2. It sets aspects of the move relied upon by downstream code, such as PrioritizeMoves(Position Position, ulong[] Moves, ...) and Board.PlayMove(ulong Move).

The engine that crashed already included move validity testing. If a cached position contains an invalid best move, the best move is not played. Instead, the engine generates moves. I improved the move validity code by more closely examining pawn promotions, king moves, and captures of kings- the last one obviously illegal. I ran another tournament with a version of the engine that included missing king logging and the following move validity code.

If you’re paying close attention you’ll know the enhanced move validity testing did not prevent the engine from crashing. The second log disproves the Zobrist hash collision / insufficient move validity testing hypothesis. In the second log, the illegal move that caused the engine to crash was not marked as a best move (B = False), meaning it did not come from the cache. So what’s causing the crash?

Third Hypothesis : Bitwise Overflow?

I noticed both crashes involved the engine playing a move that, nonsensically, promotes to a pawn. In both cases the Promo bit range was set to 1, indicating Promo = P, white pawn. Pieces are encoded as follows.

Hmm, that’s a strange coincidence. Recognizing the second log indicates the bug is related to move generation (not cached moves) and thinking of the programming adage, “Debugging is like being the detective in a crime movie where you are also the murderer,” I resisted the temptation to blame the GUI and contemplated how I could have killed my own chess engine?

Debugging is like being the detective in a crime movie where you are also the murderer.

Well, the Board.PlayMove(ulong Move) method simply plays the move it is given, trusting it’s a valid move. If it promotes a piece to a pawn it does so because it was “told” to do it. Knowing this, I examined ulong move encoding, focusing on bits near the Promo bit range. What’s immediately beneath (to the right, less signifcant bits) the Promo bit range? Killer Move. Is it possible code setting the Killer Move aspect overflows its bit range and spills into the Promo range?

No, not possible. Killer Move can have only three values: 2, 1, or 0, all of which fit inside 2 bits (2 Pow (50 – 49 + 1) = 4). What’s beneath Killer Move? Move History. Is it possible code setting the History aspect overflows its bit range and spills into the Killer Move and Promo bit ranges?

Yes.

No code restricts Move History to an upper limit. I didn’t bother restricting move history scores to a defined integer range because I thought 27 bits (2 Pow (48 – 22 + 1) = 134,217,728) would accommodate any history score likely to occur in the engine. Perhaps even at bullet time control this limit is exceeded? Both crashes did occur late in a game: at ply 305 (move 153) in the first log and ply 174 (move 87) in the second log. Perhaps in the course of a game a move history score became so large it required an additional three bits (three more doublings to a value >= 1,073,741,824) to accomodate it, spilling into the first bit of the Promo aspect, setting it to 1, indicating promote to white pawn?

Bug Fix

To test this hypothesis (and prevent the engine from crashing) I began to write code that explicitly tests- prior to setting the move history bits- if the move history score exceeds 134,217,728. Then I realized I don’t have to explicitly test a limit. The engine already employs a technique that ensures values fit within a defined range: a bit mask. So I applied the move history mask when setting its value (line 9).

This fixed the bug. In 4,000 games at bullet time control, MadChess never crashed. The engine searches moves at a rate of about 5,000,000 per second. If the average game at 2 min + 1 sec / move time control lasts 60 moves, that’s 180 seconds per game x 5,000,000 moves searched per second x 4,000 games = 3.6 trillion moves searched without encountering a kingless board position.

Preventing Bitwise Overflow

Why does the bit mask fix the bug? Let me illustrate the problem by aligning move bits with history score bits. If the history score has reached 1,073,741,823, its binary representation is 111111111111111111111111111111. (The problem actually occurs earlier, when history == 536,870,912 decimal == 100000000000000000000000000000 binary. But let’s use a binary value consisting of all ones to make the alignment examples below easier to read.) When the history score is shifted then “or’d” into the ulong move via Move |= ((ulong)history << _historyShift);, the upper bits of the history score overwrite bits in the Killer and Promo ranges as illustrated below.

If we first apply ("and") the history mask to the shifted history score, then "or" it into the ulong move via Move |= ((ulong)history << _historyShift) & _historyMask;, the mask prevents any upper bits of the history score from overwriting bits in the Killer and Promo ranges as illustrated below.

  • H means "History Score"
  • & means "bitwise and"
  • = means "the result"

Align the result from line 3 above to the ulong move and you'll notice in line 11 the upper bits of the history score have been truncated (effectively limiting the score to a maximum value of 1,073,741,823) and do not overwrite bits in the Killer and Promo ranges.

Hmm... Now I'm wondering how the hell history score can reach 500 million+ merely by incrementing by the square of the distance to the horizon? Does MadChess not clear history scores at the beginning of a new game? Does the CuteChess GUI not send the ucinewgame command when starting games in a tournament? Or are these high history scores to be expected in drawn positions (like KRkr) where the engine can reach depth 64 (incrementing by 4,096 each time a beta cutoff occurs)? I'll investigate those questions later.

Because a move's history value is set in the Search.PrioritizeMoves(Position Position, ulong[] Moves...) method, I'll categorize this as a Search update. Due to the rarity of the bug, the fix did not have any appreciable effect on engine strength. MadChess remains 2513 Elo at bullet time control.

Hopefully you found this blog post helpful. Happy chess programming!

See my Engine Crash Detective Story post on the TalkChess forum for a discussion of this blog post.

 

Feature Category Date Commit1 WAC2 Elo Rating3 Improvement
Crash Bug Search 2020 Aug 29 2d855ec 288 2513 +0
King Safety Evaluation 2020 Aug 16 6794c89 288 2513 +63
Eval Param Tuning Evaluation 2020 Jul 23 bef88d5 283 2450 +30
Late Move Pruning Search 2020 Feb 08 6f3d17a 288 2420 +29
Piece Mobility Evaluation 2020 Feb 01 5c5d4fc 282 2391 +62
Passed Pawns Evaluation 2018 Dec 27 103 279 2329 +119
Staged Move Generation Search 2018 Dec 15 93 275 2210 +39
History Heuristics Search 2018 Dec 03 84 275 2171 +28
Eval Param Tuning Evaluation 2018 Nov 24 75 272 2143 +47
Sophisticated Search
Material and Piece Location		 Baseline 2018 Nov 08 58 269 2096 0
  1. GitHub commit (hash) or Subversion source code revision (integer)
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move

i>Bullet chess, 2 min / game + 1 sec / move

No comments

MadChess 3.0 Beta 6794c89 (King Safety)

  By

I added evaluation of king safety to MadChess 3.0 Beta. Because determining the safety of a king’s position involves examining moves that attack squares near the king, I combined it with piece mobility evaluation, which also examines moves. When examining piece mobility, keep a weighted count of attacks on squares ringing the king (16 squares in outer ring and 8 squares in inner ring) with separate weights for attacks by minor pieces, rooks, and queens.

In the following code, white moves to squares ringing the black king contribute negatively to black’s king safety. Black moves to squares ringing the white king contribute negatively to white’s king safety. This will become evident in a later code snippet that illustrates the king safety array contains negative values.

The above code encourages MadChess to block enemy pieces from “aiming” at its king. Conversely, it encourages MadChess to direct its pieces toward the enemy king for an eventual attack.

Next, add a weighted count of semi-open files (missing guard pawn) near the king (left file, king file, and right file). Evaluate this only for the middlegame, assuming open files are common in the endgame and don’t necessarily make a king’s position unsafe.

Finally, lookup the king safety score in an array. The array is calculated at engine startup using a non-linear formula.

The showevalparams command displays the king safety values calculated by the above code.

PS C:\Users\Erik\Documents\Chess\Engines\MadChess\3.0> .\MadChess.Engine.exe
showevalparams

King Safety KingSafetyPowerPer16:                029
King Safety MgKingSafetySemiOpenFilePer8:        062
King Safety KingSafetyMinorAttackOuterRingPer8:  008
King Safety KingSafetyMinorAttackInnerRingPer8:  021
King Safety KingSafetyRookAttackOuterRingPer8:   007
King Safety KingSafetyRookAttackInnerRingPer8:   018
King Safety KingSafetyQueenAttackOuterRingPer8:  014
King Safety KingSafetyQueenAttackInnerRingPer8:  033
King Safety KingSafetyScalePer128:               043

King Safety:  +000 +000 -001 -002 -004 -006 -008 -011 -014 -018 -021 -025 -030 -035 -040 -045 -051 -057 -063 -069 -076 -083 -091 -098 -106 -114 -123 -132 -141 -150 -159 -169 -179 -189 -200 -211 -222 -233 -245 -257 -269 -281 -294 -306 -319 -333 -346 -360 -374 -388 -403 -418 -433 -448 -463 -479 -495 -511 -527 -544 -561 -578 -595 -613

In addition, I simplified use of aspiration windows when searching the root position. The engine searches with a window of 200 centipawns (100 in each direction) centered around the best score from the prior search depth. If this fails high or low, adjust the aspiration window in the direction of failure by 600 centipawns. If this fails high or low, search the root position using an infinite window.

This code increased the playing strength of MadChess 3.0 Beta by 63 Elo. MadChess has crossed the 2500 Elo threshold.

 

Feature Category Date Commit1 WAC2 Elo Rating3 Improvement
King Safety Evaluation 2020 Aug 16 6794c89 288 2513 +63
Eval Param Tuning Evaluation 2020 Jul 23 bef88d5 283 2450 +30
Late Move Pruning Search 2020 Feb 08 6f3d17a 288 2420 +29
Piece Mobility Evaluation 2020 Feb 01 5c5d4fc 282 2391 +62
Passed Pawns Evaluation 2018 Dec 27 103 279 2329 +119
Staged Move Generation Search 2018 Dec 15 93 275 2210 +39
History Heuristics Search 2018 Dec 03 84 275 2171 +28
Eval Param Tuning Evaluation 2018 Nov 24 75 272 2143 +47
Sophisticated Search
Material and Piece Location		 Baseline 2018 Nov 08 58 269 2096 0
  1. GitHub commit (hash) or Subversion source code revision (integer)
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move
No comments

MadChess 3.0 Beta bef88d5 (Tweak Search, Tune Eval)

  By

I’ll let my Pull Request notes (PR 3) explain where I began and where I finished (hint: not where I expected) with my latest code improvements to MadChess 3.0 Beta:

Originally, I intended this PR to add Static Exchange Evaluation (SEE) to MadChess’ search method to reorder or skip evaluation of captures and / or quiet moves that enable the opponent to profitably capture the most recently moved piece. After numerous attempts to write a method that evaluates piece exchanges- either statically (without actually moving pieces) or dynamically (move pieces and search), and integrate it into the search, I could not find any technique that improved the engine’s playing strength. I decided to leave in the Search.GetExchangeScore method (dynamic evaluation of piece exchanges) and associated exchangescore and analyzeexchangepositions UCI commands even though exchange score is not considered by the main search nor the quiet (quiescence) search.

I could not find any SEE technique that improved the engine’s playing strength.

In addition, this PR contains numerous tweaks to search logic and tuned evaluation parameters; and it contains numerous code performance and clarity improvements. Together, these changes account for a 30 Elo improvement in playing strength. MadChess 3.0 Beta, even with its primitive evaluation function (simple endgames, material, piece location, passed pawns, and piece mobility) now plays stronger (2450 Elo) than MadChess 2.2 (2443 Elo), at least at bullet time control.

 

Feature Category Date Commit1 WAC2 Elo Rating3 Improvement
Eval Param Tuning Evaluation 2020 Jul 23 bef88d5 283 2450 +30
Late Move Pruning Search 2020 Feb 08 6f3d17a 288 2420 +29
Piece Mobility Evaluation 2020 Feb 01 5c5d4fc 282 2391 +62
Passed Pawns Evaluation 2018 Dec 27 103 279 2329 +119
Staged Move Generation Search 2018 Dec 15 93 275 2210 +39
History Heuristics Search 2018 Dec 03 84 275 2171 +28
Eval Param Tuning Evaluation 2018 Nov 24 75 272 2143 +47
Sophisticated Search
Material and Piece Location		 Baseline 2018 Nov 08 58 269 2096 0
  1. GitHub commit (hash) or Subversion source code revision (integer)
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move