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 file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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).
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
The above code references the following configuration parameters.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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.
GitHub commit (hash) or Subversion source code revision (integer)
Win At Chess position test, 3 seconds per position
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.
I work as a Software Architect at an insurance company. We're building a modern tech stack in the cloud using C#, Azure, ASP.NET Core, Angular, TypeScript, etc.
I've always been interested in chess (a game of complete information) and poker (a game of incomplete information). This is my attempt to write chess-playing software. I'll get to poker later.
You may be interested to explore my general programming blog, ErikTheCoder.