MadChess 3.0 Beta Build 093 (Staged Move Generation)

I increased the speed at which MadChess 3.0 Beta examines nodes by implementing staged move generation. Previously, in the main search, the chess engine would generate all pseudo-legal moves, sort them by move priority, then iterate through them: testing move legality (does move expose own king to check) and playing the legal moves. This is wasteful if a beta cutoff occurs early in the move list. Usually a capture is responsible for a beta cutoff, so time is wasted generating non-captures. Now the chess engine generates moves in stages. I could have implemented more stages (QueenCaptures, RookCaptures, BishopKnightCaptures, etc) but… Continue Reading

MadChess 3.0 Beta Build 084 (History Heuristics)

I increased the playing strength of MadChess 3.0 by improving the history heuristics used by Late Move Reductions (LMR). First, I added a flag that indicates if a move was played during search (indicated below with “!”). This implies the move is legal (doesn’t expose own king to check) and search examined it (as opposed to moves appearing in the move list after a move that causes a beta cutoff). Moves are encoded as ulong primitives like so: Next, I altered the search function to flag played moves. Then I modified the search function so it not only increments move… Continue Reading

MadChess 3.0 Beta Build 075 (Eval Param Tuning)

I ported my particle swarm tuning code from MadChess 2.x to MadChess 3.0 Beta, then simplified and improved it. My code uses the Texel tuning technique described by Peter Österlund in a TalkChess forum post. I improved my particle swarm algorithm in the following manner. Simplified update of evaluation parameters via EvaluationConfig class. Run the Iterate method of each ParticleSwarm on the .NET Core threadpool instead of using dedicated threads. Locate global best particle (among all particle swarms) and update particle velocities after all Iterate methods have completed. This eliminates need to synchronize reads and writes of global state via… Continue Reading

MadChess 3.0 Beta Build 058 (Baseline)

I’ve reached an important milestone in the development of my new chess engine. MadChess 3.0 Beta can play a timed game of chess. I copied the search function from MadChess 2.0 but implemented an evaluation function from scratch. The search function is rather sophisticated. Alpha / beta negamax PVS with aspiration windows MVV / LVA move order Multi-PV with tracking of all principal variations (in search, not in hash table) Hashtable with score, bounds, and best move Delayed move generation (play best move from hashtable before generating moves) Null move pruning Killer moves Move history with aging (used to sort… Continue Reading

MadChess 3.0 Beta Build 039 (Bitboards)

For the last month or so, in the evenings and on the weekends, I’ve been writing a new version of MadChess. For this 3.0 version, I’m writing code using bitboards instead of the mailbox board representation I used in MadChess 1.x and 2.x. I considered using C++ and even went as far as purchasing Bjarne Stroustrup’s The C++ Programming Language book and reading the first four chapters. But in the end I decided to stick with C#, the programming language with which I’m most familiar, for a few reasons. Microsoft has been adding high-performance features to C# in recent editions,… Continue Reading