- Get link
- X
- Other Apps
In my first article I try to start with a simple AI example in it's the simplest form: A computer algorithm playing chess. They are basic stuff if you get an introduction to AI in a university college and I'll provide it here with no charges!
I try to make my code examples in PHP since most of my code is in PHP and it's easy to setup a PHP project. If you really want to achieve anything with AI, please try to use a different language that is capable of parallel processing (preferably in the GPU).
After creating this article I did some finetuning as there were a few nitpicks and the flyweight is actually not working (but enabling resulted in an other bug). In case you do not have patience, you can download it right away from my github account.
Finding a chess library
I thought that I would have to program my own chess board class that should have a method that gives me all possible moves, but it seems other people have already done the work for me. I found a composer package called p-chess/chess. The only complain I had is that the class is not immutable and you have to use the undo method to go back one move. The code example shows an example of a random chess play. Except the function doesn't work. I needed one small change to see a random chess match:
<?php
include 'vendor/autoload.php';
use \PChess\Chess\Chess;
use \PChess\Chess\Output\UnicodeOutput;
$chess = new Chess();
while (!$chess->gameOver()) {
$moves = $chess->moves();
$move = $moves[random_int(0, count($moves) - 1)];
echo (new UnicodeOutput())->render($chess) . PHP_EOL;
echo "\033[19A";
$res = $chess->move($move->san);
assert($res !== null);
}
Brute force: the perfect chess computer
The most naive implementation would be to brute force all possible moves and see which move has the highest win chance. For example we assume the computer is controlling the black pieces and he wants to win:
use PChess\Chess\Chess;
use PChess\Chess\Move;
use PChess\Chess\Output\UnicodeOutput;
use PChess\Chess\Piece;
use RuntimeException;
/**
* A DTO that contains a move and a rating how good this move is rated
*/
class MoveResult
{
public function __construct(
public string $move,
public float $score,
) {
}
}
use PChess\Chess\Chess;
use PChess\Chess\Output\UnicodeOutput;
use PChess\Chess\Piece;
/**
* Class that returns the best move for a specific chess board and gives it a score.
*/
class BestMovePicker
{
private array $alreadyCalculated = [];
/**
* Returns the next best move that is beneficial for black.
* It does this by calling this method recursively for every possible next move until someone wins.
* It keeps track of already calculated boards to speed this process up.
*/
public function decide(
Chess $chess
): MoveResult {
$hash = json_encode($chess->board);
if (!isset($alreadyCalculated[$hash])) {
$moves = $chess->moves();
$bestResult = null;
foreach ($moves as $move) {
$san = $move->san;
$result = $chess->move($san);
assert(null !== $result, 'illegal move');
try {
// if chess match is over after this move, check if black or white won.
if ($chess->gameOver()) {
return new MoveResult($san, $chess->turn === Piece::BLACK ? 1000 : -1000);
}
$result = $this->decide($chess);
$result = new MoveResult($san, $result->score);
if (!$bestResult || ($bestResult->score < $result->score)) {
$bestResult = $result;
}
} finally {
$chess->undo();
}
}
assert(!empty($bestResult));
$this->alreadyCalculated[$hash] = $bestResult;
}
return $this->alreadyCalculated[$hash];
}
}
Then we modify our code to play chess using our BestMovePicker class:
use \PChess\Chess\Chess;
use \PChess\Chess\Output\UnicodeOutput;
$chess = new Chess();
$picker = new BestMovePicker();
echo (new UnicodeOutput())->render($chess) . PHP_EOL;
while (!$chess->gameOver()) {
echo sprintf("Available moves: %s\n", implode(', ', $chess->moves()));
$result = $picker->decide($chess);
$res = $chess->move($result->move);
echo sprintf("Next turn %1s %30s score: %.2f\n", $chess->turn, $result->move, $result->score);
echo (new UnicodeOutput())->render($chess) . PHP_EOL;
assert($res !== null);
}
This is a lot of code to figure out how it works.
- First of all BestMoveDecider can be seen as a flyweight design pattern. It will only do a calculation if the calculation was not done yet. The same result will be given to the same chess board.
- We iterate over all possible moves, execute the move and call decide again to calculate the rating of the next next move of the chess board.
- If a board is a victory for black or a draw on whites turn we give it a score of 1000.
- If a board is a loss for black or a draw on our turn we give it a negative score of -1000.
- We always pick the highest score, so basically white tries moves that have the highest chance in losing the match.
- If you try to run it you will see it looks like it will run forever. In reality it does so many calculations that it will take hundreds of years to get the result. Eventually it will be done.
So our chess computer is too slow to be a chess player as a human player would die before the computer is done calculating his first move. It would take centuries to compete against this computer (but since the computer knows all moves you can not win from it).
Brute force works against very simple games like tic tac toe or four in a row, but for chess there are too many moves to calculate all of them. Oh yeah: if you play tic tac toe or four in a row with perfect strategy it will always end in a draw.
Speeding up
The problem mentioned above where checking all possible combinations would take too long to execute is called a NP-problem. It can be solved perfectly by checking all possible variations, but it's often not feasible to do as it just takes too much time on a regular computer (DNA and quantum computers can solve these problems in seconds though).
The easiest solution would be to reduce the number of recursion we use. We do this by adding a second argument to decide() to tell the amount of recursion and stop iterating if the recursion has reached a certain limit.
I was testing it locally inside a docker container, but since PHP is not compiled to machine code you can not look further than 2 turns before it becomes too slow. In compiled languages you can probably look no further than 15 turns, maybe 30 turns if you use a GPU for parallel calculations. If there are less pieces on the board, 2 might be a little bit low as we could look more moves ahead.
So this is now our code (only BestMovePicker was changed):
/**
* Class that returns the best move for a specific chess board and gives it a score.
*/
class BestMovePicker
{
private array $alreadyCalculated = [];
/**
* Returns the next best move that is beneficial for black.
* It does this by calling this method recursively for every possible next move until someone wins.
* It keeps track of already calculated boards to speed this process up.
*/
public function decide(
Chess $chess,
int $maxRecursion = 2
): MoveResult {
$hash = json_encode($chess->board) . $maxRecursion;
if (!isset($alreadyCalculated[$hash])) {
$moves = $chess->moves();
$bestResult = null;
foreach ($moves as $move) {
$san = $move->san;
$result = $chess->move($san);
assert(null !== $result, 'illegal move');
try {
// if chess match is over after this move, check if black or white won.
if ($chess->gameOver()) {
return new MoveResult($san, $chess->turn === Piece::BLACK ? 1000 : -1000);
}
if ($maxRecursion > 0) {
$result = $this->decide($chess, $maxRecursion - 1);
$result = new MoveResult($san, $result->score);
} else {
$result = new MoveResult($san, 0);
}
if (!$bestResult || ($bestResult->score < $result->score)) {
$bestResult = $result;
}
} finally {
$chess->undo();
}
}
assert(!empty($bestResult));
$this->alreadyCalculated[$hash] = $bestResult;
}
return $this->alreadyCalculated[$hash];
}
}
So the magic that has changed is just this line:
if ($maxRecursion > 0) {
$result = $this->decide($chess, $forPlayer, $maxRecursion - 1);
$result = new MoveResult($san, $result->score);
} else {
$result = new MoveResult($move, 0);
}
So if this $maxRecursion argument is still higher than 0 we run the decide method recursively with $maxRecursion decreased by one. Otherwise we give the board the score 0.
The problem that we see now is that this chess computer will start very badly. Since we only look 2 moves ahead and the shortest chess match is 4 moves, the computer can only start with the first found move or a random move (our current implementation picks the first found move). We can tackle this problem by pre-caching results by filling in some moves in $alreadyCalculated.
A better scoring system
We put +1000 on winning and -1000 on losing and the score is 0 if we have no victories or losses. Those numbers are just some values we could call weights. We could add weights to all pieces still on the board because the more pieces you have the more likely you win. We could also add weight to draws as well, because our current implementation makes very little sense here.
This becomes our implementation and black wins because white removes all his pawns except the one in front of the king so the queen can easily check mate the king. And if we put the $maxRecursion on value 4 we have to wait around 5 minutes per turn, but it will result in the fool's mate.
/**
* Class that returns the best move for a specific chess board and gives it a score.
*/
class BestMovePicker
{
public const VICTORY = 1000;
public const LOSS = -1000;
public const DRAW = 500;
public const PAWN = 1;
public const KNIGHT = 12;
public const BISHOP = 16;
public const ROOK = 16;
public const QUEEN = 32;
private array $alreadyCalculated = [];
private function giveScore(Chess $chess): int
{
$score = 0;
if ($chess->inDraw()) {
$score += self::DRAW;
}
if ($chess->inCheckmate()) {
$score += ($chess->turn === Piece::WHITE ? self::VICTORY : self::LOSS);
}
foreach ($chess->board as $boardCell) {
$cellScore = match($boardCell?->getType()) {
Piece::PAWN => self::PAWN,
Piece::KNIGHT => self::KNIGHT,
Piece::BISHOP => self::BISHOP,
Piece::ROOK => self::ROOK,
Piece::QUEEN => self::QUEEN,
default => 0,
};
if ($boardCell?->getColor() === Piece::WHITE) {
$cellScore = -$cellScore;
}
$score += $cellScore;
}
return $score;
}
/**
* Returns the next best move that is beneficial for black.
* It does this by calling this method recursively for every possible next move until someone wins.
* It keeps track of already calculated boards to speed this process up.
*/
public function decide(
Chess $chess,
int $maxRecursion = 2
): MoveResult {
$hash = json_encode($chess->board);
if (!isset($alreadyCalculated[$hash])) {
$moves = $chess->moves();
$bestResult = null;
foreach ($moves as $move) {
$san = $move->san;
$result = $chess->move($san);
assert(null !== $result, 'illegal move');
try {
// if chess match is over we return the current board rating.
if ($chess->gameOver() || $maxRecursion <= 0) {
return new MoveResult($san, $this->giveScore($chess));
}
$result = $this->decide($chess, $maxRecursion - 1);
$result = new MoveResult($san, $result->score);
if (!$bestResult || ($bestResult->score < $result->score)) {
$bestResult = $result;
}
} finally {
$chess->undo();
}
}
assert(!empty($bestResult));
$this->alreadyCalculated[$hash] = $bestResult;
}
return $this->alreadyCalculated[$hash];
}
}
If we change the weights we get a different match. What are the correct values of these weights? The only way is by randomly changing the weights and see if the chess computer becomes a better player.
Minimax algorithm
If you would rewrite it to play against a human player you will notice the AI is still really stupid and that has to do because the AI assumes you intentionally try to lose.
The problem is this line:
if (!$bestResult || ($bestResult->score < $result->score)) {
$bestResult = $result;
}This line of code always picks the highest score (highest chance black wins), but this also happens on white's turn which makes no sense. As you can guess, we can rewrite it to assume white always try to get the lowest score possible (lowest chance black wins):
if (!$bestResult || ($chess->turn === Piece::WHITE && $bestResult->score < $result->score) || ($chess->turn === Piece::BLACK && $bestResult->score > $result->score)) {
$bestResult = $result;
}This algorithm is called the minimax algorithm and it is often used with games where two people compete against each other. It can also be used to ignore some moves when looking for the best move so it can be made much faster. But that is a bit out of context for this page.
I uploaded the chess program on github so feel free to play with it or see if you can make it a better chess AI.
Conclusion
When I ran this, the game resulted in a draw by repeating the same move more than once, because the draw weight was 500 which was quite high. After some tinkering I ended up with a nice computer versus computer chess match where white eventually wins. I will make a new article in the future how we can use AI to tinker these weights to improve our chess computer. It will be an introduction to evolutionary programming!
As you can see the code is just a simple (recursive) algorithm, but I'm quite sure it can beat a rookie chess player.
For now have fun with the chess AI.
Comments
Post a Comment