🧠 Chess Programming – Chapter I: Getting Started
This is the first entry in a six-part tutorial about teaching computers how to play chess — and, by extension, other perfect information games like Go, Checkers, and Othello.
Chess is often called the Drosophila melanogaster (fruit fly) of artificial intelligence — meaning it's a prime subject of study due to how much insight it offers into strategic thinking. Much like fruit flies have helped genetics researchers unlock complex biological mechanisms, chess has guided AI researchers toward major milestones — including the historic victory of IBM’s Deep Blue over Garry Kasparov, widely considered one of the greatest players of all time.
This series will walk you through the most successful techniques used in top chess programs, including Deep Blue. By the time we reach the final installment (originally scheduled for October 2000), I will have published a working Java chess engine along with downloadable source code. So if you're looking for examples, they’re coming — just bear with me.
♟️ Perfect Information Games
Chess falls under the category of perfect information games — meaning both players always have full knowledge of the current game state. If you look at the board, you know exactly where every piece is, and what your opponent can do. Other games in this category include Checkers, Go, Go-Moku, Backgammon, and Othello. Poker doesn’t qualify, since your opponent's hand is hidden.
Although this series focuses on chess, many of the concepts you'll learn can be applied to other perfect information games. However, specifics like how to generate moves or evaluate positions will always depend on that game’s unique rules.
🧩 What a Chess Program Needs
To play a decent game of chess, a computer must be able to:
-
Store the board in memory and track the game’s current state.
-
Generate legal moves based on chess rules, to play fairly.
-
Decide on the best move from all possible legal options.
-
Evaluate moves to choose the most intelligent one.
-
Provide a user interface (which this series won’t cover in detail).
Throughout this tutorial, we’ll explore all the components except the user interface, which is relatively generic for a 2D game. Let’s now introduce the core ideas behind each key component.
🧱 Board Representation
In the early days of computing, memory was limited. Chessboards were often represented using an 8x8 array where each square was stored as one byte — empty squares were 0, and pieces were assigned integer values (e.g., black king = 1). These compact methods were perfect for the limited systems of the 1970s and 1980s.
Later, more advanced techniques emerged — particularly with the arrival of 64-bit machines. The bitboard method was developed (possibly first in the Soviet Union) where each of the 64 bits in a word represents one square on the chessboard. For example, a bitboard could track every square occupied by black pawns, or every square a queen on e3 can reach.
Bitboards allow for incredibly fast operations because logical operations like AND, OR, and NOT can handle them in a single CPU cycle. Many calculations that appear repeatedly in a game can be simplified this way.
For more on bitboards, stay tuned for Chapter II.
🔄 Move Generation
Generating legal moves may seem simple at first, but in chess, it's quite complex. Each piece has different movement rules, and the game has special conditions for castling, en passant captures, pawn promotion, and not leaving the king in check.
Because of this complexity, move generation is one of the most demanding parts of a chess engine. However, much of the work can be optimized with pre-processing. I’ll present efficient data structures in Chapter III that drastically improve speed.
🔍 Search Techniques
Choosing the “best” move from legal options isn’t straightforward. The computer must predict the consequences of each — often looking several moves ahead. A basic search algorithm called minimax assumes both players play optimally and analyzes move trees to determine outcomes.
However, minimax can quickly become inefficient. Its complexity is O(bⁿ) — where b is the number of possible moves, and n is the number of moves (plies) analyzed. To manage this, smarter search techniques like Alpha-Beta pruning, NegaScout, Iterative Deepening, and MTD(f) are used.
These methods — along with structures like transposition tables and the "killer heuristic" — will be covered in Chapter IV and Chapter V.
One major challenge is the horizon effect, where the program can only “see” danger a few plies deep. For example, it might throw away a bishop to delay a queen capture beyond its search depth — thinking it “saved” the queen, only to lose it later. Solutions like quiescence search and singular extensions (used in Deep Blue) address these issues.
🧠 Evaluation
Ultimately, the engine needs to judge whether a position is good or bad — ahead or behind. The evaluation function is key. In chess, material balance (having more or stronger pieces) is often a primary factor. But in other games, like Othello, this can be misleading — you might actually want fewer pieces on the board until the end.
Building a solid evaluation function is tricky. Chapter VI will explore how top programs — such as Chess 4.5, Cray Blitz, and Belle — approach this task.
🔚 In Closing
We’ve just laid out the foundational elements needed for a chess engine. Next time, we’ll focus on how to represent chess boards in code, including arrays, bitboards, and other methods.
Get ready to build the core — piece by piece.
—
🖋 François Dominic Laramée, April 2000 (Paraphrased by ChatGPT)
🧠 Chess Programming – Chapter II: Data Structures
In the first article, we reviewed all the essential components of a chess-playing program. Now, it’s time to zoom in on one of the most foundational elements: how the chessboard is represented in memory.
Surprisingly, the core ideas used today haven’t changed much in over 30 years. This isn’t due to stagnation — it’s because early developers made some clever decisions that still hold up. Good board representation is the bedrock of any chess engine. Without it, none of the more complex features (like move generation or searching) could function efficiently.
In this chapter, we’ll cover both the primary board structures and three powerful supporting data structures. Two of them help accelerate search, while the third optimizes move generation.
🔡 Keep It Simple (At First)
A general tip: use the simplest data structure that does the job. Fancy techniques can improve performance, but when you’re just starting or working on a new game, basic, well-structured systems are often enough. You can always optimize later once the core engine is working.
📦 Basic Board Representations
Back in the 1970s, memory was extremely limited, so chess programmers had to be economical. The go-to method was an array of 64 bytes, with each byte representing a square. The value stored in each byte indicated the piece type (e.g., 0 for empty, 1 for black king, etc.).
There are a few well-known refinements of this technique:
-
🧱 SARGON-style padding:
The early SARGON program wrapped the board with two layers of “fake” squares, filled with invalid values. This hack made it easy to detect out-of-bounds moves. For example, a bishop could slide in a direction until it hit one of these fake squares, stopping the move. Knights — with their unique L-shape — required two padding layers to avoid memory errors. -
🔁 MYCHESS-style piece mapping:
MYCHESS flipped the logic: it tracked the square of each piece, rather than what piece was in each square. For example, one byte stored the location of the white king, another stored the location of the queen’s knight pawn, etc. But this had a major flaw: you couldn’t promote a pawn to a new queen unless the original queen had already been captured. Later versions solved this.
📝 Today, these techniques may only be useful in environments with extremely tight memory (e.g., old cell phones, embedded systems). For most games, simpler and more modern representations will work better.
📚 For more on vintage chess engines, see David Welsh’s 1984 book: “Computer Chess.”
🧠 Bitboards: The Power of 64 Bits
For 64-square games like chess or checkers, one brilliant technique stands out: bitboards. Developed by the KAISSA team in the Soviet Union during the late 1960s, bitboards map each square to a single bit in a 64-bit word.
For example:
-
One bitboard could represent all squares occupied by white pawns.
-
Another might show all squares threatened by a queen on e3.
-
Yet another could show the squares under attack by black knights.
By using logical operations like AND, OR, and NOT, bitboards can rapidly compute results in just a few clock cycles.
✅ Why Bitboards Are Awesome
Let’s say we want to know if the white queen is threatening the black king:
-
Load the bitboard showing the queen’s position.
-
Use it to index into a pre-computed database of queen attack patterns.
-
AND the result with the black king’s position bitboard.
If the result isn’t zero, the king is under attack. Fast, elegant, and done in just a few cycles — assuming the data is already in the cache.
Here’s another example: to find all possible moves for white knights, combine their attack bitboards and remove any square already occupied by white pieces (using a NOT on the white occupancy bitboard). No looping through all pieces or squares — just fast, logical math.
📖 For more, read about CHESS 4.5 in Peter Frey’s “Chess Skill in Man and Machine” (1977, 1981 editions).
💡 Note: Not all personal computers are truly 64-bit (especially older ones), so you may not always get the full performance benefit. But even in emulated environments, bitboards remain efficient and widely used.
🔁 Transposition Tables
In chess, you can reach the same board position through different move orders — a phenomenon called transposition. For example, 1. e4 then d4 leads to the same position as 1. d4 then e4.
Rather than analyzing the same position twice, chess engines store previously computed evaluations in a transposition table, which acts like a cache. If a new move leads to a known position, the program can reuse old data.
🧠 Benefits of Transposition Tables:
-
Speed: Especially during endgames, where many paths converge to the same state. Transposition tables allow reuse of work — often saving 90% or more of the search effort.
-
Depth bonus: If a position has already been analyzed to 6-ply, but the current search only needs 4-ply, the deeper analysis can be reused for more accuracy.
-
Opening integration: Many engines preload their transposition tables with content from their opening books, allowing them to continue using this knowledge even after the book “ends.”
⚠️ Drawback:
-
Memory-hungry. To be useful, the table must store thousands (preferably millions) of entries, each taking about 16 bytes. In tight memory environments, this is a challenge.
🧪 Hashing and Keys: Zobrist’s Method
How do you quickly generate a unique key for each chess position?
Enter Zobrist hashing (1970):
-
Assign a random N-bit number to each possible piece-square combo (e.g., black rook on h4).
-
Start with an empty hash value.
-
For each occupied square, XOR its number into the hash.
To update the hash after a move:
-
XOR the moving piece's old position.
-
XOR the captured piece (if any).
-
XOR the new position.
💡 Bonus: This method also allows a secondary “hash lock” key to detect collisions — two different boards producing the same hash.
📈 History Tables
History tables help guide move ordering during search. Inspired by the “killer move” heuristic, they track which moves tend to cause early cutoffs.
-
Implemented as a simple 64x64 table.
-
Each time a move proves effective, its counter is incremented.
-
Moves with higher history values are considered earlier in future searches.
It’s a cheap, yet surprisingly effective way to improve performance.
⚙️ Preprocessed Move Databases
Move generation is expensive. But we can preprocess a lot of it:
The technique proposed by Jean Goulet in his 1984 thesis (Data Structures for Chess, McGill University) suggests:
-
Precompute “rays” of movement for every piece on every square, assuming an empty board.
-
Store these rays in a small database.
-
During gameplay, check each ray until it hits a piece or edge of the board.
This turns move generation into a near-instant lookup and only takes a few dozen kilobytes — almost nothing compared to transposition tables.
🔚 Wrapping Up
Today, we explored how chess boards are stored, manipulated, and optimized for speed. Bitboards, transposition tables, hashing, and move databases all contribute to a powerful and flexible chess engine.
All of these tools will be demonstrated in the sample engine that accompanies this series.
Next time, we’ll dive deeper into Move Generation itself — one of the trickiest but most crucial parts of the engine.
—
🖋 François Dominic Laramée, June 2000 (Paraphrased by ChatGPT)
♟️ Chess Programming – Chapter III: Move Generation
Previously, we introduced a technique for speeding up move generation using precomputed data structures. Now, we dive deep into the mechanics of how computers generate chess moves — and the different strategies programmers have used over the years.
This chapter focuses on understanding the options and trade-offs between generating all possible moves at once or just a few at a time. It also revisits some early experimental approaches like forward pruning, explains why they failed, and compares modern approaches that work better in today’s engines.
⚔️ The Challenge of Move Generation
For humans, not all legal moves are equally appealing. Even beginner players learn not to hang their queen. But coding that kind of judgment into a computer is extremely difficult — especially since so much human intuition is subconscious.
Because of this, most modern engines rely on brute force: examine every legal move and look ahead as far as possible. You don’t need clever reasoning if you can analyze every outcome fast enough. So, optimizing move generation is about enabling fast, exhaustive search.
Three main strategies exist:
-
Selective Generation: Only generate “likely good” moves.
-
Incremental Generation: Generate moves one at a time as needed.
-
Complete Generation: Generate all legal moves upfront, then search them.
🚫 The Fall of Forward Pruning (Selective Generation)
Claude Shannon, in 1949, suggested two basic ways to build a chess-playing program:
-
Analyze all moves and all responses.
-
Analyze only a few “best” moves and their most probable replies.
Initially, the second option (selective search) seemed logical. After all, that’s how people play. But programs using this technique never reached high-level play. They’d miss critical tactical threats and blunder in key moments.
Why it failed: Even a “95% accurate” best-move selector will make at least one mistake in nearly every 40-move game. A 90% accurate one will go a full game without error in only about 1.5% of cases.
In the mid-1970s, the Northwestern team (Slate & Atkin) demonstrated that it was more reliable to search all legal moves, even if it cost more processing time. The results were stronger engines, and forward pruning largely vanished from chess programming.
♟️ Botvinnik’s Vision: A Grandmaster’s Plan
In the Soviet Union, Mikhail Botvinnik tried to build a program that “thought” like a grandmaster — planning deeply with only a few candidate moves. His system aimed to simulate high-level strategic ideas.
Though it offered interesting insights into chess theory, the engine never reached competitive performance. The complexity and fragility of the approach made it impractical.
📜 Complete Move Generation: The Standard Method
Once forward pruning was out, most programs adopted a simpler, universal method:
-
Generate all legal moves.
-
Sort them based on likely usefulness (e.g., captures, checks).
-
Search them one by one until a cutoff is found or all moves are evaluated.
In older programs like Sargon, this involved scanning the board one square at a time and computing moves on the fly — slow but necessary due to memory constraints.
Today, engines use precomputed move databases (as discussed in Chapter II), which dramatically improve speed. These databases make complete generation faster and more efficient, especially when combined with transposition tables. If even one move hits a cutoff due to prior search results, the engine can skip evaluating the rest.
Complete generation is also more flexible across different games (e.g., Othello, Go-Moku), making it a better choice for engines that support multiple games.
➕ Incremental Move Generation: One at a Time
Some advanced engines use a different strategy: generate a few moves at a time, hoping to find a cutoff early and avoid calculating the rest.
Reasons to use this method:
-
Memory efficiency: Programs in the 70s lacked room for full databases.
-
Chess-specific complexity: Move legality is tricky due to castling, en passant, and king safety.
-
Early refutations: Often a single capture refutes an entire line. So, generating captures first can quickly prune bad paths.
-
Quiescence Search compatibility: Captures dominate the positions explored in quiescence (covered in Part V), so isolating them early is helpful.
For instance, CHESS 4.5 used:
-
A set of bitboards that track all attacking pieces.
-
Efficient queries to check whether a piece attacks or is attacked.
-
“Rotated bitboards” to manage complex attack directions (see James Swafford’s work online for technical details).
🧠 Ordering Moves to Speed Up Search
The order in which moves are searched dramatically affects performance. Good move ordering can shrink the size of the search tree to its square root!
💡 Problem: The best ordering means searching the best move first… but if you knew that already, you wouldn’t need to search!
Heuristics to improve move ordering:
-
Captures first: Losing your queen is rarely good.
-
Pawn promotions: Major material swings.
-
Checks: Often force responses.
-
Killer moves: Past moves that caused cutoffs at the same depth.
-
History heuristic: Moves that worked well in the past (regardless of piece type).
All of these help Alphabeta pruning (see Chapter IV) work more effectively.
Important note: These methods delay “bad” moves but do not discard them. This is not forward pruning — every move is still eventually considered.
❗ When Is a Move Illegal?
Some moves are technically illegal — like moving into check. But instead of filtering them out during generation (which is expensive), most engines allow them and only validate legality during search, when needed. This lazy validation saves time when early cutoffs happen.
✅ Why I Chose Complete Generation
In my Java engine, I generate all legal moves at once. Why?
-
It makes the code cleaner and easier to follow.
-
I want to extend the engine to other games, not just chess.
-
I have enough memory for precomputed databases.
-
There are already other programs (e.g., Crafty, Galahad) using incremental generation, so that ground is covered.
Sure, it may not match Deep Blue’s performance — but the simplicity and portability are worth it for this tutorial series.
🔜 Next Chapter: Search Algorithms
Now that we can generate moves, we’ll look at how to search through them intelligently. In Chapter IV, we’ll start with basic search methods like Minimax and Alphabeta — the core of every strategy AI.
Stay tuned — things are about to get deep.
—
🖋 François Dominic Laramée, July 2000 (Paraphrased by ChatGPT)
🤖 Chess Programming – Chapter IV: Basic Search
Welcome to Part IV — the brain of the chess engine: the search algorithm. Now that the engine can generate legal moves, it must figure out which one is best.
This chapter introduces the Minimax algorithm and its faster cousin Alpha-Beta pruning, which lie at the heart of all competitive chess engines. These strategies apply to most two-player, turn-based games of perfect information.
🔍 Why Search?
Because humans are too complex — and computers aren't good at guessing.
Rather than trying to understand a position the way a human would (e.g., “control the center,” “attack the weak pawn”), a computer just calculates millions of possibilities very quickly. If a computer examines all legal moves, all responses, and all replies a few moves deep, it can spot tactics like forks, mates, or blunders — without “understanding” anything.
For instance, a knight fork (attacking two valuable pieces at once) is easy for a human to spot. But a program that explores three moves deep can “discover” it purely by evaluating the material gain it causes, even if the programmer didn’t explicitly teach it what a fork is.
So in short: search depth = tactical strength.
👴 The Minimax Algorithm
Minimax is the most basic two-player game search method. Here’s how it works:
-
Assign a numeric value to each board state.
-
Positive = good for Player 1 (Max)
-
Negative = good for Player 2 (Min)
-
-
Max wants to increase the score. Min wants to decrease it.
-
Assume both players play perfectly.
-
Simulate every move for Max, every reply for Min, and so on.
-
Choose the path where Max gets the best worst-case result.
Let’s imagine a simple tree with two moves for each player. Max chooses between move A and B. For each move, Min has two replies. Max picks the move that minimizes Min’s advantage — and maximizes his own.
That’s Minimax.
⏳ The Problem: Exploding Complexity
Minimax’s major flaw is its exponential growth. The number of board positions increases dramatically with each move (“ply”) you look ahead.
In chess:
-
Average branching factor: ~35 moves per turn
-
Depth of 8 plies: 35⁴ ≈ 1.5 million positions
-
Depth of 10: 35⁵ ≈ 50 million
-
Depth of 12: ~1.8 billion positions
This becomes unsustainable fast. So, we need something smarter.
✂️ Alpha-Beta Pruning: Minimax on Steroids
Alpha-Beta speeds things up by pruning branches that can’t possibly affect the final decision.
How it works:
-
Track the best score Max can guarantee (alpha)
-
Track the worst score Min can allow (beta)
-
If a branch results in a worse score than these limits, it gets cut off early
For example:
-
If we already know Max has a move worth +5
-
And we try another move that leads to a guaranteed -2 no matter what…
-
We can stop analyzing it. It’s already worse than the +5 we had.
In best-case scenarios, Alpha-Beta reduces the number of nodes from millions to just a few thousand — with zero loss of accuracy.
🔄 Move Ordering: The Key to Alpha-Beta’s Power
Alpha-Beta only works well if we analyze the best moves first. Otherwise, we waste time on suboptimal branches.
But there’s a paradox: if we knew which move was best, we wouldn’t need to search!
Here’s how we fake it:
-
Try moves stored in the transposition table first.
-
Prioritize captures, checks, and promotions — they often cause cutoffs.
-
Use the killer move heuristic: moves that previously caused early cutoffs.
-
Track successful moves in a history table and try them earlier.
These aren’t guaranteed, but they massively improve efficiency.
🔁 Iterative Deepening: Searching in Layers
This technique feels backwards — but it works.
Instead of searching straight to depth 6, we search:
-
First to depth 1
-
Then 2
-
Then 3...
-
Until we reach 6
It sounds wasteful — repeating previous work over and over. But due to how search trees grow, each extra ply requires far more effort than all the previous ones combined. So repeating shallower searches adds minimal cost — but gives you move ordering data from earlier layers.
In fact, Iterative Deepening with Alpha-Beta (IDAB) is so effective that it outperforms plain Alpha-Beta with even perfect static ordering.
Add in a transposition table, and you’ll often reuse results from earlier layers — making IDAB not just smarter, but faster.
🧠 What This Means for Play Style
Minimax-based programs are cautious. Here’s why:
Let’s say a program sees a bold move that might lead to checkmate — unless the opponent finds a tricky refutation 8 plies deep. A human might risk it. But a computer, assuming perfect play from the opponent, avoids it entirely.
As a result, engines often choose safe lines — even boring ones — to avoid risk. They won’t gamble on the opponent missing something.
Also, computers aren’t great at deception or long-term traps — unless the depth of search is enough to see the payoff.
🔚 Coming Up Next
In Chapter V, we go beyond basic search. Topics include:
-
Horizon effect (and how to fix it)
-
Quiescence search
-
Null-move heuristics
-
Aspiration search
-
MTD(f) — one of the most efficient search algorithms in existence
-
Deep Blue’s secret weapon: Singular Extensions
This is where engines get seriously strong.
—
🖋 François Dominic Laramée, August 2000 (Paraphrased by ChatGPT)
🔍 Chess Programming – Chapter V: Advanced Search
We’ve explored how Minimax and Alpha-Beta allow a chess engine to make decent decisions — but there’s still a long way to go. Rigid, fixed-depth search has major weaknesses. This chapter introduces advanced search enhancements used by top-tier programs to make their play stronger and faster.
These techniques help engines:
-
Avoid blunders just beyond their search limit,
-
Handle chaotic positions more intelligently,
-
And make better use of processing time.
Let’s get started.
🌪️ The Problem with Fixed Depth
Suppose your engine always searches 5 plies deep. Here are three ways that causes trouble:
-
Early Termination:
If a checkmate or stalemate is visible at ply 3, there’s no need to search further. But without awareness, the engine might waste time evaluating meaningless extensions beyond a decisive moment. -
False Positives:
Say the engine captures a pawn on move 5. At first glance, this looks great. But it doesn’t realize that the move exposes its queen, which will be captured at ply 6 — just outside its search depth. The engine incorrectly assumes the queen is safe. -
The Horizon Effect:
This is when the engine “hides” a disaster by pushing it just beyond its vision. For example, it might sacrifice a rook to delay the capture of its queen to ply 6, falsely believing it has avoided the loss. On the next turn, it “realizes” the queen is still gone — but now it's also down a rook.
These problems demand a smarter, more adaptive form of search.
🤫 Quiescence Search: Waiting for Calm
Chess positions are only safe to evaluate if they’re quiet — meaning no big material swings are likely to happen immediately. Evaluating a volatile position will almost always lead to errors.
Quiescence Search (QS) is the solution:
-
After reaching the search depth limit, the engine doesn't immediately evaluate.
-
Instead, it continues searching only “non-quiet” moves (e.g., captures, promotions, and sometimes checks).
-
Once it finds a quiet position — no more captures or tactical explosions — it finally runs the evaluator.
Example:
-
After a 5-ply search, the engine finds a knight capturing a rook.
-
Instead of evaluating right away, it checks if the capturing knight can itself be captured.
-
If yes, the position is not quiet and search continues.
This selective extension fixes the horizon effect in most cases — but QS can be expensive, eating up 50% or more of total processing time. Use it wisely.
👻 The Null-Move Heuristic
Here’s an unexpectedly powerful idea: let your side skip a move.
At first glance, that sounds insane. But in most positions, doing nothing should make things worse — or at least not better.
How it works:
-
Your engine evaluates the current position, but pretends your side passed the turn.
-
If, even after that, your position is still strong enough to cause a beta cutoff, you can skip evaluating all your legal moves.
Benefits:
-
Huge time savings: Instead of analyzing 35+ branches, you only examine 1 “null” branch.
-
Strengthens QS: If skipping a move leads to disaster, you can be sure the position is not quiet and needs deeper analysis.
Risks:
-
In rare positions (e.g., zugzwang), skipping a move might actually improve your chances.
-
But these cases are so infrequent that the trade-off is worth it.
Null-move pruning can cut search time by 20% to 75%, with just a few lines of extra code.
🧪 Aspiration Search and MTD(f)
🫧 Aspiration Search
Instead of searching with extreme bounds (–∞ to +∞), you “guess” the score range and search within a small window — say, ±100 points around the expected value.
If the result falls inside the window, great — it’s faster due to more pruning.
If not, it’s a fail-high or fail-low, and you retry with a wider window.
It’s a gamble that usually pays off.
🔄 MTD(f) – Memory-enhanced Test Driver
A researcher named Aske Plaat took this further. What if the search window is zero?
That’s right — each search guesses one specific value, and it either fails high or low. The engine then adjusts its guess and tries again, gradually zeroing in on the correct score. Like a binary search through the score space.
Combined with a transposition table, this is incredibly efficient:
-
Each guess is fast.
-
Fewer nodes are explored.
-
It works well with “coarse” evaluators (where position scores aren’t ultra-precise).
📝 MTD(f) is compact (10 lines of code), simple to implement on top of Alpha-Beta, and extremely fast — making it one of the most effective search methods available.
Original MTD(f) paper:
Aske Plaat – MTD(f)
🧠 Singular Extensions (Deep Blue’s Secret)
Deep Blue, IBM’s famous engine that defeated Garry Kasparov, used a clever trick:
If one move is way better than all the others at a certain node, extend the search one ply deeper for that move only.
This ensures that:
-
You confirm the move’s superiority.
-
You’re not being fooled by a tactic hidden one move deeper.
This strategy:
-
Boosts tactical sharpness,
-
Helps detect forced wins or traps,
-
And gives an edge in key moments.
But there’s a trade-off: extending even one ply can double the size of that subtree. It requires serious hardware. Deep Blue had it. Most engines don't.
Still, a simplified version of this concept can be implemented in most programs.
🧠 Wrapping Up
With these advanced techniques, a chess engine gains:
-
Speed (via null-move and aspiration),
-
Clarity (via quiescence),
-
Efficiency (via MTD(f)),
-
And tactical accuracy (via singular extensions).
If you’re building a competitive engine, these methods will get you there.
🔜 Coming Next: Evaluation Functions
In Chapter VI, we finally reach the “soul” of the chess engine: the evaluation function — how the engine scores a position. We’ll break down concepts like:
-
Material balance
-
Mobility
-
King safety
-
Pawn structures
-
Development
-
And more
It’s the most creative — and controversial — part of chess engine design.
—
🖋 François Dominic Laramée, September 2000 (Paraphrased by ChatGPT)
🧮 Chess Programming – Chapter VI: Evaluation Functions
Congratulations! After months of theory, we're now at the heart of the chess engine’s intelligence: the evaluation function.
While move generation and search are mechanical and follow the rules, the evaluation function is where the engine thinks. It analyzes a position and decides whether it's winning, losing, or balanced — and why.
This chapter introduces the most common factors used to evaluate a chessboard and highlights how subjective and experimental this part of programming really is.
⚖️ Material Balance: The Backbone of Evaluation
The simplest — and most important — factor is material balance, i.e., who has more and stronger pieces.
Typical piece values (in centipawns):
-
Pawn = 100
-
Knight = 300
-
Bishop = 325
-
Rook = 500
-
Queen = 900
-
King = ∞ (but its safety is scored indirectly)
The formula is:
Material = Σ (Number of pieces × Value of piece)
Many top engines rely on material difference alone and still play decent chess. According to the creators of CHESS 4.5, an advantage of 1.5 pawns outweighs most positional advantages.
👉 So yes, material is king — but there's more to the story.
Some refinements:
-
Reward trades when ahead (simplifies the position).
-
Penalize early material sacrifices unless part of a known opening gambit.
-
Apply a “contempt factor”: a small optimism bias that discourages draws when slightly behind.
Note: In games like Othello or Go-Moku, material balance is irrelevant — every game needs a custom approach.
🧭 Mobility and Board Control
In chess, one way to pressure your opponent is to limit their mobility — the number of legal moves they can make.
To measure this:
-
Count the number of legal moves for each side.
-
Compare totals.
However, pure mobility scores are misleading. Many legal moves are garbage (e.g., moving the rook back and forth). Worse, a mobility-focused engine might waste time chasing meaningless checks.
Refinements:
-
Penalize “bad bishops” blocked by same-colored pawns.
-
Penalize knights near the edge (less reach).
-
Reward rooks on open or semi-open files.
Board control is a deeper concept:
-
A square is controlled if you attack it more than your opponent.
-
Controlling the center is a known positional advantage.
But board control is expensive to calculate in real time — especially without bitboards. My engine skips it. Yours might not.
🚀 Development and Initiative
Early in the game, you want to:
-
Move minor pieces (bishops, knights) into play.
-
Castle the king for safety.
-
Delay moving the queen until later.
Good evaluation functions reward:
-
Pieces off the back rank
-
Openings that don’t block your rooks
-
King already castled
-
Avoiding early queen moves
But this factor fades fast. After 10–12 moves, almost all engines enter the middlegame where development scoring becomes irrelevant.
In games like Checkers, keeping back-rank pieces in place is good — so development heuristics might be reversed.
🧱 Pawn Structure: The Soul of Chess
Many grandmasters have said, “Pawns are the soul of chess.” Here's why.
Good pawn structure = long-term strength. Bad structure = target practice for the opponent.
Common factors:
-
Doubled/Tripled Pawns:
Two or more friendly pawns on the same file. Penalize — they block each other and can't protect neighboring files. -
Pawn Rams:
Two opposing pawns blocking each other. Creates gridlock — neutral but worth tracking. -
Isolated Pawns:
No friendly pawns on adjacent files. Vulnerable to attack. -
Passed Pawns:
No enemy pawns in front or on adjacent files. Very strong, especially in the endgame. Reward heavily. -
Too Many Pawns:
Eight pawns restrict rook activity. Sometimes it's better to have an open file.
Advanced:
-
Reward passed pawns with rook support from behind — they’re lethal.
-
Track pawn chains for defense or attack coordination.
🛡️ King Safety and Tropism
Early in the game, the king should be hidden — usually behind castled pawns.
In the endgame, though, the king becomes a fighting piece.
Scoring king safety involves:
-
Checking if the king has castled (reward it).
-
Evaluating how many enemy pieces are nearby.
-
Assessing pawn cover around the king.
Tropism = How close enemy pieces are to your king. The closer they are, the higher the threat.
This is tricky to evaluate, but even a basic scoring of proximity (distance to king square) can help.
⚖️ Assigning Weights: The Black Art of Evaluation
Now that you’ve got all these features — how do you combine them?
Answer: Trial and error.
There is no universal formula. Every engine uses a custom combination of weights and priorities, often refined through:
-
Self-play matches
-
Genetic algorithms (in fast engines)
-
Manual tuning by the programmer
Three rules of thumb:
-
Keep it simple:
A fast evaluator lets you search deeper. Don’t overload it unless necessary. -
Balance for play style:
Want a defensive engine? Emphasize king safety. Want aggression? Boost mobility and development. -
Search is stronger than smarts:
Adding one ply of search is often better than all the heuristics in the world.
If you're not aiming to win world championships, a basic material + safety evaluator with 5–6 supporting features will do wonders.
🏁 Final Words
This concludes the Chess Programming series. We’ve covered:
-
Game structure
-
Board representations
-
Move generation
-
Search algorithms
-
Optimization techniques
-
Evaluation strategy
You now have all the tools to write a complete chess engine — and if you followed along, you’ll find the author’s Java code available alongside this final chapter.
Of course, there’s more:
-
Opening books
-
Endgame tablebases
-
Parallel search
-
Neural networks
But those are for another time.
If this journey inspired or helped you, find the author at GDC or E3 — and say hello.
—
🖋 François Dominic Laramée, October 2000 (Paraphrased by ChatGPT)
#chessprogramming #chess #ajedrez #programming
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.