|
I (Willem Rens, a retired IT professional, not a programmer, but an
analyst) wrote a chess program named Gambit-80
around 1980. The program was one of the first reasonably playing programs in the
Netherlands. It became commercial and known in tournaments where computers
played against computers. The language for the program was Z80 assembler
language running on RadioShack’s TRS-80, one of the first home computers. In
those days, I had several ideas to improve the program, but most failed hopelessly.
Reasons were hardware limitations (16k of memory!) and not to forget the
complexity barrier.
|
|
|
|
About thirty years later, a lot happened in computer land. When
Microsoft introduced the .NET framework, I became challenged to try my old ideas
about chess programming with Visual Basic. The result got the name GambitVB.
GambitVB plays reasonable chess and offers a complete and friendly
user-interface. The emphasis is on well-structured, self-documenting,
object-oriented code, created in MS Visual Studio. When I wrote his very first
program, I was inspired by the book “Sargon: A Computer Chess Program” written
by Dan and Kathe Spracklen. Today, a web site delivering free software and free
documentation looks an obvious choice to inspire others.
|
|
The first program was completely programmed with Visual Basic using Visual
Studio 2005. Like in all following versions of GambitVB, the
software was built in three major parts: The Move Engine, the Search
Engine, and the Graphical User Interface. In addition, version 1.0
included an openings book developer, which created a collection of named
opening variations to be used by GambitVB.
The Move Engine created the program classes Board, Piece, Move, and
MoveList, plus the classes King, Queen, Rook, Bishop, Knight
and Pawn derived from class Piece. Together, those classes knew the rules of chess; that is, the
engine was capable to deliver a legal move list for a legal chessboard
position. The algorithm for move generation was based on calculation: board
squares are numbered and the square number after a single step of a piece from
any place is calculated by (square number + direction). The direction is
presented by a fixed number for each of the eight directions east, east-south,
south, and so on.
The Search Engine was based on the αβ pruning algorithm,
explained in GambitVB The Book (and in
Alpha-beta pruning - the free encyclopedia
) and was programmed with the classes TreeSearcher, PlyNode and
TreeNode. The TreeSearcher drove the algorithm and created a collection of PlyNodes that
delivered search-information for a single variation of moves in a volatile
move tree. (Volatile, because only one variation at the time was visible in the PlyNode
collection.) Because GambitVB should play with a chess clock, the TreeSearcher
used the iterative αβ pruning algorithm: first a move tree of one move
deep is examined, then two moves deep, and so on, until a time
control signal is given. The other side of the iterative approach is that the
same information is regenerated and reexamined over and over again. To soften
that pain, a subset of the complete move tree was built with TreeNode objects.
GambitVB’s Graphical User Interface is a Windows Form Application, which
delivers the central classes FormSetup, FormBoard, FormClock, and
FormGame.
Program module GambitGui created and controlled those forms and called the move engine
and search engine when needed.
Writing a complete chess program is complex, needs a lot of code, but is
well defined, and requires limited programmer experience. However, writing a
better complete chess program, better than a previous version, is a race against
the chess clock. And that requires at lot of research and programmer experience.
How faster essential parts of the program, how
deeper the program can look within the time constraints. GambitVB’s time
management was driven by the forms Setup and Clock and controlled by the
TreeSearcher. Optimization for version 1.0 was done for 40
moves in 80 minutes.
With each new version of GambitVB:
- Code became faster for a better chess player experience.
- Code was streamlined for a better programmer experience.
- Old bugs were removed and, as always, new mistakes were implemented.
- GambitVB The Book was updated and improved.
|
For the second version, the author decided to reprogram the move and search
engines with the program language C/C++. The C language gives
the programmer more control over how the compiler translates the code to more
efficient machine instructions, which helps in the race against the chess clock sometimes.
The C++ language is an extension of the compact C language and helps the
programmer to write good structured code and helps him to avoid common
programmer errors.
Deliberately, the author chose the Microsoft implementation of ISO/ANSI C++ ,
rather than the .NET language C# or the .NET implementation of C++. The reason
was that those two .NET languages implement managed code, which does not give the
programmer full control over dynamic (free to use by the program) computer
memory. In GambitVB v1.0, that was seen as a bottleneck, in particular for
GambitVB’s TreeNode approach.
GambitVB’s defines a class named TreeNode to create a move tree structure in
memory, which offers fast access to valuable move tree search information, what
is missing in the standard α,β pruning approach. This
can grow up to millions of TreeNodes; all linked in a tree structure, what is
still a fraction of the total move tree, but is better than nothing. With
TreeNodes could also easily be built a more serious implementation of “thinking
in the opponent’s time”; the TreeSearcher continued working on the move tree
while the chess player considered his own move.
For version 2.0, the Graphical User Interface was still programmed with
Visual Basic .NET, as in all following versions of GambitVB. The developer tool
was Visual Studio 2008 this time. Optimization was done with default time
control limits set to 40 moves in 40 minutes, as in all following versions of
GambitVB.
|
Version 2.1 was a maintenance update of version 2.0
|
This version delivered two end-user installation files, one for 32-bits
computer and one for 64-bits computers. The source code was still written as a
single Visual Studio solution, but now with Visual Studio 2010.
|
For GambitVB 3.1, the strategic chess approach was redesigned. GambitVB uses so-called Score objects to compare board positions as better, equal, or worse.
The score object consists of two integral numbers, one
to valuate the material on the board, the other (named
strategy) to valuate the strength of the position.
The material valuation simply
counts the pieces still on the board. The unit is a pawn; bishop and knight
are worth three pawns, a rook five pawns, a queen nine pawns. Black pieces are
summed up as negative. A material advantage always gets
precedence over a strategy advantage.
The strategy valuation is not so straightforward as the material
evaluation, because it has to look for factors like the strength of the pawn
structure, development of pieces, king's safety, and etcetera. For version 3.1,
the number of items to look at was reduced for more efficiency and a better
chess-player experience. Also the design of the game phases (opening,
middlegame, and end game) were reconsidered and extended and will certainly be
revisited in later versions of GambitVB.
|