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
No comments

The Sorceress

  By

MadChess 2.2 participated in a tournament Graham Banks arranged, named The Sorceress.

                                1  2  3  4  5  6  7  8  9  0  
1   FrankWalter 2.4.0 64-bit    ** 01 ½½ ½0 10 1½ 10 ½1 11 11  11.5/18
2   KnightX 2.1b 64-bit         10 ** 1½ 1½ 11 ½0 1½ 1½ 01 ½0  11.0/18  100.25
3   CyberPagno 3.0 64-bit       ½½ 0½ ** ½1 01 11 01 01 11 01  11.0/18  94.50
4   RookieMonster 1.7.2 64-bit  ½1 0½ ½0 ** 01 01 ½1 ½½ 11 11  11.0/18  88.75
5   Lozza 1.18 64-bit           01 00 10 10 ** 1½ ½0 11 01 11  10.0/18
6   Trace 1.37a                 0½ ½1 00 10 0½ ** ½1 0½ 11 11   9.5/18
7   Raven 0.90 64-bit           01 0½ 10 ½0 ½1 ½0 ** 0½ 1½ 01   8.0/18
8   MadChess 2.2 64-bit         ½0 0½ 10 ½½ 00 1½ 1½ ** 00 10   7.0/18
9   Delphil 3.2 64-bit          00 10 00 00 10 00 0½ 11 ** ½1   6.0/18
10  Bruja 1.9.1 64-bit          00 ½1 10 00 00 00 10 01 ½0 **   5.0/18

Games

No comments

MadChess 3.0 Beta 6f3d17a (Late Move Pruning)

  By

I added late move pruning to MadChess 3.0 Beta. Quiet moves (not captures, pawn promotions, castling, or check) near the search horizon that are sorted near the bottom of the move list- in order words, “late” moves- are skipped. These moves are “late” because history heuristics have recorded few instances of them causing a beta cutoff. Most likely they are futile (they will not raise the score to alpha), so the engine doesn’t waste time searching them.

The search only examines two quiet moves immediately next to the search horizon, five quiet moves two ply from the horizon, up to 20 quiet moves five ply from the horizon. Actually, fewer quiet moves may be examined due to futility pruning conditions.

This code increased the playing strength of MadChess 3.0 Beta by 29 Elo.

 

Feature Category Date Commit1 WAC2 Elo Rating3 Improvement
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 5c5d4fc (Piece Mobility)

  By

I have not worked on my chess engine in over a year. I had other, more important, priorities. In the last year, my wife and I bought a new home closer to the city, sold our old home, moved (*), started new jobs in the summer, and ran the Chicago Marathon in the autumn. The little free time I had for hobby programming I spent on general interest projects, not on MadChess. I’m especially proud of Leaderless Replication, an essay I published on my general programming blog, ErikTheCoder.

Lately I’ve had time to do some chess programming. I added piece mobility evaluation to MadChess 3.0 Beta. This particular evaluation feature really demonstrates the benefits of bitboards over mailbox board representation. I can calculate the mobility of knights, bishops, rooks, and queens essentially for free- that is, with no negative impact on performance. I do not need to generate any moves or scan any piece arrays (along ranks, files, or diagonals). I simply lookup pseudo-legal candidate moves (not checked for move legality, i.e. does move expose own king to check?) via the PrecalculatedMoves class (for sliding pieces) and move bit masks (for knights). Then lookup piece mobility scores in two arrays per piece type (middlegame and endgame) based on the number of moves available to the piece. Each piece mobility array is calculated at engine startup using a non-linear formula. The piece mobility scores are centered so the average number of moves is assigned zero score, less than average is assigned a negative score, and more than average is assigned a positive score. I tuned piece mobility configuration parameters against a database of about 54,000 Grandmaster games using the particle swarm algorithm I discussed in a previous blog post.

The following code calculates a mobility score for each piece on the board. By scoring mobility per piece, and not simply based on the total count of moves per side, the chess engine is encouraged to develop all of its pieces and cramp the position of its opponent.

It references the following code which determines the pseudo-legal candidate moves of each piece on the board, returned as a bit mask (where a 1 indicates a “to” square).

The above code references the following configuration parameters.

I changed source control from a local Subversion repository to a public GitHub repository. So that’s why the revision in the title of this post is a hash (used by GitHub) instead of an integer (used by Subversion) seen in my earlier posts about MadChess 3.0 Beta.

This code increased the playing strength of MadChess 3.0 Beta by 62 Elo.

 

Feature Category Date Commit1 WAC2 Elo Rating3 Improvement
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 know most people consider this one event: moving to a new home. However, because the sale, purchase, and move happened on three separate days over one month; and we had to purchase our new home before selling our old one (causing some anxiety and stress), it felt like three separate events.