A “Chess Game” in Ada 2012?
Developing a chess game can be a difficult task. This article shows how the implementation of a number of paradigms and services underpinned by Ada 2012 makes it possible to ease this task.
Introduction¶
As part of the Ada trainings provided by Systerel, a number of exercises are proposed. Everything being very technical, these exercises also have a playful side as shown in the “chess game” example proposed within the framework of our training “Ada2012 - The keys”.
Through this article we will present some elements of what the Ada 2012 language brings to the development of such a chess game.
The code presented is the framework of the engine of a basic chess game (1200 ELO) and representing 2000 lines of code in Ada 2012. The GUI is provided by a client not presented here and provided during the training.
Only basic knowledge of chess game rules are necessary to follow this article.
Although this will not be presented in this article, the implementation also uses traits specific to the Ada 2012 language such as:
- Static predicates,
- Quantified expressions,
- Pre/post conditions.
Oriented Object Design¶
A chess game is a set of pieces of different types (pawn, bishop, etc.) but having common characteristics:
- They have a color (White or Black),
- They have a position on a chessboard,
- They move on the same board respecting precise rules, some of which are common to all pieces.
We therefore consider here that:
- A chessboard is a “container” of pieces,
- A piece is a cursor on this container.
subtype Square_T is Positive range 1 .. 8 * 8;
-- The chessboard.
type Chessboard_T is array (Square_T) of access Piece_T'Class;
type Board_T is tagged record
Chessboard : Chessboard_T;
end record;
type Color_T is (Black, White);
-- The pieces class
type Piece_T (Color : Color_T) --> its color
is abstract tagged record
Square : Square_T; --> its position
Board : access Board_T; --> its board
end record;
-- The weight of a piece is used by the evaluation function (see next)
function Weight (Piece : in Piece_T) return Integer is abstract
with Inline => True;
-- we need to know the rules for moving a piece
function Move_Valid_To (Piece : in Piece_T;
To : in Square_T) return Boolean is abstract
with Inline => True;
The class function Valid_To implements the rules
common to all the pieces with respect to their movements:
function Valid_To (Piece : in Piece_T'Class;
To : in Square_T) return Boolean is
Chessboard : constant Chessboard_T := Piece.Board.Chessboard;
Result: Boolean := True;
begin
if Chessboard (To) /= null and then
Chessboard (To).Color = Piece.Color
then
-- I can't go on a square containing a piece of my color.
-- I can't "stand still."
Result := False;
end if;
return Result;
end Valid_To;
Knowing that each part will have to implement its own function
Move_Valid_To (the abstract above) to verify
the validity of his movements.
Now we must define the pieces of our board:
type Pawn_T is new Piece_T with null record;
overriding
function Move_Valid_To (Pawn : in Pawn_T;
To: in Square_T) return Boolean;
overriding
function Weight (Pawn : in Pawn_T) return Integer is
(if Pawn.Color = White then -1 else +1) with Inline => True;
With here for example:
overriding
function Move_Valid_To (Pawn : in Pawn_T;
To : in Square_T) return Boolean is
Result : Boolean := Pawn.Valid_To (To);
begin
if Result then
Result := ... -- test of the validity of the movement specific to the pawn
end if;
return Result;
end Move_Valid_To;
The knight:
type Knight_T is new Piece_T with null record;
overriding
function Move_Valid_To (Knight : in Knight_T;
To: in Square_T) return Boolean
with Inline => True;
overriding
function Weight (Knight : in Knight_T) return Integer is
(if Knight.Color = White then -500 else +500)
with Inline => True;
The queen, the king, the rook, etc…
And populate the board:
Chessboard : aliased Chessboard_T := (Chessboard => (1 | 8 => new Rook_T(Black),
...
57 | 64 => new Rook_T(White),
...
others => null)); --> empty cells
Our chessboard being populated, it is enough to move a piece and the appropriate method to verify the validity of the movement of this will be called by redirect.
-- a1(57) a2(49)
if Chessboard.board (57).Move_Valid_To (49) then
...
-- a2(49) a3(41)
if Chessboard.board (49).Move_Valid_To (41) then
...
-- a3(41) a4(33) CONSTRAINT_ERROR (access check)
if Chessboard.board (41).Move_Valid_To (33) then
...
Implementation of AI¶
The AI of the game is implemented through a Mini-Max algorithm consisting in computing successively all the possible moves for each of the players. An evaluation function makes it possible to associate a value to a game situation for each move played. All of the possibilities will then create a tree of possible moves:
- The root of the tree represents the current state of the game (here Empty_Tree).
- A node represents a legal situation in the game.
- The children of a node are the situations that can be reached from this node by playing by the rules.
- A branch represents a sequence of ½ legal moves in the game.
Analysis of this tree (upwards analysis from its leaves) thus makes it possible to know the initial move making it possible to have the best score:
Imagined in 1928 by Von Neumann, the basic postulate of this algorithm is that the computer’s opponent will always play the best move possible.
However, this algorithm has two drawbacks:
- He explores all the branches of the tree without any form of distinction between these, while some will produce no move opportunity.
- The number of elements in the tree explodes when the depth increases. If we calculated all the possible moves with a depth of 100, we would get a tree with more elements that nucleons in the universe, that is ~$10^{80}$ !
A more efficient algorithm such as Alpha-Beta (or Alpha-Beta pruning) could have been implemented but in the context of the exercise it was decided to implement the simplest algorithm.
The move tree has been implemented using the new Ada 2012 container
Ada.Containers.Multiway_Trees.
Each node in the tree contains the following information:
- The color played,
- The half move played (From/To),
- The board resulting from the half move played,
- The value of this chessboard (the result of the evaluation function),
type Possible_Move_T is record
From, To: Square_T := Square_T'First;
Color : Color_T := White;
Value : Integer = 0;
Chessboard : Ref_Board_T := null;
end record;
package Pkg_Move_Tree is new
Ada.Containers.Multiway_Trees (Element_Type => Possible_Move_T);
Move_Tree : Tree := Pkg_Move_Tree.Empty_Tree; --> root
The evaluation function used here looks like:
function Value (Chessboard : in Chessboard_T;
Color : in Color_T) return Integer is
...
begin
for Piece of Board.ChessBoard loop
if Piece /= null then
Result: = Result + Piece.Weight;
end if;
end loop;
return Result + ... . ;
end Value;
The construction of the tree and its browsing are done through
the many services offered by the Ada.Containers.Multiway_Trees package.
Conclusion¶
The Ada 2012 language has brought new features such as:
- Programming by contract and the notion of aspects,
- New forms of expression and predicates,
- Support for SMP architectures,
- Iterators,
- An extension of the predefined environment,
- Various and varied improvements.
Apart from semantic corrections or “aesthetic” improvements, and like its “predecessors”, Ada 2012 put particular emphasis on new features to guarantee safety and integrity of the applications developed while embracing new technologies like SMP.
Although the implementation presented here could have been developed in another language, the fact that it was carried out in Ada 2012 contributed to having a concise, legible and reliable source code.
Comments