Franklin: A Chess Engine

Engine evaluation

Engine evaluation: make a move...

Positive = better for white. Negative = better for black.
100 is roughly equal to one pawn.
A ridiculously high number means checkmate.

Game history (PGN):

How it works

TLDR:

You wake up Franklin by making a move.
Franklin finds all possible response moves.
Franklin quickly looks over each move to sort them with the best-looking ones first.
For each move, Franklin imagines making that move and does this same process from the opposite side's perspective, building a tree of possible positions.
When Franklin grows its tree grows to a certain depth, Franklin evaluates how good each possible position is using factors like difference in material and piece development, and assigns it a score.
Franklin chooses the move to which it gave the highest score as the best move.
Franklin takes a nap while you think over your next move.

To get a bit more detailed about it:

Minimax

The core concept inside Franklin is minimizing the maximum advantage the opponent could gain. If Franklin has scores for every move you can make in response to its move, Franklin will give its move the lowest score of your possible moves; that is, the worst (for Franklin) position that could happen after you respond to Franklin's move. If Franklin has scores for every move it can make, it will choose the highest-scored move; that is, the move where your best (for you) response is the least bad (for Franklin).

Franklin needs to look at A LOT of possibilities with this approach; there are at least 4,865,609 possible chess positions after two and a half moves from the starting position. Franklin reduces its workload using alpha-beta pruning. If Franklin finds an outcome for a move that's worse than a move it's already evaluated, Franklin can safely skip over this new move, "pruning" that part of the tree and saving a lot of work.

Move sorting

Alpha-beta pruning works better when more favorable moves are evaluated first, so subsequent moves will be more likely to have worse outcomes than previously-evaluated moves, leading to pruning. To optimize for pruning, Franklin presorts its list of moves before doing a full evaluation on each one. When presorting moves, Franklin looks at whether the move is a pawn promotion, whether the move hangs a piece in front of a pawn, and, if the move is a capture, the values of the capturing and captured pieces (Most Valuable Victim, Least Valuable Aggressor heuristic).

Additionally, if a branch is pruned, Franklin adds the move whose superiority caused the branch to be pruned to a list of "killer moves" for that depth from the root, if that move isn't a capture. These killer moves are evaluated before other moves. The idea is that if a move was found to be good on a previous search, it may still be a good move.

Position evaluation

When it's finally time to give a score to a single position, Franklin looks at how well-positioned each piece on the board is. Franklin has built-in piece-square tables for each type of piece, with a score for every square that piece could end up on. These scores are combined with traditional material values to determine which side is ahead positionally, and by how much. Franklin also gives a very slight bonus to positions where the opposing king is in check.

In the endgame, what makes a good position is different, and Franklin adapts by adding two new factors when there are 7 or fewer pieces on the board: A lower score when its king is farther from the opposing king, and a higher score when the opposing king is closer to the edges of the board. This allows Franklin to perform well in endgames without increasing its depth or using an endgame tablebase like Syzygy.