Chess-Plisco
view release on metacpan or search on metacpan
lib/Chess/Plisco/Tutorial.pod view on Meta::CPAN
When we talk about coordinates, we mean a pair of a file and a rank, but
always as 0-based indexes. So the files "a" to "h" are indexed as
0 ... 7, and the ranks "1" to "8" are indexed as 0 ... 7.
=head4 Squares
Squares are conventional coordinates like "e4" or "c7". They are only
used for presentational purposes.
=head4 Shifts
A bitboard has 64 bits, and each bit stands for a particular square of
the chess board:
a b c d e f g h
8 56 57 58 59 60 61 62 63 8
7 48 49 50 51 52 53 54 55 7
6 40 41 42 43 44 45 46 47 6
5 32 33 34 35 36 37 38 39 5
4 24 25 26 27 28 29 30 31 4
3 16 17 18 19 20 21 22 23 3
2 8 9 10 11 12 13 14 15 2
1 0 1 2 3 4 5 6 7 1
a b c d e f g h
So the square "e4" is represented by the bit with the index 28 of a
bitboard (actually the 29th bit if you count from 1). So, a better term
may actually be "index" or "bit number".
But you do not have to remember the mapping. Instead just use the constants
C<CP_A1> for "a1", C<CP_A2> for "a2" and so on.
=head4 Shift Masks
How would you find out whether the square "e4" is occupied by a white
piece? You create a bitboard (64-bit integer) where only the 28th bit is
set and AND that with the bitboard of the white pieces. And you create a
bitboard where only the 28th bit is set with a shift operation:
$e4_square = (1 << 28) & $w_pieces
You "shift" the one 28 places to the left. And this is why the indexes
or bit numbers are called "shifts" here. And a shift mask is a bitboard
with exactly one bit set.
The code will be better understandable if you replace the literal 28 with a
constant:
$e4_square = (1 << CP_E4) & $w_pieces
=head3 C<Chess::Plisco> Instances
Unlike most Perl objects, instances of C<Chess::Plisco> are blessed
array references. This design decision was taken because accessing
accessing array elements is faster than accessing hash elements. But
there is no need to remember the exact ordering of the array. You can
either use dedicated macros that operate directly on
C<Chess::Plisco> instances or use constants for the indexes:
use Chess::Plisco (:all);
use Chess::Plisco::Macro;
$pos = Chess::Plisco->new;
# Equivalent!
$w_pieces = $pos->[CP_POS_WHITE_PIECES];
$pos->[CP_POS_WHITE_PIECES] = $_pieces;
$w_pieces = cp_pos_white_pieces $pos;
cp_pos_white_pieces $pos = $w_pieces;
=head3 Pieces
The chess pieces are specified by an enumeration:
=over
=item * C<CP_NO_PIECE> 0
=item * C<CP_PAWN> 1
=item * C<CP_KNIGHT> 2
=item * C<CP_BISHOP> 3
=item * C<CP_ROOK> 4
=item * C<CP_QUEEN> 5
=item * C<CP_KING> 6
=back
The default values for each piece are defined by these constants in
C<Chess::Plisco>:
=over
=item * C<CP_PAWN_VALUE> 100
=item * C<CP_KNIGHT_VALUE> 320
=item * C<CP_BISHOP_VALUE> 330
=item * C<CP_ROOK_VALUE> 500
=item * C<CP_QUEEN_VALUE> 900
=back
Unfortunately, these constants cannot be overridden in derived classes in an
easy manner. While C<$class->CP_KNIGHT_VALUE()> would produce the
overridden value for the caller it would not for just C<CP_KNIGHT_VALUE>.
Unfortunately, the latter is faster by orders of magnitude and therefore the
former version is not used.
=head3 Moves
=head4 Internal Move Representation
A move in C<Chess::Plisco> is simply an integer. The individual bits of a
move are:
lib/Chess/Plisco/Tutorial.pod view on Meta::CPAN
=over
=item * C<cp_move_set_to($move, $to)>: the destination square as a shift
=item * C<cp_move_set_from($move, $from)>: the starting square as a shift
=item * C<cp_move_set_promotion($move, $piece)>: the promotion piece
=item * C<cp_move_set_piece($move, $piece)>: the attacking piece
=item * C<cp_move_set_captured($move, $piece)>: a possible captured piece
=back
There are no macros for setting the colour or the en-passant flag.
=head4 Parsing Moves
The method C<parseMove()> can be used for creating a move. It expects the
move in either:
=over 4
=item Coordinate Notation
=item Standard Algebraic Notation (SAN)
=item Long Algebraic Notation (LAN)
=back
The coordinate notation is the notation that most chess engines use. It is
simply the start and the destination square appended plus an optional piece
to promote a pawn to, for example "b1c3" for the piece on square "b1" moving
to "c3" or "e7d8q" for a pawn on "e7" capturing the piece on "d8" being promoted
to a queen.
Standard Algebraic Notation (SAN) is the notation conventionally used for
describing chess games. You will find more information about it on the internet.
Long Algebraic Coordination is similar to SAN but always gives the from and
two square.
Note that the move parser is very forgiving and accepts a lot of moves that
are not complying with the standard.
=head4 Making Moves Human-Readable
The methods C<SAN>, C<LAN>, and C<moveCoordinateNotation> can be used to print
a move in humand-readable format:
$pos->SAN($move);
# Nxe7#
$pos->LAN($move);
# Nf5xe7#
$pos->moveCoordinateNotation($move);
# d5e7
In general, you will prefer printing moves in Standard Algebraic Notation.
=head2 Using Macros
When dealing with chess programming you often find yourself executing
small operations many times, more than often millions of times. You can,
of course, write subroutines for these operations but the calling
overhead sums up and contributes significantly to the execution time of
your code.
Even writing these routines in C does not help at all because the
calling overhead is large compared to the execution time of the function
body.
This is why the module C<Chess::Plisco::Macro> exists. It makes a lot
of small helper functions available, the names of which all begin with
C<cp_>. You can use them more or less like functions but they are inlined
into your code at compile-time.
But this is only necessary, when performance is important. For normal
purposes, you can just use regular instance methods instead of macros.
But when you want to use the macros, there are a couple of caveats that you
have to keep in mind:
=head3 Use C<Chess::Plisco::Macro> and(!) C<Chess::Plisco>
The macros in C<Chess::Plisco::Macro> make use of constants defined in
C<Chess::Plisco>. If you do not import these constants, you will get
strange errors. You should therefore start your own code with this
boilerplate:
use strict;
use integer;
use Chess::Plisco qw(:all);
use Chess::Plisco::Macro;
=head3 Use C<integer>
Some of the macros will only work on integers. You must therefore always
C<use integer> in the scope of your code. Not doing so will result in
errors!
If you need floating point arithmetics, activate them only in the limited
scope of a block:
{
no integer;
printf "avg. loss in centipedes: %g\n", $score / 100;
}
=head3 Do Not Use Here Documents
The translation currently chokes on here documents (E<lt>E<lt>EOF ...). So
sorry, I have to check out once again how to make L<PPI::Document> round-trip
safe.
=head3 Do not Create References to Macros
Macros are not Perl subroutines. They are more or less stupidly replaced
with chunks of code. Things like C<my $sub = \&cp_pos_white_pieces> may or
may not cause a syntax error but they will never do what you expect.
=head3 Be Prepared for Errors
The macro expansion internally makes use of C<PPI::Document> and it
therefore shares all of that module's inevitable limitations. And it
adds a fair amount of its own shortcomings. The macro approach is rather
an experiment than a production-ready general-purpose tool.
=head2 Common Bitboard Operations
Bitboards are fast and efficient but working with them is a little bit
convoluted compared to more conventional representations of a chess
board like two-dimensional arrays or hashes.
=head3 Counting Pieces
Task: Count the number of white pawns on the board.
Without macros, it is pretty straight-forward.
use Chess::Plisco;
my $pos = Chess::Plisco->new;
my $white_pawns = $pos->[CP_POS_WHITE_PIECES] & $self->[CP_POS_PAWNS];
my $count = $pos->bitboardPopcount($white_pawns);
print "There are $count white pawns on the board.\n";
Using macros looks a little bit strange at first glance but that strangeness
is unavoidable:
use Chess::Plisco;
use Chess::Plisco::Macro;
my $pos = Chess::Plisco->new;
my $white_pawns = cp_pos_white_pieces($pos) & cp_pos_pawns($pos);
my $count;
cp_bitboard_popcount $white_pawns, $count;
print "There are $count white pawns on the board.\n";
The important line is the last but one. The macro C<cp_bitboard_popcount>
counts the number of bits set in an integer, and this is exactly what
you need here. But you have to give the variable that should hold the
result as a regular scalar C<$count> and not as a reference C<\$count>.
=head3 Iterating Bitboards
Task: Print the square for every white pawn on the board.
=head4 Conventional and Slow Approach
Iterating over a bitboard can be done in an intuitive and straight-forward way:
use integer;
use Chess::Plisco qw(:all);
use Chess::Plisco::Macro;
my $white_pawn_mask = cp_pos_white_pieces($pos) & cp_pos_pawns($pos);
foreach my $shift (0 .. 63) {
my $shift_mask = 1 << $shift;
if ($shift_mask & $white_pawn_mask) {
my $square = cp_shift_to_square $shift;
print "There is a white pawn on $square.\n";
}
}
You basically shift a 1 bit subsequently to the left, and then test whether the
corresponding bit is set in the bitboard. There is nothing wrong with this
approach and it is actually reasonably fast.
=head4 Efficient and Fast Approach
But there is a another technique that achieves the same result and is often
faster:
use integer;
use Chess::Plisco qw(:all);
use Chess::Plisco::Macro;
my $pos = Chess::Plisco->new;
my $white_pawn_mask = cp_pos_white_pieces($pos) & cp_pos_pawns($pos);
while ($white_pawn_mask) {
my $shift = cp_bitboard_count_trailing_zbits $shift_mask;
my $square = cp_shift_to_square $shift;
print "There is a white pawn on $square.\n";
$white_pawn_mask = cp_bitboard_clear_least_set $white_pawn_mask;
}
If you count the trailing zero bits with the macro
C<cp_bitboard_count_trailing_zbits()> you get the position of that bit in the
bitboard and you can now use that information for whatever you want to do.
At the end of the loop body, you clear the least significant bit of the
bitboard. Therefore, the population count of the bitboard decreases by
one with each iteration.
If you want to benchmark both approaches, make sure to remove the expensive
operations inside the loop body, that is the call to C<cp_shift_to_square()>
and especially the print to the console.
What you will find out is that the second approach runs around 10-15 %
faster than the conventional approach. On the one hand you have less
iterations (8 vs. 64) but masking out the bits and especially counting the
trailing zero bits outweighs that mostly.
But if you replace "pawn" with "king" in the code, the 2nd variation runs
around 700 % or seven times faster than the conventional approach. This is
because you always have exactly one loop iteration instead of 64. And in
the case of kings you could improve that even further by taking advantage of
the fact that there is always exactly one white king on the board. So you
do not even need a loop.
Most of the time, the bitboards you are dealing with are sparsely populated
and it is advantageous to take the second approach. Only in the exceptional
case that you want to iterate over a bitboard with all pieces of one colour
or even all pieces of both colours, you are better off using the conventional
approach.
=head2 Game Play
=head3 Initializing a Position
You use the constructor to instantiate a chess position. For the start
position you call it with arguments. If you have the position represented
as a string in Forsyth-Edwards Notation (FEN) you pass that as an
argument to the constructor:
$pos = Chess::Plisco->new;
# Or:
$fen = 'r4rk1/1p3pp1/1q2b2p/1B2R3/1Q2n3/1K2PN2/1PP3PP/7R w - - 3 22';
$pos = Chess::Plisco->new($fen);
=head3 Making Moves
lib/Chess/Plisco/Tutorial.pod view on Meta::CPAN
There is also a method C<dumpAll()> which dumps all bitboards at once.
=head3 Checking for Check
Finding out whether the side to move is in check, can be done like this:
$checkers = $pos->inCheck;
if ($checkers) {
print "pieces giving check: ", $pos->dumpBitboard($checkers);
}
In fact, what you get is not a boolean flag but a bitboard with the pieces
that are giving check.
You can get more information in array context:
($checkers, $king_shift, $defence_bb) = $pos->inCheck;
The king shift is the position of the (attacked) king. The defence bitboard
is a bitboard where any piece may defend the check.
=head3 Checking for Pieces
Finding out whether a white piece is on "e4" can be done like this:
$shift = CP_E4;
# or $shift = $pos->squareToShift('e4');
# or $shift = $pos->coordinatesToShift(4, 0);
$mask = 1 << $shift;
$is_white = $mask & $pos->[CP_POS_WHITE_PIECES];
# or: $is_white = $mask & cp_pos_white_pieces($pos);
If you want to know whether it is a white king, you go like this:
$is_king = $mask & ($pos->[CP_POS_WHITE_PIECES] & $pos->[CP_POS_KINGS]);
# or: $is_king = $mask & (cp_pos_white_pieces($pos) & cp_pos_kings($pos));
If you want to also check for the colour, you additionally have to do the
bitwise AND of the white or black bitboard.
Finding out which piece is on a particular location can also be done with
dedicated methods:
($piece, $colour) = $pos->pieceAtSquare('e4');
($piece, $colour) = $pos->pieceAtCoordinates(4, 3);
($piece, $colour) = $pos->pieceAtShift(27);
$piece = $pos->pieceAtSquare('e4');
$piece = $pos->pieceAtCoordinates(4, 3);
$piece = $pos->pieceAtShift(27);
In array context, you get the piece and the colour, in scalar context just the
piece. The piece is one of C<CP_NO_PIECE>, C<CP_PAWN>, C<CP_KNIGHT>, C<CP_BISHOP>,
C<CP_QUEEN>, or C<CP_KING>, and the colour one of C<CP_WHITE>, C<CP_BLACK>,
or C<undef> if there is no piece at all at the specified location.
=head3 Castling State
The castling state is encoded with other state information in one single
integer as a bit mask. It is highly recommended that you use the dedicated
methods from L<Chess::Plisco> or the macros from L<Chess::Plisco::Macro> for it:
$white_can_castle_king_side = cp_pos_white_king_side_castling_right $pos;
# or $white_can_castle_king_side = $pos->whiteKingSideCastlingRight;
$white_can_castle_queen_side = cp_pos_white_queen_side_castling_right $pos;
# or $white_can_castle_queen_side = $pos->whiteQueenSideCastlingRight;
$black_can_castle_king_side = cp_pos_black_king_side_castling_right $pos;
# or $black_can_castle_king_side = $pos->blackKingSideCastlingRight;
$black_can_castle_queen_side = cp_pos_black_queen_side_castling_right $pos;
# or $black_can_castle_queen_side = $pos->blackKingSideCastlingRight;
=head3 En Passant
Find out on which square en-passant capturing is possible:
$en_passant_shift = $pos->enPassantShift;
# or $en_passant_shift = cp_pos_en_passant_shift $pos;
This will be 0 if capturing en passant is not possible in the particular
position. You may have to be careful to use this information because 0 is
also the "shift" for the square "h1". In doubt, go like this:
$ep_shift = cp_pos_en_passant_shift $pos;
if ($ep_shift && $ep_shift == $location) {
# do what you need ...
}
=head3 Evading a Check
A check can be defended in one of three ways:
=over 4
=item Moving the King
This is always an option.
=item Capturing the Piece Giving Check
This is only an option if there is just one piece giving check (because you
cannot capture multiple pieces at once).
=item Blocking the Check With a Piece
You can also block the check by moving a piece between the king and the
opponent's piece giving check. But this is not an option if multiple pieces
give check, or if the piece giving check is a queen, a rook, or a knight.
Why? If the piece giving check is a pawn, there is no space between it and
the king, and a knight can jump over other pieces.
=back
Remember that the method C<inCheck()> gives you a bitboard with all
pieces giving check. Alternatively, you can use the macro C<cp_pos_in_check>.
=head2 Various Tricks
=head3 Calculating the Number of Pieces
The locations of pieces are usually represented as bitboards. You therefore
( run in 0.674 second using v1.01-cache-2.11-cpan-8f98c5d2c55 )