We cannot get out.
A shadow moves in the dark.
We cannot get out.
They are coming.
Advertisements
Angular 2 directive – square
This article is part of a series – the contents page is here.
In the last article we looked at the component that displays a piece. It was pretty simple, not least because it didn’t support any kind of user input. This time we’ll deal with the display of an individual board square. We’ll make the square respond to mouse clicks so that the user can select it.
My first implementation of a board square was a component – a lot like the piece component. However I eventually ran into an annoying quirk on the Edge browser that forced me to rewrite it as a directive, for reasons that I shall explain.
Consuming the directive
Let’s begin as we did with the piece component – by looking at how we will consume the square directive. Here’s the relevant snippet from game.component.html:
<div [square]="boardSquare" *ngFor="let boardSquare of boardSquares" (selected)="onSquareSelected($event)"></div>
You might have been expecting to see a <square> element (just as we used a <square> element for the piece component). Instead, we have a plain old <div> element with a [square] attribute. If we ignore that difference for a moment we will find a couple of things that look similar to what we saw in the piece component:
- There’s an *ngFor loop to emit a
<div>for each of the board squares. - The boardSquare loop control variable’s value is being injected into the directive by the use of the square brackets around the
[square]attribute.
There’s one more thing that’s new: the (selected) attribute. Even if you haven’t used Angular you can probably guess that this is some sort of event binding. The idea is that the square directive exposes an Output property called selected that fires an event when the square is selected by the user. We’re handling that event using a method in our container (which is actually our game component) so that we can keep global track of the currently selected square. The important point here is the round brackets around (selected). That tells Angular that we’re binding to an Output property. When you see round brackets around an attribute, think the component/directive is emitting information for the container to consume.
Declaring the directive
Here’s the code for the directive from square.component.ts (okay, I should probably rename that). In other articles I’ve snipped bits out to keep the code fragments short, but this time I think it’s worthwhile to post the whole thing:
import { Directive, Input, Output, HostBinding, HostListener, OnInit, EventEmitter } from '@angular/core';
import * as Chess from '../engine/ChessElements';
@Directive({
selector: '[square]',
})
export class SquareComponent implements OnInit {
@Input("square") public square: Chess.BoardSquare;
public file: number;
public rank: number;
public isLightColour: boolean;
public algebraicName: string;
public isSelected: boolean;
@Output() selected: EventEmitter<SquareComponent> = new EventEmitter();
constructor() {
this.isSelected = false;
}
ngOnInit() {
this.file = this.square.file;
this.rank = this.square.rank;
this.isLightColour = ((this.rank - 1) * 8 + this.file + (this.rank % 2)) % 2 === 1;
this.algebraicName = this.square.algebraicNotation;
}
@HostBinding('style.-ms-grid-row') get rowBinder() {
return 9 - this.rank;
}
@HostBinding('style.-ms-grid-column') get colBinder() {
return this.file;
}
@HostBinding('id') get idBinder() {
return this.algebraicName;
}
@HostBinding('class') get classBinder() {
let classes = "boardsquare";
classes += (this.isLightColour ? " lightsquare" : " darksquare");
if (this.isSelected) {
classes += " selectedFromSquare";
}
return classes;
}
@HostListener('click') onclick() {
this.selected.emit(this);
};
public select(): void {
this.isSelected = true;
}
public deselect(): void {
this.isSelected = false;
}
}
The list in the first import line at the top looks a bit more intimidating this time. The only type that’s familiar from the piece component is Input. The first one we need to discuss is Directive, which is the @Directive decorator. The good news is that Directive is a lot like Component. In fact, it’s pretty much a subset. Notice that the only property we use in the @Directive decorator is selector. We don’t use the template properties for the very good reason that they don’t exist. We’re creating an attribute directive that changes the behaviour of an existing element, so there’s no new element and hence no template.
The directive selector
Let’s zoom in on the @Directive decorator and the @Input property declaration, because they’re important:
@Directive({
selector: '[square]',
})
export class SquareComponent implements OnInit {
@Input("square") public square: Chess.BoardSquare;
...
}
The selector for this directive is [square], which explains how the directive gets wired up to the <div> that we declared at the beginning. Recall that the syntax was:
<div [square]="boardSquare" *ngFor="let boardSquare of boardSquares" (selected)="onSquareSelected($event)"></div>
…so the [square] input attribute seems to be doing two tasks. It amplifies the <div> with our square directive and it pushes the boardSquare object into an Input property called … “square”?
Yep, that’s what’s happening. On the one hand it gives us a rather slick syntax; on the other hand it’s a little confusing. Is “[square]=” a reference to a directive or an input property? Apparently, it’s both! Notice that we declare @Input(“square”) at the top of the SquareComponent class. It makes sense when you realise that triggering the creation of the directive and binding its input properties are two separate phases in Angular; a property used in one phase can have the same name as another property used in the other phase.
That puts us in a familiar position: we’ve got an instance of SquareComponent that has been given a BoardSquare object that tells it about the board square that it is responsible for rendering.
OnInit
We want to style the square with the right colour – light or dark (since we’re the UI it seems fair enough that we should be responsible for that; the engine doesn’t care about the difference between light and dark squares). Seems like we need an isLightColour flag. Since it involves a fiddly calculation, and since its value for a given square never changes, it would be nice to compute and cache it up front. Couldn’t we do that in the constructor? No! We can’t do it until the [square] input has been initialized. That’s why we have to hook up the Angular ‘init’ event. We do this by (1) having our directive class implement the OnInit interface and (2) adding an ngOnInit method, where we can safely use this.square.
@HostBinding
Okay, so we know whether we’re a light or dark square. But how can we manipulate the <div>‘s class attribute value? Answer: with the @HostBinding decorator…
@HostBinding('class') get classBinder() {
let classes = "boardsquare";
classes += (this.isLightColour ? " lightsquare" : " darksquare");
if (this.isSelected) {
classes += " selectedFromSquare";
}
return classes;
}
There’s no other wiring required; notice that there’s no mention of the “class” attribute in the original <div> element. Our directive has got its claws into that <div> and is now manipulating it like crazy! Angular will call classBinder() regularly – notice how we can add the “selectedFromSquare” style when the square is in the selected state (this puts a green border around the square). The only thing that’s a little confusing is the method name “classBinder”. Is this some kind of magic name? No! In fact, you can use any name you like. The only thing that matters to Angular is the literal string "class" inside @HostBinding.
We do a similar trick for the 'style.-ms-grid-row' and 'style.-ms-grid-column' attributes (these are used in the Edge browser to position the div in the grid). I hope that you are starting to feel that this directive is not that different from a component. The main difference is that we use @HostBinding instead of attributes in a template element to bind the data in our class to the DOM.
Handling selection events
The square directive has one more thing that the piece component didn’t. Not because it’s a directive, but because it supports selection via mouse clicks. (BTW: this is why the piece.component.css puts the pointer-events: none style onto each piece’s image – so that when you click on a piece image the click event will fall through to the square underneath).
The UI requirement is pretty simple. When a human player wants to move, they start by clicking on the square containing the piece that they want to move, then they click on the square to which they want to move it. Assuming that this represents a legal move, the second click will commit that move. Of course, having selected the first square they might change their mind, so a second click on the first square will simply de-select that first square.
The first thing to realise is that the square directive is not in a position to drive all this logic, because it doesn’t know about the players, the other squares or the state of the game. The only things it can do are (1) keep track of whether or not it is in the selected state; (2) highlight itself in the selected state; and (3) tell the world when it is clicked.
@Output, EventEmitter and @HostListener
In Angular 2 a component or directive can ‘tell the world’ about events through an @Output property of type EventEmmitter:
@Output() selected: EventEmitter<SquareComponent> = new EventEmitter();
This declares an event to which out container can subscribe. Remember the original <div>? Notice how it hooks up a handler to the selected event. The event can send an object in its message. In our case the directive object will simply send itself as the message – hence the reference to the SquareComponent type.
That explains how the directive’s container is wired up to receive the selection event. Now we just have to fire the event whenever we get a mouse click. That’s where @HostListener comes in:
@HostListener('click') onclick() { this.selected.emit(this); };
Like @HostBinding, @HostListener connects a method in our directive class to an aspect of the DOM element that ‘hosts’ us. But whereas @HostBinding connects us to our div’s attributes, @HostListener connects us to our div’s events – in this case, the click event. In response to the click event we call the emit() method of selected, passing ourselves as the event’s message body.
So why is it a directive?
We’ve covered a lot in this article but we still haven’t answered the question: why use a directive? Wouldn’t it have been more natural to have a custom element with its own attributes instead of using @HostBinding and @HostListener to amplify a <div>? Well, yes – and my first version did just that. But here’s the problem: when you add a <square> element to the DOM you get a <square> element in the DOM. Your square component’s template (which consists of a div that’s pretty much like the one we’ve been manipulating) appears within the <square> element.
Now, for 99% of purposes this is no big deal, because browsers are supposed to ignore elements that they don’t understand (like <square>). But it turned out that the Edge browser, which relies on those -ms-grid-row and -ms-grid-column styles to position the square in the grid, can’t understand the div’s grid styling when the div is buried inside a parent element (even though it’s supposed to ignore the parent element). I had to remove that element from the DOM – and there just isn’t a way to do that when you’re using components and templates. But by using a directive I was able to manipulate the div element without the need for a parent element.
Angular 2 components – piece
This article is part of a series – the contents page is here.
So far we’ve talked a lot about chess and not much about Angular. It’s time to change tack and look at some components. We’ll start with the simplest component: ‘piece’, which represents a single chess piece on the playing board UI. This article might be of interest to developers who are just starting to explore Angular 2.
Consuming the component
It might seem like putting the cart before the horse, but let’s start by looking at how we will consume the piece component. Here’s the relevant snippet from game.component.html:
<piece *ngFor="let occupiedSquare of occupiedSquares" [squarePiece]="occupiedSquare">
</piece>
Straight away we notice that is a custom element. Once we get everything wired up, Angular will render using our piece component.
But one piece is no good; we need a element for every piece on the board. Hence the *ngFor directive that loops over the occupiedSquares collection. occupiedSquares is a property of the game component that holds an array of OccupiedSquare objects. OccupiedSquare is defined in ChessElements.ts; it’s simply a combination of a BoardSquare and a ColouredPiece (so an OccupiedSquare instance can represent a white pawn on e4, for example).
Finally, notice the [squarePiece] attribute. The square brackets tell us that squarePiece is an input property of the piece component. (When you see square brackets in an Angular 2 element, think “the data is being pushed into the component.”) In this case the value is occupiedSquare, which is the loop variable from our *ngFor.
Declaring the component
So we know that our component will be created for each piece and it will be given a rich object with all the details of the square and piece in question. Fantastic – talk about spoon feeding! Let’s start building a component to consume it, in piece.component.ts:
import { Component, Input } from '@angular/core';
import * as Chess from '../engine/ChessElements';
@Component({
selector: 'piece',
styleUrls: ['./piece.component.css'],
template: `<img src="{{imgUrl}}" class="piece" [style.left.px]="positionX" [style.top.px]="positionY" />`
})
export class PieceComponent {
@Input() public squarePiece: Chess.OccupiedSquare;
constructor() {
}
// ... declarations of imgUrl, positionX and positionY go here.
}
We start by importing the code that our component references. This is a pretty simple component so there isn’t much: Angular’s @Component and @Input decorators and Shallow Thought’s Chess types.
The PieceComponent class
If you look down below the @Component decorator you will see that this file is actually declaring a class: PieceComponent. At runtime, every component will in fact be an instance of this class. As a class, we can populate it with fields, properties, methods, etc. – and we will do that shortly. But first we need to amplify this plain old class into a full Angular component, which we do by decorating it with @Component.
The Component decorator
The @Component decorator is the heart of our component’s declaration. Everything else in this TypeScript file is providing the data that’s demanded in this declaration.
- The
selectoris “piece”. This will wire the component up to the element that we saw earlier. - The
styleUrlsvalue points to a CSS file where we can style the HTML element that our component emits. - The
templatevalue is a literal string containing the HTML to be emitted. An embedded string is appropriate here because we don’t have much HTML, but if there was a lot more then we would put it in a separate .html file and point to it withtemplateUrlinstead.
The class properties
Recall that our element injected the occupiedSquare object via an attribute called “squarePiece”. To make that work we need to declare squarePiece as a class property and decorate it with @Input. That’s all!
Notice that the template refers to imgUrl, positionX and positionY. We will declare these as properties of our class:
private get imgUrl(): string {
const colour = (this.squarePiece.piece.player === Chess.Player.White) ? "l" : "d";
let pieceCode: string;
switch (this.squarePiece.piece.piece) {
case Chess.PieceType.Pawn:
pieceCode = "p";
break;
case Chess.PieceType.Knight:
pieceCode = "n";
break;
case Chess.PieceType.Bishop:
pieceCode = "b";
break;
case Chess.PieceType.Rook:
pieceCode = "r";
break;
case Chess.PieceType.Queen:
pieceCode = "q";
break;
case Chess.PieceType.King:
pieceCode = "k";
break;
}
return `app/ui/img/${pieceCode}${colour}.png`;
}
private static squareSize = 60;
private get positionX(): number {
return (this.squarePiece.square.file - 1) * PieceComponent.squareSize;
}
private get positionY(): number {
return (8 - this.squarePiece.square.rank) * PieceComponent.squareSize;
}
I’ve always loved read-only (calculated) properties. They can do most of the heavy lifting in the system while being easy to reason about (since they have no side-effects).
Chess engine code – the evaluation function
This article is part of a series – the contents page is here.
Throughout this series we’ve referred to the evaluation function and in the last article we saw how the minimax algorithm calls it. Now, at last, we can reveal it.
You might be surprised by how simple it is. Or maybe not. It probably depends on how good you are at chess, and whether you’re a glass-half-empty or glass-half-full person. Personally, I’m quite intrigued by how such a naïve function can sometimes pull off moves that aren’t half bad. But yes, I have to concede that sometimes it does some pretty dumb things (although it can be very hard to tell how much of that is due to the over-simplification of the evaluation versus the horizon effect).
The dirty secret
So here it is: the dirty secret at the heart of this engine. The evaluation function’s score comes from just two factors:
- A simple count of material, counting pawns as 100, queens as 900, etc.
- A weighted sum of attacked squares. Each player gets a few points for each square that they attack.
Attacked square weightings
In evaluating the attack scores, both squares and pieces are weighted. For example, the squares e4 and e5 have a much higher weighting than a1 and h1. The square weightings for Black are reversed (so Black’s score for f6 is the same as White’s score for f3).
The attacking pieces are also weighted, but in the reverse of the usual order. So a pawn on e4 attacking d5 gets a higher score than a queen attacking d5.
That’s it?!
Yep. To the extent that Shallow Thought plays half-way-decent moves, most of the credit goes to the computer’s thoroughness. Unlike many humans, the machine diligently evaluates even the most obscure lines and doesn’t suffer from what magicians call isolation of interest. When playing a beginner, this methodical rigour tends to compensate for its mediocre understanding of strategy.
Chess engine code – minimax
This article is part of a series – the contents page is here.
In this article we cut to the chase and present the function that implements the minimax algorithm. I’m going to cut out some miscellaneous stuff so that we can focus on the core, which is walking the tree and comparing the lines. You can get the full version in the code base.
private getBestMoveMinimax(board: Chess.Board, headStartMoves: Chess.GameMove[], depth: number, isCaptureChain: boolean, alphaScore: number): EvaluatedMove {
const movesAndReplies = this.getMovesAndReplies(board, headStartMoves);
// ... snipped the test for checkmate/stalemate, which boils down to whether we have any moves.
let maxDepth = isCaptureChain ? 6 : 4;
let bestMoveSoFar: Chess.GameMove = null;
let bestScoreSoFar: number = null;
const haveReachedDepthLimit = depth >= maxDepth;
if (haveReachedDepthLimit) {
board.isWhiteToMove = !board.isWhiteToMove;
const opponentAttacks = board.getPotentialMoves(true);
board.isWhiteToMove = !board.isWhiteToMove;
return { move: null, score: EvaluationFunction.getEvaluation(board, movesAndReplies, opponentAttacks) };
}
let numMoves = movesAndReplies.length;
let movesEvaluated = 0;
for (let move of movesAndReplies) {
if ((!move.move.isPawnAttack)
&& move.replies.some(reply => reply.isTheoreticalKingCapture)) {
continue; // move is not legal.
}
let lineEvaluation: number;
const boardAfterMove = board.applyMove(move.move);
let bestReply = this.getBestMoveMinimax(boardAfterMove, move.replies, depth + 1, isCaptureChain && move.move.isCapture, bestScoreSoFar);
lineEvaluation = bestReply.score;
if (!bestMoveSoFar
|| ComputerPlayer.isBetterScore(lineEvaluation, bestScoreSoFar, board.isWhiteToMove)) {
bestScoreSoFar = lineEvaluation;
bestMoveSoFar = move.move;
}
if (alphaScore !== null
&& ComputerPlayer.isBetterScore(lineEvaluation, alphaScore, board.isWhiteToMove)) {
break;
}
}
return { move: bestMoveSoFar, score: bestScoreSoFar };
}
private static isBetterScore(newScore: number, baseScore, isWhiteToMove: boolean) {
if (isWhiteToMove) {
return newScore > baseScore;
}
return baseScore > newScore;
}
Moves versus replies
The getBestMoveMinimax function starts by calling getMovesAndReplies(). As you can probably guess, this returns an array of all the potential moves for the current player and, for each move, all of the opposing player’s potential replies. But why do we need to calculate the replies now instead of in the next recursive call? And what is that headStartMoves parameter for? The answer is that we need the replies in order to know whether each move is legal. Recall that the move generator enumerates the moves without regard to check. The only way to know whether a move is legal is to generate all the potential replies and see if any of them is a ‘potential king capture.’ If you find one then the move is illegal (you can see this test being performed at the top of the for loop that iterates through the moves; it also ignores ‘pawn attack’ moves that are generated to help the evaluation function).
But as we start to walk the tree we will need the opponent’s replies again. After all, the moves that are the “opponent’s replies” at depth zero become the “player’s moves” at depth one! It would be inefficient to regenerate the reply moves in the next recursive call, so we pass them down via the headStartMoves parameter (Get it? They give us a “head start” in calculating the next set of potential moves).
Evaluating leaf nodes
All recursive functions have a base case and ours is no exception. The hard part is knowing when we’ve reached that base case. In one sense, we usually don’t: unless we’ve found a checkmate or stalemate we can just keep searching ever deeper and we never seem to run out of moves. So we have to draw the line somewhere and hope that we don’t get kicked too badly by the horizon effect.
The function above uses a simple cutoff based on the current search depth, with a slight boost for lines that involve nothing but capturing moves. The point here is that we somehow end up with the haveReachedDepthLimit flag. When it’s true we call the evaluation function. One of the inputs to the evaluation is our opponent’s current attack (even though it’s not their turn to move). To get this we temporarily flip the isWhiteToMove flag and call getPotentialMoves, then we flip the flag back again to restore the board.
Since we haven’t made an actual move in the base case, the return value is just the evaluation score for the state of the board – the move is null.
Searching non-leaf nodes
If we haven’t reached our depth limit then we enter the for loop that is pretty much a straight implementation of the alpha-beta algorithm that we discussed in a previous article. Note the following points as we iterate through the moves:
- As explained earlier, the first thing to do is to check that the move is actually a legal move.
- We call
Board.applyMove()to get a new board that describes the state of the game after the move has been played (remember that in this new board it will now be the opponent’s turn to move). - Then comes the recursive call. Note that we pass in our current best score (the “alpha” of the alpha-beta algorithm). This call returns to us the best score that we can achieve with this move (assuming that both players always play their best possible moves).
- If this move has the best score we’ve seen then it becomes our best-move-so-far. We have to be careful in evaluating “best” – note the call to
isBetterScorewith its isWhiteToMove parameter. For White, a more positive score is better, but for Black a more negative score is better. - Finally, if we’ve been given an alpha score we perform the alpha-beta short circuit test. If the current move’s score (the “beta” score) is better for us than the alpha score then we can bail out of the whole loop
The most confusing thing when talking about this function (particularly the alpha-beta test) is that the meaning of words like “player”, “us”, “better” and “best” flips around at each depth!
Chess engine code – running in the background
This article is part of a series – the contents page is here.
In earlier articles we’ve seen the code for generating moves. Before we use it to build a playing engine, let’s take a detour and consider how we’re going to run that engine.
We’ve already identified that, thanks to the vastness of chess’s move tree, our engine could be slow to run. Sophisticated modern engines can generate strong moves in just a few milliseconds, but unfortunately such speed and strength is beyond the scope of this project. We’re going to have to wait a few seconds for Shallow Thought to calculate its moves. (Incidentally, is this a good time to mention that Shallow Thought runs a lot faster on Chrome than on Edge? Hmmm).
But lets make a virtue of necessity and use this as an opportunity to study ways to perform slow CPU-bound tasks in a browser. As I’m sure you know, browsers are mostly single-threaded, and in any event only that main thread can touch the DOM tree. But nowadays we have an option for running a task in a background browser thread: Web Workers. The discussion below might interest you if you haven’t worked with these before.
The Player classes
Players are represented by the HumanPlayer and ArtificialPlayer classes, which derive from the PlayerBase class (see /src/app/ui/playerbase.ts). The players implement an activate() method, which is called each time the player is called upon to make a move. In the case of the HumanPlayer, activate() simply kicks the player into listening mode so that it will respond to the mouse clicks on the squares where the move is to be made. But for ArtificialPlayer, activate() invokes the engine.
ArtificialPlayer.activate()
Here’s the salient part of the ArtificialPlayer code (with some irrelevant bits removed):
export class ArtificialPlayer extends PlayerBase {
private currentBoard: Chess.Board;
private engineWorker: Worker;
activate(board: Chess.Board): void {
if (!this.engineWorker) {
this.engineWorker = new Worker("/engine.bundle.js");
}
this.currentBoard = board;
this.engineWorker.onmessage = this.onMoveDecision;
this.engineWorker.postMessage(board);
}
public onMoveDecision = (e: MessageEvent) => {
...
this.playedMove = Chess.GameMove.deserialize(e.data);
this.move.emit(this.playedMove);
}
}
Note the following:
- We declare a
Workerobject calledengineWorkerand on first use we initialize it fromengine.bundle.js. This is an extra bundle in our WebPack configuration that contains only the move-calculating code. We won’t have access to any DOM-related stuff inside the Worker and we will run into errors if we even try to bring in modules that expect to use thewindowobject, for example. - We hook up a handler for the Worker’s
onmessageevent. We have to use messages to communicate across the threads – there’s no shared memory. The essence of our handler is to turn the message into aGameMoveobject and emit it through ourmoveobservable. - Having prepared the engineWorker, we invoke it by posting a message. Notice that the message consists only of a
Boardobject containing the position to be played.
So does that message parameter arrive on the Worker thread as a full functioning Board object? Unfortunately no! It’s a bit like serialization – the materialized object contains the right data but loses the prototype chain and becomes a plain old Object. One of the worker’s tasks will be to fix it up. Let’s now switch over to the worker thread.
The engine bundle
Once the Worker picks up our posted message it starts to run the code in engine.bundle.js. The entry point for this bundle is artificialPlayerDispatch.ts
artificialPlayerDispatch.ts
Here’s the entry code (again with some irrelevant detail removed so that we can focus on the message passing).
onmessage = function (event) {
// Marshall the Board object that we have been sent.
var board: Chess.Board = Object.assign(new Chess.Board, event.data);
// Prepare a player object that will calculate the next move and tell us about its progress.
var computerPlayer = new ComputerPlayer();
var selectedMove = computerPlayer.getBestMove(board);
// Send our selected move back to the main thread.
(<any>self).postMessage(selectedMove);
}
We start by using Object.assign() to turn event.data (the raw message Object) into the fully functioning Board object that we know and love. Then it’s a simple matter of creating a ComputerPlayer object (basically, the engine) and asking it to tell us what move to play for that board. Finally, the Worker’s self object gives us the postMessage method that sends the GameMove object back to the main thread. Doing so will trigger the onMoveDecision method in ArtificialPlayer. Look back at that code and you will see a call to GameMove.deserialize(). This is the same chore of turning the posted data back into a strongly typed object on the main thread.
Conclusion
So what do we get for all this extra work? Simple – we get a user interface that doesn’t freeze up while the computer thinks about its move. In the full code base you will see that we add extra messages to drive a progress bar that lets the user know how much thinking is still to be done. That wouldn’t be possible if the engine was running on the main thread.
Chess engine code – laying the groundwork
This article is part of a series – the contents page is here.
In the last article we covered the very basic theory of a chess engine. Time to write some code! Before we can get to the interesting stuff we need to lay the groundwork with a few elementary types and enums. You can see all of these in the ChessElements.ts file. The main ones are PieceType, BoardSquare, Board and GameMove.
BoardResources
Often when we build a new system, an important design goal is extensibility. We want to avoid code that depends on the intimate details of the requirements, because we know that there is a high chance of those details changing. For this reason “premature optimization” is usually considered a bad idea. The small performance improvement you get is often completely negated by the extra work needed to maintain the code when the requirements change.
Well, our chess-playing system is not like that at all. The rules of the game are set in stone. We are absolutely justified in assuming that the board will always be 8 by 8, for example. On the other hand, performance is our biggest enemy, since the search tree is so vast. If we can shave a millisecond off the evaluation function by making intricate use of the fact that the number of pieces on the board can never increase then we should do it!
With this in mind we define the BoardResources class to hold a bunch of objects that act a bit like flyweights. For example, we create 64 BoardSquare objects and place them in BoardResources.squares. This gives us a quick, global, way for every board to refer to the object representing the e5 square. The pieces array gives us the one-and-only object representing a white pawn and so on.
Board
The Board class represents a single position. Walking the search tree means using moves to manipulate boards, so that manipulation is a performance critical task.
The Board class’s design has one key principle: Boards are immutable. Applying a move to a board gives you a brand new board, which makes Board.applyMove() one of the most important methods in the code.
Immutable objects are great because they’re easy to reason about (they can’t change, after all). But the price is that applying a move means cloning the Board to get a fresh copy that we can then update with the move. To make the clone as fast as possible, Board stores its pieces in a one-dimensional array of numbers called squares. Of course, in chess it’s much more natural to think of the squares as being a two-dimensional array, so there are helper functions to translate the square indexes (for example, to translate between “b2” and the index value 9). Outside of the Board class most of the code doesn’t need to know about our one-dimensional indexes.
Board has one more vital property: the flag isWhiteToMove. This is true when it is White’s turn to move and false when it is Black’s turn. The last thing applyMove does is to flip this value.
MoveGenerator
The MoveGenerator class contains static functions that generate the pieces’ potential moves – the raw material for our search. There’s one for each type of piece, for example here’s the signature for the knight-move function:
public static getPotentialKnightMoves(board: Chess.Board, fromSquare: Chess.BoardSquare, findKingCaptureOnly?: boolean): Chess.GameMove[] {
...
}
This function takes a Board and a square. It starts by looking at Board.isWhiteToMove to find out who is moving. It assumes that that square contains a knight of that colour! The getPotentialMoves functions return all the legal moves that a piece could make from that square, with a few caveats:
- It doesn’t take checks into consideration. So some of the moves that it generates might be illegal because they might put (or leave) the mover’s king in check.
- It includes ‘theoretical king captures’, where the moving piece captures the opponent’s king. Such moves are of course invalid, but they are the key to identifying check situations. These ‘moves’ are identified by the presence of the GameMove.isTheoreticalKingCapture flag.
- We want to know when a piece attacks an empty square (for positional evaluation purposes). For most pieces we get this information from the potential moves, but pawns are a special case. A list of legal pawn moves won’t tell us when a pawn attacks an empty square. So the getPotentialPawnMoves function has an extra option to serve up ‘moves’ that are flagged as ‘pawn attacks’.
Notice the findKingCaptureOnly parameter. If this is set to true then the function operates in a different mode, where it is simply trying to answer the question: are there any theoretical king captures? Obviously in this mode the function runs more quickly.
Board.getPotentialMoves
The last building block that we need is to generate all the moves for a position. The Board.getPotentialMoves function simply runs through all the pieces belonging to the moving player and calls each piece’s move generator function. Put them all together and you’ve got your potential moves, but to figure out whether a potential move is legal you must generate all of the opponent’s potential replies to that move and see if any of them are ‘king captures.’ If there is at least one king capture then the move is illegal because it would put (or leave) the mover in check.
