MS PROJECT (FALL 2006)

Ax Chess, and efficient representation of Chess targeted for a chess AI
program and a mobile device

Submitted by Azhar Ali

Project Advisor: Dr. Mohammad Zubair

ABSTRACT

	   This project, Ax Chess, is a two player chess engine/game. Most of
the features of

	   chess, such as valid moves, checkmate, stalemate, threefold
repetition, fifty move

	   rule, etc., are implemented. This project exposes a chess api that
can be integrated

	   by a gui chess interface, a mobile chess interface and/or an
artificial chess engine.

	   Design and Efficiency aspects are be studied through out the
project. And a best

	   design which would utilize memory and processor's speed efficiently
is produced;

	   suitable to low-memory devices like Series 60 Symbian Mobile Phones.

Contents

Introduction

Motivation

Technologies/Tools Used

Features of Ax Chess

Approach towards Solution

5.1 Object Oriented Design

5.2 Compile-time Programming

Symbian

Memory Management

Screenshots (Implementation's output)

Submitted Code & Installation instructions

Conclusion

1. Introduction

This project essentially consists of two phases.

Phase I: This phase solely concentrates on the implementation of Ax
Chess. 

Throughout the course of this project, I constantly tried to refine the
code to incorporate

"compile time programming" techniques, which made the code elegant,
succinct and highly

maintainable; and in turn helped the compiler to generate efficient
machine code. I had also focused

on using different programming paradigms, particularly Generic
Programming Paradigm (using

parametric polymorphism, which compared to subtype polymorphism is very
efficient), Functional

Paradigm (through which, we could avoid loops with tighter code
generation), Object Oriented

Paradigm, Procedural Paradigm etc; and evaluated the best one(s) for my
project from the perspective of both an efficient implementation for a
chess AI and also low-memory devices.

Phase II: The project code for PC would also be ported to Symbian OS,
using Symbian C++, which is

a much restricted version of Standard C++. Because of the inherent
constrained environment of a

mobile phone (when compared to PC, of course), unlike Standard C++,
Symbian C++ has a completely

different way of managing memory, exception handling, etc. The Symbian
C++ port is done considering all these aspects. And another impediment
for the port is the lack of the Standard Template

Library and the Boost Library for the Symbian environment. I had written
handcrafted versions for some of those library features.

2. Motivation

2.1 Need for an Efficient Chess Representation

To understand the need for an efficient ``chess representation'' like Ax
Chess, lets consider the

following example of how a basic chess Artificial Intelligence (AI)
program works:

The following figure (Figure 1) shows the tree of board positions
generated by a minimax algorithm after playing one move by both sides:

As we can see from the Figure 1, when the game of chess begins, white
has a choice of 20 moves. Followed by a white's move, black has 20 moves
in reply. Thus 400 different positions arise after one move by both
sides. This number grows to 20,000 after two moves and astronomically
later.

Techniques like alpha-beta search, killer heuristics, etc., are employed
to prune such trees.The way a chess AI program works is by searching the
above mentioned tree to a certain depth for both sides, and deeper along
highly tactical lines. 

It is to be noted that the chess AI consults the ``chess
representation'' at every node of the moves tree, to

get the result of the move such as checkmate, stalemate, etc. The chess
AI program uses a depth first search to traverse the above tree, so it
backtracks a lot and needs the support of undo operations from the
``chess representation''. The undo (and also redo) mechanism and the
different chess algorithms are important operations, because their
implementation's efficiency multiplies by a large factor (actually by
the number of move nodes in a chess tree), when used by chess AI.

Currently, the strongest chess playing software ``Deep Fritz 10'' can
see 18-ply (i.e., 9 moves on both sides) deep. This means that the chess
representation's functionality would be executed millions of times.

	Figure 1: Chess AI Tree generated by minimax algorithm after one move
by both sides

2.2 Why yet another one?

There are a lot of excellent chess playing softwares like Fritz,
Extreme, Crafty, etc for PC and Chess Tiger, etc., for Smart Phones. A
lot of effort is going on to improve these softwares. To get into such
development stream one needs experience like programming a simple chess
AI and understanding the real efficiency concerns which are involved in
the chess AI computations. The aim of this project is to get such
experience.

3. Technologies/Tools used

The following are the list of technologies and tools used

C++, STL, BOOST, Symbian C++

emacs, g++, gdb, make, cppunit, gprof

Symbian 8.0a SDK, Metrowerks CodeWarrior, Microsoft Visual Studio 2003

I choose C++ as my programming language, because of its flexibility. It
gives me complete control over the system, and allows me to think in
more than one paradigms

Using STL and BOOST, I got the following benefits

more efficient

better portability

concise code

better thinking process because of high level constructs

automatic memory management without sacrificing efficiency

support for custom memory allocators

etc

I used Gentoo 2.6 as my development platform, and tested it Ubuntu 6.10
and Windows XP also.

There were no portability problems.

4. Features of Ax Chess

The following are the features provided by Ax Chess:

Valid Moves for all Pieces:

	The movement algorithms for all pieces are take care of, and all things
related to them like 	enpassant, castling, pawn promotion.

Check

	A player's king is under threat.

Checkmate

	A player's king is under threat and he cannot escape that situation.

Stalemate

	A players's king is not under threat, but he has no legal moves to
make.

Threefold-repetition

	If the same board position occurs for three consecutive moves, then the
player could claim a 	draw. Note that the same board position need not
occur in consecutive moves. For ex: if certain 	pattern of moves are
repeated such that the board position is repeated thrice, then the
player 	could claim a draw.

 

50 Move Rule

	If no piece has been captured in 50 consecutive moves, then the player
can claim a draw.

Minimal Draw Algorithm

	If both sides have minimal pieces with which either cannot win, an
algorithm detects this and 	reports a draw.

Undo & Redo

	The Undo and Redo algorithms are exposed in a simple manner, so the
user of this project can 	request undo and redo of any number of moves
(if any).

Chess API

	The above features and some others needed by the chess AI are exposed
as an API. The API is 	given as follows:

	enum MoveResult { INVALIDMOVE, VALIDMOVE, CHECK, CHECKMATE, 

				  STALEMATE, DRAW, THREEFOLDREPETITION,

				  FIFTYMOVERULE };

	// string format: d2d4, e7e5, b1c3, etc.,

	MoveResult move(const string&);

	// pos (0, 0) & (0, 7) => black rook, (7, 0) & (7, 7) => white rook

	MoveResult move(const Move&);

	bool whiteTurn();

	const PieceID* chessBoardIterator();

	void undo(size_t nmoves = 1);

	void redo(size_t nmoves = 1);

	void pawnPromoter(PieceID (*)(PieceID));

	void recordPossibleMoves(const Position&, vector<Position>&);

	void generate_moves(vector<Move>&);

5. Approach towards Solution

5.1 Object-Oriented Design

My initial approach towards this project was an Object-Oriented
Solution. The following diagram shows part of my initial design related
to the chessmen.

		Figure 2: Part of Object Oriented Design for chessmen

I have found Object Oriented Design such as the one above constraining
to my particular project, because of the following reasons:

1)  Cost of Dynamic binding: 

I have a detailed discussion on the cost of dynamic binding in the
section ``compile-time programming''.

2) Object Model Inconsistency

 In the real-world at any time I have at most 32 pieces on the chess
board. That means even in situations like pawn promotion, a pawn is
promoted to a queen, rook, bishop or knight i.e., a Pawn object should
get converted to a Queen, etc. This is not directly possible in a
statically programming language like C++. In dynamically typed
languages, say for example Python, I could have changed the type of an
object using something like this ``pawnObject.class =  class(Queen)'',
and the pawn object starts behaving as a Queen object. To get this
support in C++, I should use some extra levels of indirection through
which I could write several solutions easily. But this approach is out
of question because I try to minimize extra run-time indirections.

Upon trying this Object Oriented solution further when implementing
undo, redo operations by using design patterns like ``memento'', I found
that a purist object-oriented approach was though giving elegant
solutions had some extra indirections, because of which I had written
some work-around solutions in non-object oriented way. This approach I
had pushed further and I had got a solution now which is a mixture of
generic, functional, procedural and object oriented paradigms.

5. 2 Compile-time Programming:

Lets see an situation in my project, in which I arrived at a good
solution using Compile-time programming. The example is as follows:

The following function is executed by a class say ``GameManager''
whenever a user or a chess AI program makes a move.

	bool moveValid(const Position& from, const Position& to);

As the declaration says, the return value is true if the move made is
valid; false otherwise.

An efficient implementation of the above function is as follows:

Solution 1:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    if (id == WROOK || id == BROOK)

	        return rookMoveValid(from, to, board);

    	    else if (id == WKNIGHT || id == BKNIGHT)

          	   return knightMoveValid(from, to, board);

    	    else if (id == WBISHOP || id == BBISHOP)

              return bishopMoveValid(from, to, board);

    	    else if (id == WQUEEN || id == BQUEEN)

		   return queenMoveValid(from, to, board);

    	    else if (id == WKING || id == BKING)

   		   return kingMoveValid(from, to, board);

    	    else if (id == WPAWN || id == BPAWN)

		   return pawnMoveValid(from, to, board);

    	    return false;

	}

The above solution is an efficient one, but it is a bad practice to
implement this way, because of the following reasons:

I need to move a piece from one position to another in a lot of
functions that means I have to duplicate the above code at many places.
We all know that code duplication should be avoided, which helps in
easier maintainability of the code.

Large if-else blocks also makes it difficult to write reusable code. For
example, ``Chinese Chess'' has one more piece ``Cannon'' in addition to
the above pieces (the names of the chessmen are different than standard
chess names). If I want to resuse my chess project to

design ``Chinese Chess'' then I got to add another ``if condition'' as
in the above code, at all

the places that has such functionality.

Solution 2: Object Oriented Solution

Here I give a solution using Object Oriented Paradigm to avoid the above
mentioned two problems.

The following is a basic Object Oriented design for the chessmen in my
project.

	class Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&) = 0;

    	    virtual void move(const Position&, Board&);

	    // other member functions and data removed for clarity.

     };

The above ``Piece''' base class specifies a contract that should be
implemented by all its derived classes i.e., all the concrete chessmen.

The concrete classes are as follows:

	class Rook : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

	class Knight : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

Similarly Bishop, Queen, King and Pawn classes.

Now the code for the ``moveValid'' function would be as follows:

	bool Board::moveValid(const Position& from, const Position& to) {

    	    Piece *p = board.piece(from);

    	    return p && p->moveValid(to, board);

   	}

The above one is an elegant solution. It is as simple as saying in plain
english, ``get a piece from a position, and ask it to move to another
posiion''.

Unlike in Solution 1, here the board object is not concerned which piece
its going to move. It is guaranteed that whatever the Piece would be,
its going to support the ``moveValid'' function. And 

through dynamic binding the big ``if-else'' block in Solution 1 is
translated into simple code.

But this clarity comes at a cost in Object Oriented world. To understand
the cost of dynamic binding lets see the object representation for a
concrete piece like ``Rook''. The layout in memory for an object of
class ``Rook'' would be as follows:

			   Figure 3: A Rook Object layout

Any classes that has virtual functions would have a virtual table (per
class) that contains the RTTI (runtime type information) and the virtual
functions. Every object of such class has a ``vptr'' (virtual table
pointer) member pointer pointing to the vtable (virtual table).

The line ``p->moveValid(to, board)'' is translated into the following
assembly code by the compiler.

	; Note: function_offset and vptr_offset known at compile time

	load [object_address + vptr_offset], reg1

	load [reg1 + function_offset], reg2

	call reg2

As seen in the above assembly code, dynamic binding does two
dereferences (one for obtaining the vtable address, and another to
obtain the appropriate function; ``moveValid'' in this case) then the
actual function call. The above code is resuable too, say if I added
another piece ``Cannon'' for chines chess, then I need to write another
class ``Cannon'' which would derive from ``Piece'', and no changes are
required for the ``moveValid'' function.

One thing to be noticed in solution 1 is that: on an average six if
conditions would be executed  before the appropriate ``xxMoveValid''
function call. But a clever compiler in the case of Solution 1 could
inline all these ``xxMoveValid'' functions, there by avoiding the
function call itself. I agree that the C++ compiler cannot inline
functions that are not simple, however, it is possible to write the code
using techniques like tighter loops, functors (functions as values), etc
which are unrolled by the compiler, and

could be inlined.

Where as in the case of Solution 2, due to dynamic binding it is
impossible to inline the functions.

Hence, even that the Solution 2 is elegant it comes with an cost (2
dereferences and actual function call), which is undesirable in this
project where I am trying to increase the execution speed of the overall
application.

Solution 3: A better solution (one less dereference):

The following is the solution I arrived at after studying the dynamic
binding (especially how virtuals work through vtables). Here I kind of
create manual vtable which is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool (*moveValid_[12])(const Position&, const Position&, const Board&) 
	=

    			{ 

        			pawnMoveValid, knightMoveValid, bishopMoveValid,   

        			rookMoveValid, queenMoveValid, kingMoveValid, 

        			pawnMoveValid, knightMoveValid, bishopMoveValid, 

        			rookMoveValid, queenMoveValid, kingMoveValid

    			};

Here ``moveValid_'' is a  array [12] of function pointers. Now the
moveValid function could be written as

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && (*moveValid_[id])(from, to, board);

	}

As can be seen from the above code, now we have one dereference to the
actual function then the actual function call.

Solution 4: Compile-time Programming

This is the final solution I created which has the same benefits as
Solution 1, and none of its draw backs. The Solution is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	typedef boost::tuple

    		<		

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

			RookMoveValid, QueenMoveValid, KingMoveValid,

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

  			RookMoveValid, QueenMoveValid, KingMoveValid

    		> TUPLE;

	TUPLE moveValidFunctors;

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && call(moveValidFunctors, id, from, to,
board);

	}

	

The above ``moveValid'' is as elegant as the Solution 2 version and as
efficient as Solution 1.

The compiler translates the line ``call(moveValidFunctors, id, from, to,
board)'' to the following big ``if-else'' block.

	return id == 11 ? KingMoveValid(from, to, board)

		: (id == 10 ? QueenMoveValid(from, to, board)

		   ... 

		: (id ==  0 ? PawnMoveValid(from, to, board)))...);

I have written this ``call'' construct using Templates and partial
Template Specialization. Note that this conversion would take at compile
time, and hence once the compiler is done, the ``call'' construct
vanishes replacing itself by the big ``if-else'' block

6. Symbian

The following are a few concepts which I thought are worth mentioning.
These topics would be explained in detail in Symbian OS or Symbian C++
books. 

Standard C++ didn't had exceptions when Symbian OS was designed
initially. After exceptions were added to standard C++ it was found that
the language techniques used to support exceptional handling 

adds a good amount of overheads to the compiled code and also some
run-time overheads, regardless of whether exceptions were actually
thrown or not. So developers of Symbian OS didn't find exception
handling suitable to Symbian C++ because they wanted the Symbian OS and
the client code to be compact. Since Symbian C++ has a different way of
dealing with memory, its lays certain restrictions on the types that we
can create. These are called T, C and R classes. T classes are ones like
the primitive ones which do not need explicit destructors, and C classes
are the ones in which the virtuals are involved, and R classes represent
the resource classes.

Leaves

A simple, good and lightweight exception handling solution called
``leaves'' was developed for Symbian OS. A leave is used to propagate an
error which occurs because of exceptional conditions (such as being out
of memory or disk space) to higher-level code which can handle it. A
Symbian OS leave is equivalent to a C++ throw and a TRAP harness is used
to catch the leave. In fact, a TRAP harness is effectively a combination
of try and catch.

TRAP and leave are analogous to the setjmp() and longjmp() methods,
respectively - setjmp() tores information about the location to be
``jumped to'' in a jump buffer, which is used by ``longjmp()'' to direct
the code to jump to that point.

Cleanup Stack

The stack memory is freed as the stack unwinds, but otherwise the stack
frame is abandoned and no object destructors are called (which is unlike
a standard C++ exception). This means the destructors of any local
variables or arguments passed by value, or objects created as member
variables of either of these, will not be called. Some objects are
``leave-safe'' - they do not need destructors and contain only data
which can be destroyed as stack memory is freed by the leave. This data
may consist of the basic, built-in types or other objects which contain
such types. In Symbian OS these are called T classes, the characteristic
of which is that they may safely be created on the stack in functions
where code may leave. If a local variable is a pointer to an object on
the heap, when a leave occurs the pointer is destroyed without freeing
that heap memory, which becomes unrecoverable, causing a memory leak.
The memory is said to be orphaned. This means that C classes objects,
which are always created on the heap are not leave safe. R class objects
are generally not leave-safe either, since the resources they own must
be freed in the event of a leave (through a call to the appropriate
Close() or Release() type function). If this call cannot made by an
object accessible after the leave, the resource is orphaned.

Various techniques are used to effectively do the cleanup activities of
resources through Cleanup Stack.

I have read and understood the above concepts and several others related
to Symbian, such as

descriptors, dynamic buffers, event-driven multitasking using Active
Objects, Symbian OS Threads and Processes, graphics for display and
interaction etc.

I have resolved several issues while I was doing the port of Ax Chess to
Symbian OS. Some of issues were lack of STL and BOOST because of which I
had to write the appropriate constructs, and since Symbian C++ compiler
is not so sophisticated as standard C++ compilers like g++, Comeau C++,
MS Visual Studio C++  compiler,etc., I had written work-arounds for the
compile-time programming techniques I have used.

7. Memory Management

This is the area that I didn't think when I submitted the this project's
proposal. But during the course of this project I found that custom
memory management would improve the performance. The following is a
discussion on why custom memory management would be helpful.

Datastructures provided by STL are used, which currently manage memory
automatically.

Internally they call new/delete for memory allocation and deallocation.
The above mentioned dynamic memory allocators/dealloactors matter when
efficieny is  concerned. For example: Each "new" operation executes a OS
call to get memory allocated from free store, and each "delete" involves
in returning the allocated memory to the free  pool. These are costly
operations. And using "new/delete"s frequently in a chess AI program is
going to cost too much.

Created a Garbage Collector, which uses Mark-Sweep (with Compaction)
Algorithm. This project is made thread-safe using POSIX Threads, Mutex,
Condition variables etc. The Garbage Collector exposes a pointer
abstraction gc_ptr<T>, which has allocation speed faster than the
standard new operator, and can be approximated to the speed of the
allocation on stack space. However,

sweep does take time to reclaim storage space occupied by out-of-scope
pointers, and also to compact the active memory under use. Conversions
between gc_ptr of base and derived types are taken care at compile-time,
which ensures compile-time type safety; avoiding any run-time safety
overhead.

By default the Garbage Collector can be used in a multi-threaded
environment, but it can be configured at compile-time as a
single-threaded one, thus removing multithread specific overhead,
unnecessary in a single-thread environment. This type of Garbage
Collector can be used in projects where heap-based

memory allocations should be very fast. For example, a chess AI program
can use this garbage collector, to build large trees (of search-worthy
moves and search the best move) during the computers turn of play, and
can reclaim the storage when it is idle i.e., during the opponents turn.
This method drastically speeds-up performance when compared to the
standard new operator that itself spends a lot of time during
allocation.

There are other garbage collection algorithms available like reference
counting, mark sweep, copying, etc. I found that the mark-sweep one
suits best to the chess AI's situtation. Because all I do care is that
the memory allocations should be very efficient, and even though the
sweep is complex and inefficient, that doesn't matter because it is
supposed to be called in the idle phase of the chess AI program.

Currently this GC isn't integrated with "Ax Chess" as I haven't finished
testing the GC.

8. Screenshots

The following are a few screenshots showing some features of the
implementation.

 

		Figure 4: Ax Chess ported to Symbian OS (S60 devices), running on
emulator

 

	

				   Figure 5: A checkmate condition.

					Figure 6: A stalemate condition

The following is a screen-shot of my character user interface that uses
the chess API; showing the steps of a simple checkmate:

Note: White pieces are represented using lower-case letters and black
pieces are in upper case letters, as can be seen using the ``draw''
command.

		

				Figure 7: CUI using the chess API

9. Submitted Code & Installation instructions

For this project, you need to have a good C++ compiler. I would
recommend g++, comeau C++ compiler or MS Visual Studio 2005 C++
compiler.

And you need to have the BOOST library installed on your system.

For installing boost, check the instructions from the boost website 

  HYPERLINK "http://www.boost.org/" http://www.boost.org/ 

or for gentoo and debian based systems, here is a simple procedure

  HYPERLINK
"http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-d
ebianubuntu/"
http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-de
bianubuntu/ 

I have hosted my project code at savannah website. The url is

  HYPERLINK "http://savannah.nongnu.org/projects/ax-chess/"
http://savannah.nongnu.org/projects/ax-chess/ 

To download the project code, use the following command:

cvs -z3 -d:pserver:anonymous@cvs.savannah.nongnu.org:/sources/ax-chess
co ax-chess

The above command would create a directory ``ax-chess'' in your present
working directory.

Type ``make'' to compile the project. And  use ``./cuigamemanager'' at
the shell prompt to test 

Ax Chess.

I am also submitting the code as a tar.gz file to the ODU CS department
as part of the MS Project requirements. The zipped file would contain
both Ax Chess project and the port of Ax Chess for Symbian OS.

10. Conclusion

This project had been a great learning experience; I am a better
programmer now. There is plenty left to do. I believe that a fresh
review of my complete code would give me some more ideas to improve it.
The following are some the concepts that I have learned.

1) Several concepts of C++. For example, few would be Internal
representation of Objects, Templates, 2) Compile-time computations,
Policy based design.

3) Idea about different programming paradigms and efficiency
considerations.

4) STL and BOOST

5) Memory Management and Garbage Collection.

6) Symbian OS Internals and Symbian C++

7) Various Tools like emacs, g++, gdb, make, cppunit, gprof, Metrowerks
CodeWarrior, etc

MS PROJECT (FALL 2006)

Ax Chess, and efficient representation of Chess targeted for a chess AI
program and a mobile device

Submitted by Azhar Ali

Project Advisor: Dr. Mohammad Zubair

ABSTRACT

	   This project, Ax Chess, is a two player chess engine/game. Most of
the features of

	   chess, such as valid moves, checkmate, stalemate, threefold
repetition, fifty move

	   rule, etc., are implemented. This project exposes a chess api that
can be integrated

	   by a gui chess interface, a mobile chess interface and/or an
artificial chess engine.

	   Design and Efficiency aspects are be studied through out the
project. And a best

	   design which would utilize memory and processor's speed efficiently
is produced;

	   suitable to low-memory devices like Series 60 Symbian Mobile Phones.

Contents

Introduction

Motivation

Technologies/Tools Used

Features of Ax Chess

Approach towards Solution

5.1 Object Oriented Design

5.2 Compile-time Programming

Symbian

Memory Management

Screenshots (Implementation's output)

Submitted Code & Installation instructions

Conclusion

1. Introduction

This project essentially consists of two phases.

Phase I: This phase solely concentrates on the implementation of Ax
Chess. 

Throughout the course of this project, I constantly tried to refine the
code to incorporate

"compile time programming" techniques, which made the code elegant,
succinct and highly

maintainable; and in turn helped the compiler to generate efficient
machine code. I had also focused

on using different programming paradigms, particularly Generic
Programming Paradigm (using

parametric polymorphism, which compared to subtype polymorphism is very
efficient), Functional

Paradigm (through which, we could avoid loops with tighter code
generation), Object Oriented

Paradigm, Procedural Paradigm etc; and evaluated the best one(s) for my
project from the perspective of both an efficient implementation for a
chess AI and also low-memory devices.

Phase II: The project code for PC would also be ported to Symbian OS,
using Symbian C++, which is

a much restricted version of Standard C++. Because of the inherent
constrained environment of a

mobile phone (when compared to PC, of course), unlike Standard C++,
Symbian C++ has a completely

different way of managing memory, exception handling, etc. The Symbian
C++ port is done considering all these aspects. And another impediment
for the port is the lack of the Standard Template

Library and the Boost Library for the Symbian environment. I had written
handcrafted versions for some of those library features.

2. Motivation

2.1 Need for an Efficient Chess Representation

To understand the need for an efficient ``chess representation'' like Ax
Chess, lets consider the

following example of how a basic chess Artificial Intelligence (AI)
program works:

The following figure (Figure 1) shows the tree of board positions
generated by a minimax algorithm after playing one move by both sides:

As we can see from the Figure 1, when the game of chess begins, white
has a choice of 20 moves. Followed by a white's move, black has 20 moves
in reply. Thus 400 different positions arise after one move by both
sides. This number grows to 20,000 after two moves and astronomically
later.

Techniques like alpha-beta search, killer heuristics, etc., are employed
to prune such trees.The way a chess AI program works is by searching the
above mentioned tree to a certain depth for both sides, and deeper along
highly tactical lines. 

It is to be noted that the chess AI consults the ``chess
representation'' at every node of the moves tree, to

get the result of the move such as checkmate, stalemate, etc. The chess
AI program uses a depth first search to traverse the above tree, so it
backtracks a lot and needs the support of undo operations from the
``chess representation''. The undo (and also redo) mechanism and the
different chess algorithms are important operations, because their
implementation's efficiency multiplies by a large factor (actually by
the number of move nodes in a chess tree), when used by chess AI.

Currently, the strongest chess playing software ``Deep Fritz 10'' can
see 18-ply (i.e., 9 moves on both sides) deep. This means that the chess
representation's functionality would be executed millions of times.

	Figure 1: Chess AI Tree generated by minimax algorithm after one move
by both sides

2.2 Why yet another one?

There are a lot of excellent chess playing softwares like Fritz,
Extreme, Crafty, etc for PC and Chess Tiger, etc., for Smart Phones. A
lot of effort is going on to improve these softwares. To get into such
development stream one needs experience like programming a simple chess
AI and understanding the real efficiency concerns which are involved in
the chess AI computations. The aim of this project is to get such
experience.

3. Technologies/Tools used

The following are the list of technologies and tools used

C++, STL, BOOST, Symbian C++

emacs, g++, gdb, make, cppunit, gprof

Symbian 8.0a SDK, Metrowerks CodeWarrior, Microsoft Visual Studio 2003

I choose C++ as my programming language, because of its flexibility. It
gives me complete control over the system, and allows me to think in
more than one paradigms

Using STL and BOOST, I got the following benefits

more efficient

better portability

concise code

better thinking process because of high level constructs

automatic memory management without sacrificing efficiency

support for custom memory allocators

etc

I used Gentoo 2.6 as my development platform, and tested it Ubuntu 6.10
and Windows XP also.

There were no portability problems.

4. Features of Ax Chess

The following are the features provided by Ax Chess:

Valid Moves for all Pieces:

	The movement algorithms for all pieces are take care of, and all things
related to them like 	enpassant, castling, pawn promotion.

Check

	A player's king is under threat.

Checkmate

	A player's king is under threat and he cannot escape that situation.

Stalemate

	A players's king is not under threat, but he has no legal moves to
make.

Threefold-repetition

	If the same board position occurs for three consecutive moves, then the
player could claim a 	draw. Note that the same board position need not
occur in consecutive moves. For ex: if certain 	pattern of moves are
repeated such that the board position is repeated thrice, then the
player 	could claim a draw.

 

50 Move Rule

	If no piece has been captured in 50 consecutive moves, then the player
can claim a draw.

Minimal Draw Algorithm

	If both sides have minimal pieces with which either cannot win, an
algorithm detects this and 	reports a draw.

Undo & Redo

	The Undo and Redo algorithms are exposed in a simple manner, so the
user of this project can 	request undo and redo of any number of moves
(if any).

Chess API

	The above features and some others needed by the chess AI are exposed
as an API. The API is 	given as follows:

	enum MoveResult { INVALIDMOVE, VALIDMOVE, CHECK, CHECKMATE, 

				  STALEMATE, DRAW, THREEFOLDREPETITION,

				  FIFTYMOVERULE };

	// string format: d2d4, e7e5, b1c3, etc.,

	MoveResult move(const string&);

	// pos (0, 0) & (0, 7) => black rook, (7, 0) & (7, 7) => white rook

	MoveResult move(const Move&);

	bool whiteTurn();

	const PieceID* chessBoardIterator();

	void undo(size_t nmoves = 1);

	void redo(size_t nmoves = 1);

	void pawnPromoter(PieceID (*)(PieceID));

	void recordPossibleMoves(const Position&, vector<Position>&);

	void generate_moves(vector<Move>&);

5. Approach towards Solution

5.1 Object-Oriented Design

My initial approach towards this project was an Object-Oriented
Solution. The following diagram shows part of my initial design related
to the chessmen.

		Figure 2: Part of Object Oriented Design for chessmen

I have found Object Oriented Design such as the one above constraining
to my particular project, because of the following reasons:

1)  Cost of Dynamic binding: 

I have a detailed discussion on the cost of dynamic binding in the
section ``compile-time programming''.

2) Object Model Inconsistency

 In the real-world at any time I have at most 32 pieces on the chess
board. That means even in situations like pawn promotion, a pawn is
promoted to a queen, rook, bishop or knight i.e., a Pawn object should
get converted to a Queen, etc. This is not directly possible in a
statically programming language like C++. In dynamically typed
languages, say for example Python, I could have changed the type of an
object using something like this ``pawnObject.class =  class(Queen)'',
and the pawn object starts behaving as a Queen object. To get this
support in C++, I should use some extra levels of indirection through
which I could write several solutions easily. But this approach is out
of question because I try to minimize extra run-time indirections.

Upon trying this Object Oriented solution further when implementing
undo, redo operations by using design patterns like ``memento'', I found
that a purist object-oriented approach was though giving elegant
solutions had some extra indirections, because of which I had written
some work-around solutions in non-object oriented way. This approach I
had pushed further and I had got a solution now which is a mixture of
generic, functional, procedural and object oriented paradigms.

5. 2 Compile-time Programming:

Lets see an situation in my project, in which I arrived at a good
solution using Compile-time programming. The example is as follows:

The following function is executed by a class say ``GameManager''
whenever a user or a chess AI program makes a move.

	bool moveValid(const Position& from, const Position& to);

As the declaration says, the return value is true if the move made is
valid; false otherwise.

An efficient implementation of the above function is as follows:

Solution 1:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    if (id == WROOK || id == BROOK)

	        return rookMoveValid(from, to, board);

    	    else if (id == WKNIGHT || id == BKNIGHT)

          	   return knightMoveValid(from, to, board);

    	    else if (id == WBISHOP || id == BBISHOP)

              return bishopMoveValid(from, to, board);

    	    else if (id == WQUEEN || id == BQUEEN)

		   return queenMoveValid(from, to, board);

    	    else if (id == WKING || id == BKING)

   		   return kingMoveValid(from, to, board);

    	    else if (id == WPAWN || id == BPAWN)

		   return pawnMoveValid(from, to, board);

    	    return false;

	}

The above solution is an efficient one, but it is a bad practice to
implement this way, because of the following reasons:

I need to move a piece from one position to another in a lot of
functions that means I have to duplicate the above code at many places.
We all know that code duplication should be avoided, which helps in
easier maintainability of the code.

Large if-else blocks also makes it difficult to write reusable code. For
example, ``Chinese Chess'' has one more piece ``Cannon'' in addition to
the above pieces (the names of the chessmen are different than standard
chess names). If I want to resuse my chess project to

design ``Chinese Chess'' then I got to add another ``if condition'' as
in the above code, at all

the places that has such functionality.

Solution 2: Object Oriented Solution

Here I give a solution using Object Oriented Paradigm to avoid the above
mentioned two problems.

The following is a basic Object Oriented design for the chessmen in my
project.

	class Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&) = 0;

    	    virtual void move(const Position&, Board&);

	    // other member functions and data removed for clarity.

     };

The above ``Piece''' base class specifies a contract that should be
implemented by all its derived classes i.e., all the concrete chessmen.

The concrete classes are as follows:

	class Rook : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

	class Knight : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

Similarly Bishop, Queen, King and Pawn classes.

Now the code for the ``moveValid'' function would be as follows:

	bool Board::moveValid(const Position& from, const Position& to) {

    	    Piece *p = board.piece(from);

    	    return p && p->moveValid(to, board);

   	}

The above one is an elegant solution. It is as simple as saying in plain
english, ``get a piece from a position, and ask it to move to another
posiion''.

Unlike in Solution 1, here the board object is not concerned which piece
its going to move. It is guaranteed that whatever the Piece would be,
its going to support the ``moveValid'' function. And 

through dynamic binding the big ``if-else'' block in Solution 1 is
translated into simple code.

But this clarity comes at a cost in Object Oriented world. To understand
the cost of dynamic binding lets see the object representation for a
concrete piece like ``Rook''. The layout in memory for an object of
class ``Rook'' would be as follows:

			   Figure 3: A Rook Object layout

Any classes that has virtual functions would have a virtual table (per
class) that contains the RTTI (runtime type information) and the virtual
functions. Every object of such class has a ``vptr'' (virtual table
pointer) member pointer pointing to the vtable (virtual table).

The line ``p->moveValid(to, board)'' is translated into the following
assembly code by the compiler.

	; Note: function_offset and vptr_offset known at compile time

	load [object_address + vptr_offset], reg1

	load [reg1 + function_offset], reg2

	call reg2

As seen in the above assembly code, dynamic binding does two
dereferences (one for obtaining the vtable address, and another to
obtain the appropriate function; ``moveValid'' in this case) then the
actual function call. The above code is resuable too, say if I added
another piece ``Cannon'' for chines chess, then I need to write another
class ``Cannon'' which would derive from ``Piece'', and no changes are
required for the ``moveValid'' function.

One thing to be noticed in solution 1 is that: on an average six if
conditions would be executed  before the appropriate ``xxMoveValid''
function call. But a clever compiler in the case of Solution 1 could
inline all these ``xxMoveValid'' functions, there by avoiding the
function call itself. I agree that the C++ compiler cannot inline
functions that are not simple, however, it is possible to write the code
using techniques like tighter loops, functors (functions as values), etc
which are unrolled by the compiler, and

could be inlined.

Where as in the case of Solution 2, due to dynamic binding it is
impossible to inline the functions.

Hence, even that the Solution 2 is elegant it comes with an cost (2
dereferences and actual function call), which is undesirable in this
project where I am trying to increase the execution speed of the overall
application.

Solution 3: A better solution (one less dereference):

The following is the solution I arrived at after studying the dynamic
binding (especially how virtuals work through vtables). Here I kind of
create manual vtable which is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool (*moveValid_[12])(const Position&, const Position&, const Board&) 
	=

    			{ 

        			pawnMoveValid, knightMoveValid, bishopMoveValid,   

        			rookMoveValid, queenMoveValid, kingMoveValid, 

        			pawnMoveValid, knightMoveValid, bishopMoveValid, 

        			rookMoveValid, queenMoveValid, kingMoveValid

    			};

Here ``moveValid_'' is a  array [12] of function pointers. Now the
moveValid function could be written as

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && (*moveValid_[id])(from, to, board);

	}

As can be seen from the above code, now we have one dereference to the
actual function then the actual function call.

Solution 4: Compile-time Programming

This is the final solution I created which has the same benefits as
Solution 1, and none of its draw backs. The Solution is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	typedef boost::tuple

    		<		

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

			RookMoveValid, QueenMoveValid, KingMoveValid,

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

  			RookMoveValid, QueenMoveValid, KingMoveValid

    		> TUPLE;

	TUPLE moveValidFunctors;

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && call(moveValidFunctors, id, from, to,
board);

	}

	

The above ``moveValid'' is as elegant as the Solution 2 version and as
efficient as Solution 1.

The compiler translates the line ``call(moveValidFunctors, id, from, to,
board)'' to the following big ``if-else'' block.

	return id == 11 ? KingMoveValid(from, to, board)

		: (id == 10 ? QueenMoveValid(from, to, board)

		   ... 

		: (id ==  0 ? PawnMoveValid(from, to, board)))...);

I have written this ``call'' construct using Templates and partial
Template Specialization. Note that this conversion would take at compile
time, and hence once the compiler is done, the ``call'' construct
vanishes replacing itself by the big ``if-else'' block

6. Symbian

The following are a few concepts which I thought are worth mentioning.
These topics would be explained in detail in Symbian OS or Symbian C++
books. 

Standard C++ didn't had exceptions when Symbian OS was designed
initially. After exceptions were added to standard C++ it was found that
the language techniques used to support exceptional handling 

adds a good amount of overheads to the compiled code and also some
run-time overheads, regardless of whether exceptions were actually
thrown or not. So developers of Symbian OS didn't find exception
handling suitable to Symbian C++ because they wanted the Symbian OS and
the client code to be compact. Since Symbian C++ has a different way of
dealing with memory, its lays certain restrictions on the types that we
can create. These are called T, C and R classes. T classes are ones like
the primitive ones which do not need explicit destructors, and C classes
are the ones in which the virtuals are involved, and R classes represent
the resource classes.

Leaves

A simple, good and lightweight exception handling solution called
``leaves'' was developed for Symbian OS. A leave is used to propagate an
error which occurs because of exceptional conditions (such as being out
of memory or disk space) to higher-level code which can handle it. A
Symbian OS leave is equivalent to a C++ throw and a TRAP harness is used
to catch the leave. In fact, a TRAP harness is effectively a combination
of try and catch.

TRAP and leave are analogous to the setjmp() and longjmp() methods,
respectively - setjmp() tores information about the location to be
``jumped to'' in a jump buffer, which is used by ``longjmp()'' to direct
the code to jump to that point.

Cleanup Stack

The stack memory is freed as the stack unwinds, but otherwise the stack
frame is abandoned and no object destructors are called (which is unlike
a standard C++ exception). This means the destructors of any local
variables or arguments passed by value, or objects created as member
variables of either of these, will not be called. Some objects are
``leave-safe'' - they do not need destructors and contain only data
which can be destroyed as stack memory is freed by the leave. This data
may consist of the basic, built-in types or other objects which contain
such types. In Symbian OS these are called T classes, the characteristic
of which is that they may safely be created on the stack in functions
where code may leave. If a local variable is a pointer to an object on
the heap, when a leave occurs the pointer is destroyed without freeing
that heap memory, which becomes unrecoverable, causing a memory leak.
The memory is said to be orphaned. This means that C classes objects,
which are always created on the heap are not leave safe. R class objects
are generally not leave-safe either, since the resources they own must
be freed in the event of a leave (through a call to the appropriate
Close() or Release() type function). If this call cannot made by an
object accessible after the leave, the resource is orphaned.

Various techniques are used to effectively do the cleanup activities of
resources through Cleanup Stack.

I have read and understood the above concepts and several others related
to Symbian, such as

descriptors, dynamic buffers, event-driven multitasking using Active
Objects, Symbian OS Threads and Processes, graphics for display and
interaction etc.

I have resolved several issues while I was doing the port of Ax Chess to
Symbian OS. Some of issues were lack of STL and BOOST because of which I
had to write the appropriate constructs, and since Symbian C++ compiler
is not so sophisticated as standard C++ compilers like g++, Comeau C++,
MS Visual Studio C++  compiler,etc., I had written work-arounds for the
compile-time programming techniques I have used.

7. Memory Management

This is the area that I didn't think when I submitted the this project's
proposal. But during the course of this project I found that custom
memory management would improve the performance. The following is a
discussion on why custom memory management would be helpful.

Datastructures provided by STL are used, which currently manage memory
automatically.

Internally they call new/delete for memory allocation and deallocation.
The above mentioned dynamic memory allocators/dealloactors matter when
efficieny is  concerned. For example: Each "new" operation executes a OS
call to get memory allocated from free store, and each "delete" involves
in returning the allocated memory to the free  pool. These are costly
operations. And using "new/delete"s frequently in a chess AI program is
going to cost too much.

Created a Garbage Collector, which uses Mark-Sweep (with Compaction)
Algorithm. This project is made thread-safe using POSIX Threads, Mutex,
Condition variables etc. The Garbage Collector exposes a pointer
abstraction gc_ptr<T>, which has allocation speed faster than the
standard new operator, and can be approximated to the speed of the
allocation on stack space. However,

sweep does take time to reclaim storage space occupied by out-of-scope
pointers, and also to compact the active memory under use. Conversions
between gc_ptr of base and derived types are taken care at compile-time,
which ensures compile-time type safety; avoiding any run-time safety
overhead.

By default the Garbage Collector can be used in a multi-threaded
environment, but it can be configured at compile-time as a
single-threaded one, thus removing multithread specific overhead,
unnecessary in a single-thread environment. This type of Garbage
Collector can be used in projects where heap-based

memory allocations should be very fast. For example, a chess AI program
can use this garbage collector, to build large trees (of search-worthy
moves and search the best move) during the computers turn of play, and
can reclaim the storage when it is idle i.e., during the opponents turn.
This method drastically speeds-up performance when compared to the
standard new operator that itself spends a lot of time during
allocation.

There are other garbage collection algorithms available like reference
counting, mark sweep, copying, etc. I found that the mark-sweep one
suits best to the chess AI's situtation. Because all I do care is that
the memory allocations should be very efficient, and even though the
sweep is complex and inefficient, that doesn't matter because it is
supposed to be called in the idle phase of the chess AI program.

Currently this GC isn't integrated with "Ax Chess" as I haven't finished
testing the GC.

8. Screenshots

The following are a few screenshots showing some features of the
implementation.

 

		Figure 4: Ax Chess ported to Symbian OS (S60 devices), running on
emulator

 

	

				   Figure 5: A checkmate condition.

					Figure 6: A stalemate condition

The following is a screen-shot of my character user interface that uses
the chess API; showing the steps of a simple checkmate:

Note: White pieces are represented using lower-case letters and black
pieces are in upper case letters, as can be seen using the ``draw''
command.

		

				Figure 7: CUI using the chess API

9. Submitted Code & Installation instructions

For this project, you need to have a good C++ compiler. I would
recommend g++, comeau C++ compiler or MS Visual Studio 2005 C++
compiler.

And you need to have the BOOST library installed on your system.

For installing boost, check the instructions from the boost website 

  HYPERLINK "http://www.boost.org/" http://www.boost.org/ 

or for gentoo and debian based systems, here is a simple procedure

  HYPERLINK
"http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-d
ebianubuntu/"
http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-de
bianubuntu/ 

I have hosted my project code at savannah website. The url is

  HYPERLINK "http://savannah.nongnu.org/projects/ax-chess/"
http://savannah.nongnu.org/projects/ax-chess/ 

To download the project code, use the following command:

cvs -z3 -d:pserver:anonymous@cvs.savannah.nongnu.org:/sources/ax-chess
co ax-chess

The above command would create a directory ``ax-chess'' in your present
working directory.

Type ``make'' to compile the project. And  use ``./cuigamemanager'' at
the shell prompt to test 

Ax Chess.

I am also submitting the code as a tar.gz file to the ODU CS department
as part of the MS Project requirements. The zipped file would contain
both Ax Chess project and the port of Ax Chess for Symbian OS.

10. Conclusion

This project had been a great learning experience; I am a better
programmer now. There is plenty left to do. I believe that a fresh
review of my complete code would give me some more ideas to improve it.
The following are some the concepts that I have learned.

1) Several concepts of C++. For example, few would be Internal
representation of Objects, Templates, 2) Compile-time computations,
Policy based design.

3) Idea about different programming paradigms and efficiency
considerations.

4) STL and BOOST

5) Memory Management and Garbage Collection.

6) Symbian OS Internals and Symbian C++

7) Various Tools like emacs, g++, gdb, make, cppunit, gprof, Metrowerks
CodeWarrior, etc

MS PROJECT (FALL 2006)

Ax Chess, and efficient representation of Chess targeted for a chess AI
program and a mobile device

Submitted by Azhar Ali

Project Advisor: Dr. Mohammad Zubair

ABSTRACT

	   This project, Ax Chess, is a two player chess engine/game. Most of
the features of

	   chess, such as valid moves, checkmate, stalemate, threefold
repetition, fifty move

	   rule, etc., are implemented. This project exposes a chess api that
can be integrated

	   by a gui chess interface, a mobile chess interface and/or an
artificial chess engine.

	   Design and Efficiency aspects are be studied through out the
project. And a best

	   design which would utilize memory and processor's speed efficiently
is produced;

	   suitable to low-memory devices like Series 60 Symbian Mobile Phones.

Contents

Introduction

Motivation

Technologies/Tools Used

Features of Ax Chess

Approach towards Solution

5.1 Object Oriented Design

5.2 Compile-time Programming

Symbian

Memory Management

Screenshots (Implementation's output)

Submitted Code & Installation instructions

Conclusion

1. Introduction

This project essentially consists of two phases.

Phase I: This phase solely concentrates on the implementation of Ax
Chess. 

Throughout the course of this project, I constantly tried to refine the
code to incorporate

"compile time programming" techniques, which made the code elegant,
succinct and highly

maintainable; and in turn helped the compiler to generate efficient
machine code. I had also focused

on using different programming paradigms, particularly Generic
Programming Paradigm (using

parametric polymorphism, which compared to subtype polymorphism is very
efficient), Functional

Paradigm (through which, we could avoid loops with tighter code
generation), Object Oriented

Paradigm, Procedural Paradigm etc; and evaluated the best one(s) for my
project from the perspective of both an efficient implementation for a
chess AI and also low-memory devices.

Phase II: The project code for PC would also be ported to Symbian OS,
using Symbian C++, which is

a much restricted version of Standard C++. Because of the inherent
constrained environment of a

mobile phone (when compared to PC, of course), unlike Standard C++,
Symbian C++ has a completely

different way of managing memory, exception handling, etc. The Symbian
C++ port is done considering all these aspects. And another impediment
for the port is the lack of the Standard Template

Library and the Boost Library for the Symbian environment. I had written
handcrafted versions for some of those library features.

2. Motivation

2.1 Need for an Efficient Chess Representation

To understand the need for an efficient ``chess representation'' like Ax
Chess, lets consider the

following example of how a basic chess Artificial Intelligence (AI)
program works:

The following figure (Figure 1) shows the tree of board positions
generated by a minimax algorithm after playing one move by both sides:

As we can see from the Figure 1, when the game of chess begins, white
has a choice of 20 moves. Followed by a white's move, black has 20 moves
in reply. Thus 400 different positions arise after one move by both
sides. This number grows to 20,000 after two moves and astronomically
later.

Techniques like alpha-beta search, killer heuristics, etc., are employed
to prune such trees.The way a chess AI program works is by searching the
above mentioned tree to a certain depth for both sides, and deeper along
highly tactical lines. 

It is to be noted that the chess AI consults the ``chess
representation'' at every node of the moves tree, to

get the result of the move such as checkmate, stalemate, etc. The chess
AI program uses a depth first search to traverse the above tree, so it
backtracks a lot and needs the support of undo operations from the
``chess representation''. The undo (and also redo) mechanism and the
different chess algorithms are important operations, because their
implementation's efficiency multiplies by a large factor (actually by
the number of move nodes in a chess tree), when used by chess AI.

Currently, the strongest chess playing software ``Deep Fritz 10'' can
see 18-ply (i.e., 9 moves on both sides) deep. This means that the chess
representation's functionality would be executed millions of times.

	Figure 1: Chess AI Tree generated by minimax algorithm after one move
by both sides

2.2 Why yet another one?

There are a lot of excellent chess playing softwares like Fritz,
Extreme, Crafty, etc for PC and Chess Tiger, etc., for Smart Phones. A
lot of effort is going on to improve these softwares. To get into such
development stream one needs experience like programming a simple chess
AI and understanding the real efficiency concerns which are involved in
the chess AI computations. The aim of this project is to get such
experience.

3. Technologies/Tools used

The following are the list of technologies and tools used

C++, STL, BOOST, Symbian C++

emacs, g++, gdb, make, cppunit, gprof

Symbian 8.0a SDK, Metrowerks CodeWarrior, Microsoft Visual Studio 2003

I choose C++ as my programming language, because of its flexibility. It
gives me complete control over the system, and allows me to think in
more than one paradigms

Using STL and BOOST, I got the following benefits

more efficient

better portability

concise code

better thinking process because of high level constructs

automatic memory management without sacrificing efficiency

support for custom memory allocators

etc

I used Gentoo 2.6 as my development platform, and tested it Ubuntu 6.10
and Windows XP also.

There were no portability problems.

4. Features of Ax Chess

The following are the features provided by Ax Chess:

Valid Moves for all Pieces:

	The movement algorithms for all pieces are take care of, and all things
related to them like 	enpassant, castling, pawn promotion.

Check

	A player's king is under threat.

Checkmate

	A player's king is under threat and he cannot escape that situation.

Stalemate

	A players's king is not under threat, but he has no legal moves to
make.

Threefold-repetition

	If the same board position occurs for three consecutive moves, then the
player could claim a 	draw. Note that the same board position need not
occur in consecutive moves. For ex: if certain 	pattern of moves are
repeated such that the board position is repeated thrice, then the
player 	could claim a draw.

 

50 Move Rule

	If no piece has been captured in 50 consecutive moves, then the player
can claim a draw.

Minimal Draw Algorithm

	If both sides have minimal pieces with which either cannot win, an
algorithm detects this and 	reports a draw.

Undo & Redo

	The Undo and Redo algorithms are exposed in a simple manner, so the
user of this project can 	request undo and redo of any number of moves
(if any).

Chess API

	The above features and some others needed by the chess AI are exposed
as an API. The API is 	given as follows:

	enum MoveResult { INVALIDMOVE, VALIDMOVE, CHECK, CHECKMATE, 

				  STALEMATE, DRAW, THREEFOLDREPETITION,

				  FIFTYMOVERULE };

	// string format: d2d4, e7e5, b1c3, etc.,

	MoveResult move(const string&);

	// pos (0, 0) & (0, 7) => black rook, (7, 0) & (7, 7) => white rook

	MoveResult move(const Move&);

	bool whiteTurn();

	const PieceID* chessBoardIterator();

	void undo(size_t nmoves = 1);

	void redo(size_t nmoves = 1);

	void pawnPromoter(PieceID (*)(PieceID));

	void recordPossibleMoves(const Position&, vector<Position>&);

	void generate_moves(vector<Move>&);

5. Approach towards Solution

5.1 Object-Oriented Design

My initial approach towards this project was an Object-Oriented
Solution. The following diagram shows part of my initial design related
to the chessmen.

		Figure 2: Part of Object Oriented Design for chessmen

I have found Object Oriented Design such as the one above constraining
to my particular project, because of the following reasons:

1)  Cost of Dynamic binding: 

I have a detailed discussion on the cost of dynamic binding in the
section ``compile-time programming''.

2) Object Model Inconsistency

 In the real-world at any time I have at most 32 pieces on the chess
board. That means even in situations like pawn promotion, a pawn is
promoted to a queen, rook, bishop or knight i.e., a Pawn object should
get converted to a Queen, etc. This is not directly possible in a
statically programming language like C++. In dynamically typed
languages, say for example Python, I could have changed the type of an
object using something like this ``pawnObject.class =  class(Queen)'',
and the pawn object starts behaving as a Queen object. To get this
support in C++, I should use some extra levels of indirection through
which I could write several solutions easily. But this approach is out
of question because I try to minimize extra run-time indirections.

Upon trying this Object Oriented solution further when implementing
undo, redo operations by using design patterns like ``memento'', I found
that a purist object-oriented approach was though giving elegant
solutions had some extra indirections, because of which I had written
some work-around solutions in non-object oriented way. This approach I
had pushed further and I had got a solution now which is a mixture of
generic, functional, procedural and object oriented paradigms.

5. 2 Compile-time Programming:

Lets see an situation in my project, in which I arrived at a good
solution using Compile-time programming. The example is as follows:

The following function is executed by a class say ``GameManager''
whenever a user or a chess AI program makes a move.

	bool moveValid(const Position& from, const Position& to);

As the declaration says, the return value is true if the move made is
valid; false otherwise.

An efficient implementation of the above function is as follows:

Solution 1:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    if (id == WROOK || id == BROOK)

	        return rookMoveValid(from, to, board);

    	    else if (id == WKNIGHT || id == BKNIGHT)

          	   return knightMoveValid(from, to, board);

    	    else if (id == WBISHOP || id == BBISHOP)

              return bishopMoveValid(from, to, board);

    	    else if (id == WQUEEN || id == BQUEEN)

		   return queenMoveValid(from, to, board);

    	    else if (id == WKING || id == BKING)

   		   return kingMoveValid(from, to, board);

    	    else if (id == WPAWN || id == BPAWN)

		   return pawnMoveValid(from, to, board);

    	    return false;

	}

The above solution is an efficient one, but it is a bad practice to
implement this way, because of the following reasons:

I need to move a piece from one position to another in a lot of
functions that means I have to duplicate the above code at many places.
We all know that code duplication should be avoided, which helps in
easier maintainability of the code.

Large if-else blocks also makes it difficult to write reusable code. For
example, ``Chinese Chess'' has one more piece ``Cannon'' in addition to
the above pieces (the names of the chessmen are different than standard
chess names). If I want to resuse my chess project to

design ``Chinese Chess'' then I got to add another ``if condition'' as
in the above code, at all

the places that has such functionality.

Solution 2: Object Oriented Solution

Here I give a solution using Object Oriented Paradigm to avoid the above
mentioned two problems.

The following is a basic Object Oriented design for the chessmen in my
project.

	class Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&) = 0;

    	    virtual void move(const Position&, Board&);

	    // other member functions and data removed for clarity.

     };

The above ``Piece''' base class specifies a contract that should be
implemented by all its derived classes i.e., all the concrete chessmen.

The concrete classes are as follows:

	class Rook : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

	class Knight : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

Similarly Bishop, Queen, King and Pawn classes.

Now the code for the ``moveValid'' function would be as follows:

	bool Board::moveValid(const Position& from, const Position& to) {

    	    Piece *p = board.piece(from);

    	    return p && p->moveValid(to, board);

   	}

The above one is an elegant solution. It is as simple as saying in plain
english, ``get a piece from a position, and ask it to move to another
posiion''.

Unlike in Solution 1, here the board object is not concerned which piece
its going to move. It is guaranteed that whatever the Piece would be,
its going to support the ``moveValid'' function. And 

through dynamic binding the big ``if-else'' block in Solution 1 is
translated into simple code.

But this clarity comes at a cost in Object Oriented world. To understand
the cost of dynamic binding lets see the object representation for a
concrete piece like ``Rook''. The layout in memory for an object of
class ``Rook'' would be as follows:

			   Figure 3: A Rook Object layout

Any classes that has virtual functions would have a virtual table (per
class) that contains the RTTI (runtime type information) and the virtual
functions. Every object of such class has a ``vptr'' (virtual table
pointer) member pointer pointing to the vtable (virtual table).

The line ``p->moveValid(to, board)'' is translated into the following
assembly code by the compiler.

	; Note: function_offset and vptr_offset known at compile time

	load [object_address + vptr_offset], reg1

	load [reg1 + function_offset], reg2

	call reg2

As seen in the above assembly code, dynamic binding does two
dereferences (one for obtaining the vtable address, and another to
obtain the appropriate function; ``moveValid'' in this case) then the
actual function call. The above code is resuable too, say if I added
another piece ``Cannon'' for chines chess, then I need to write another
class ``Cannon'' which would derive from ``Piece'', and no changes are
required for the ``moveValid'' function.

One thing to be noticed in solution 1 is that: on an average six if
conditions would be executed  before the appropriate ``xxMoveValid''
function call. But a clever compiler in the case of Solution 1 could
inline all these ``xxMoveValid'' functions, there by avoiding the
function call itself. I agree that the C++ compiler cannot inline
functions that are not simple, however, it is possible to write the code
using techniques like tighter loops, functors (functions as values), etc
which are unrolled by the compiler, and

could be inlined.

Where as in the case of Solution 2, due to dynamic binding it is
impossible to inline the functions.

Hence, even that the Solution 2 is elegant it comes with an cost (2
dereferences and actual function call), which is undesirable in this
project where I am trying to increase the execution speed of the overall
application.

Solution 3: A better solution (one less dereference):

The following is the solution I arrived at after studying the dynamic
binding (especially how virtuals work through vtables). Here I kind of
create manual vtable which is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool (*moveValid_[12])(const Position&, const Position&, const Board&) 
	=

    			{ 

        			pawnMoveValid, knightMoveValid, bishopMoveValid,   

        			rookMoveValid, queenMoveValid, kingMoveValid, 

        			pawnMoveValid, knightMoveValid, bishopMoveValid, 

        			rookMoveValid, queenMoveValid, kingMoveValid

    			};

Here ``moveValid_'' is a  array [12] of function pointers. Now the
moveValid function could be written as

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && (*moveValid_[id])(from, to, board);

	}

As can be seen from the above code, now we have one dereference to the
actual function then the actual function call.

Solution 4: Compile-time Programming

This is the final solution I created which has the same benefits as
Solution 1, and none of its draw backs. The Solution is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	typedef boost::tuple

    		<		

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

			RookMoveValid, QueenMoveValid, KingMoveValid,

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

  			RookMoveValid, QueenMoveValid, KingMoveValid

    		> TUPLE;

	TUPLE moveValidFunctors;

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && call(moveValidFunctors, id, from, to,
board);

	}

	

The above ``moveValid'' is as elegant as the Solution 2 version and as
efficient as Solution 1.

The compiler translates the line ``call(moveValidFunctors, id, from, to,
board)'' to the following big ``if-else'' block.

	return id == 11 ? KingMoveValid(from, to, board)

		: (id == 10 ? QueenMoveValid(from, to, board)

		   ... 

		: (id ==  0 ? PawnMoveValid(from, to, board)))...);

I have written this ``call'' construct using Templates and partial
Template Specialization. Note that this conversion would take at compile
time, and hence once the compiler is done, the ``call'' construct
vanishes replacing itself by the big ``if-else'' block

6. Symbian

The following are a few concepts which I thought are worth mentioning.
These topics would be explained in detail in Symbian OS or Symbian C++
books. 

Standard C++ didn't had exceptions when Symbian OS was designed
initially. After exceptions were added to standard C++ it was found that
the language techniques used to support exceptional handling 

adds a good amount of overheads to the compiled code and also some
run-time overheads, regardless of whether exceptions were actually
thrown or not. So developers of Symbian OS didn't find exception
handling suitable to Symbian C++ because they wanted the Symbian OS and
the client code to be compact. Since Symbian C++ has a different way of
dealing with memory, its lays certain restrictions on the types that we
can create. These are called T, C and R classes. T classes are ones like
the primitive ones which do not need explicit destructors, and C classes
are the ones in which the virtuals are involved, and R classes represent
the resource classes.

Leaves

A simple, good and lightweight exception handling solution called
``leaves'' was developed for Symbian OS. A leave is used to propagate an
error which occurs because of exceptional conditions (such as being out
of memory or disk space) to higher-level code which can handle it. A
Symbian OS leave is equivalent to a C++ throw and a TRAP harness is used
to catch the leave. In fact, a TRAP harness is effectively a combination
of try and catch.

TRAP and leave are analogous to the setjmp() and longjmp() methods,
respectively - setjmp() tores information about the location to be
``jumped to'' in a jump buffer, which is used by ``longjmp()'' to direct
the code to jump to that point.

Cleanup Stack

The stack memory is freed as the stack unwinds, but otherwise the stack
frame is abandoned and no object destructors are called (which is unlike
a standard C++ exception). This means the destructors of any local
variables or arguments passed by value, or objects created as member
variables of either of these, will not be called. Some objects are
``leave-safe'' - they do not need destructors and contain only data
which can be destroyed as stack memory is freed by the leave. This data
may consist of the basic, built-in types or other objects which contain
such types. In Symbian OS these are called T classes, the characteristic
of which is that they may safely be created on the stack in functions
where code may leave. If a local variable is a pointer to an object on
the heap, when a leave occurs the pointer is destroyed without freeing
that heap memory, which becomes unrecoverable, causing a memory leak.
The memory is said to be orphaned. This means that C classes objects,
which are always created on the heap are not leave safe. R class objects
are generally not leave-safe either, since the resources they own must
be freed in the event of a leave (through a call to the appropriate
Close() or Release() type function). If this call cannot made by an
object accessible after the leave, the resource is orphaned.

Various techniques are used to effectively do the cleanup activities of
resources through Cleanup Stack.

I have read and understood the above concepts and several others related
to Symbian, such as

descriptors, dynamic buffers, event-driven multitasking using Active
Objects, Symbian OS Threads and Processes, graphics for display and
interaction etc.

I have resolved several issues while I was doing the port of Ax Chess to
Symbian OS. Some of issues were lack of STL and BOOST because of which I
had to write the appropriate constructs, and since Symbian C++ compiler
is not so sophisticated as standard C++ compilers like g++, Comeau C++,
MS Visual Studio C++  compiler,etc., I had written work-arounds for the
compile-time programming techniques I have used.

7. Memory Management

This is the area that I didn't think when I submitted the this project's
proposal. But during the course of this project I found that custom
memory management would improve the performance. The following is a
discussion on why custom memory management would be helpful.

Datastructures provided by STL are used, which currently manage memory
automatically.

Internally they call new/delete for memory allocation and deallocation.
The above mentioned dynamic memory allocators/dealloactors matter when
efficieny is  concerned. For example: Each "new" operation executes a OS
call to get memory allocated from free store, and each "delete" involves
in returning the allocated memory to the free  pool. These are costly
operations. And using "new/delete"s frequently in a chess AI program is
going to cost too much.

Created a Garbage Collector, which uses Mark-Sweep (with Compaction)
Algorithm. This project is made thread-safe using POSIX Threads, Mutex,
Condition variables etc. The Garbage Collector exposes a pointer
abstraction gc_ptr<T>, which has allocation speed faster than the
standard new operator, and can be approximated to the speed of the
allocation on stack space. However,

sweep does take time to reclaim storage space occupied by out-of-scope
pointers, and also to compact the active memory under use. Conversions
between gc_ptr of base and derived types are taken care at compile-time,
which ensures compile-time type safety; avoiding any run-time safety
overhead.

By default the Garbage Collector can be used in a multi-threaded
environment, but it can be configured at compile-time as a
single-threaded one, thus removing multithread specific overhead,
unnecessary in a single-thread environment. This type of Garbage
Collector can be used in projects where heap-based

memory allocations should be very fast. For example, a chess AI program
can use this garbage collector, to build large trees (of search-worthy
moves and search the best move) during the computers turn of play, and
can reclaim the storage when it is idle i.e., during the opponents turn.
This method drastically speeds-up performance when compared to the
standard new operator that itself spends a lot of time during
allocation.

There are other garbage collection algorithms available like reference
counting, mark sweep, copying, etc. I found that the mark-sweep one
suits best to the chess AI's situtation. Because all I do care is that
the memory allocations should be very efficient, and even though the
sweep is complex and inefficient, that doesn't matter because it is
supposed to be called in the idle phase of the chess AI program.

Currently this GC isn't integrated with "Ax Chess" as I haven't finished
testing the GC.

8. Screenshots

The following are a few screenshots showing some features of the
implementation.

 

		Figure 4: Ax Chess ported to Symbian OS (S60 devices), running on
emulator

 

	

				   Figure 5: A checkmate condition.

					Figure 6: A stalemate condition

The following is a screen-shot of my character user interface that uses
the chess API; showing the steps of a simple checkmate:

Note: White pieces are represented using lower-case letters and black
pieces are in upper case letters, as can be seen using the ``draw''
command.

		

				Figure 7: CUI using the chess API

9. Submitted Code & Installation instructions

For this project, you need to have a good C++ compiler. I would
recommend g++, comeau C++ compiler or MS Visual Studio 2005 C++
compiler.

And you need to have the BOOST library installed on your system.

For installing boost, check the instructions from the boost website 

  HYPERLINK "http://www.boost.org/" http://www.boost.org/ 

or for gentoo and debian based systems, here is a simple procedure

  HYPERLINK
"http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-d
ebianubuntu/"
http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-de
bianubuntu/ 

I have hosted my project code at savannah website. The url is

  HYPERLINK "http://savannah.nongnu.org/projects/ax-chess/"
http://savannah.nongnu.org/projects/ax-chess/ 

To download the project code, use the following command:

cvs -z3 -d:pserver:anonymous@cvs.savannah.nongnu.org:/sources/ax-chess
co ax-chess

The above command would create a directory ``ax-chess'' in your present
working directory.

Type ``make'' to compile the project. And  use ``./cuigamemanager'' at
the shell prompt to test 

Ax Chess.

I am also submitting the code as a tar.gz file to the ODU CS department
as part of the MS Project requirements. The zipped file would contain
both Ax Chess project and the port of Ax Chess for Symbian OS.

10. Conclusion

This project had been a great learning experience; I am a better
programmer now. There is plenty left to do. I believe that a fresh
review of my complete code would give me some more ideas to improve it.
The following are some the concepts that I have learned.

1) Several concepts of C++. For example, few would be Internal
representation of Objects, Templates, 2) Compile-time computations,
Policy based design.

3) Idea about different programming paradigms and efficiency
considerations.

4) STL and BOOST

5) Memory Management and Garbage Collection.

6) Symbian OS Internals and Symbian C++

7) Various Tools like emacs, g++, gdb, make, cppunit, gprof, Metrowerks
CodeWarrior, etc

MS PROJECT (FALL 2006)

Ax Chess, and efficient representation of Chess targeted for a chess AI
program and a mobile device

Submitted by Azhar Ali

Project Advisor: Dr. Mohammad Zubair

ABSTRACT

	   This project, Ax Chess, is a two player chess engine/game. Most of
the features of

	   chess, such as valid moves, checkmate, stalemate, threefold
repetition, fifty move

	   rule, etc., are implemented. This project exposes a chess api that
can be integrated

	   by a gui chess interface, a mobile chess interface and/or an
artificial chess engine.

	   Design and Efficiency aspects are be studied through out the
project. And a best

	   design which would utilize memory and processor's speed efficiently
is produced;

	   suitable to low-memory devices like Series 60 Symbian Mobile Phones.

Contents

Introduction

Motivation

Technologies/Tools Used

Features of Ax Chess

Approach towards Solution

5.1 Object Oriented Design

5.2 Compile-time Programming

Symbian

Memory Management

Screenshots (Implementation's output)

Submitted Code & Installation instructions

Conclusion

1. Introduction

This project essentially consists of two phases.

Phase I: This phase solely concentrates on the implementation of Ax
Chess. 

Throughout the course of this project, I constantly tried to refine the
code to incorporate

"compile time programming" techniques, which made the code elegant,
succinct and highly

maintainable; and in turn helped the compiler to generate efficient
machine code. I had also focused

on using different programming paradigms, particularly Generic
Programming Paradigm (using

parametric polymorphism, which compared to subtype polymorphism is very
efficient), Functional

Paradigm (through which, we could avoid loops with tighter code
generation), Object Oriented

Paradigm, Procedural Paradigm etc; and evaluated the best one(s) for my
project from the perspective of both an efficient implementation for a
chess AI and also low-memory devices.

Phase II: The project code for PC would also be ported to Symbian OS,
using Symbian C++, which is

a much restricted version of Standard C++. Because of the inherent
constrained environment of a

mobile phone (when compared to PC, of course), unlike Standard C++,
Symbian C++ has a completely

different way of managing memory, exception handling, etc. The Symbian
C++ port is done considering all these aspects. And another impediment
for the port is the lack of the Standard Template

Library and the Boost Library for the Symbian environment. I had written
handcrafted versions for some of those library features.

2. Motivation

2.1 Need for an Efficient Chess Representation

To understand the need for an efficient ``chess representation'' like Ax
Chess, lets consider the

following example of how a basic chess Artificial Intelligence (AI)
program works:

The following figure (Figure 1) shows the tree of board positions
generated by a minimax algorithm after playing one move by both sides:

As we can see from the Figure 1, when the game of chess begins, white
has a choice of 20 moves. Followed by a white's move, black has 20 moves
in reply. Thus 400 different positions arise after one move by both
sides. This number grows to 20,000 after two moves and astronomically
later.

Techniques like alpha-beta search, killer heuristics, etc., are employed
to prune such trees.The way a chess AI program works is by searching the
above mentioned tree to a certain depth for both sides, and deeper along
highly tactical lines. 

It is to be noted that the chess AI consults the ``chess
representation'' at every node of the moves tree, to

get the result of the move such as checkmate, stalemate, etc. The chess
AI program uses a depth first search to traverse the above tree, so it
backtracks a lot and needs the support of undo operations from the
``chess representation''. The undo (and also redo) mechanism and the
different chess algorithms are important operations, because their
implementation's efficiency multiplies by a large factor (actually by
the number of move nodes in a chess tree), when used by chess AI.

Currently, the strongest chess playing software ``Deep Fritz 10'' can
see 18-ply (i.e., 9 moves on both sides) deep. This means that the chess
representation's functionality would be executed millions of times.

	Figure 1: Chess AI Tree generated by minimax algorithm after one move
by both sides

2.2 Why yet another one?

There are a lot of excellent chess playing softwares like Fritz,
Extreme, Crafty, etc for PC and Chess Tiger, etc., for Smart Phones. A
lot of effort is going on to improve these softwares. To get into such
development stream one needs experience like programming a simple chess
AI and understanding the real efficiency concerns which are involved in
the chess AI computations. The aim of this project is to get such
experience.

3. Technologies/Tools used

The following are the list of technologies and tools used

C++, STL, BOOST, Symbian C++

emacs, g++, gdb, make, cppunit, gprof

Symbian 8.0a SDK, Metrowerks CodeWarrior, Microsoft Visual Studio 2003

I choose C++ as my programming language, because of its flexibility. It
gives me complete control over the system, and allows me to think in
more than one paradigms

Using STL and BOOST, I got the following benefits

more efficient

better portability

concise code

better thinking process because of high level constructs

automatic memory management without sacrificing efficiency

support for custom memory allocators

etc

I used Gentoo 2.6 as my development platform, and tested it Ubuntu 6.10
and Windows XP also.

There were no portability problems.

4. Features of Ax Chess

The following are the features provided by Ax Chess:

Valid Moves for all Pieces:

	The movement algorithms for all pieces are take care of, and all things
related to them like 	enpassant, castling, pawn promotion.

Check

	A player's king is under threat.

Checkmate

	A player's king is under threat and he cannot escape that situation.

Stalemate

	A players's king is not under threat, but he has no legal moves to
make.

Threefold-repetition

	If the same board position occurs for three consecutive moves, then the
player could claim a 	draw. Note that the same board position need not
occur in consecutive moves. For ex: if certain 	pattern of moves are
repeated such that the board position is repeated thrice, then the
player 	could claim a draw.

 

50 Move Rule

	If no piece has been captured in 50 consecutive moves, then the player
can claim a draw.

Minimal Draw Algorithm

	If both sides have minimal pieces with which either cannot win, an
algorithm detects this and 	reports a draw.

Undo & Redo

	The Undo and Redo algorithms are exposed in a simple manner, so the
user of this project can 	request undo and redo of any number of moves
(if any).

Chess API

	The above features and some others needed by the chess AI are exposed
as an API. The API is 	given as follows:

	enum MoveResult { INVALIDMOVE, VALIDMOVE, CHECK, CHECKMATE, 

				  STALEMATE, DRAW, THREEFOLDREPETITION,

				  FIFTYMOVERULE };

	// string format: d2d4, e7e5, b1c3, etc.,

	MoveResult move(const string&);

	// pos (0, 0) & (0, 7) => black rook, (7, 0) & (7, 7) => white rook

	MoveResult move(const Move&);

	bool whiteTurn();

	const PieceID* chessBoardIterator();

	void undo(size_t nmoves = 1);

	void redo(size_t nmoves = 1);

	void pawnPromoter(PieceID (*)(PieceID));

	void recordPossibleMoves(const Position&, vector<Position>&);

	void generate_moves(vector<Move>&);

5. Approach towards Solution

5.1 Object-Oriented Design

My initial approach towards this project was an Object-Oriented
Solution. The following diagram shows part of my initial design related
to the chessmen.

		Figure 2: Part of Object Oriented Design for chessmen

I have found Object Oriented Design such as the one above constraining
to my particular project, because of the following reasons:

1)  Cost of Dynamic binding: 

I have a detailed discussion on the cost of dynamic binding in the
section ``compile-time programming''.

2) Object Model Inconsistency

 In the real-world at any time I have at most 32 pieces on the chess
board. That means even in situations like pawn promotion, a pawn is
promoted to a queen, rook, bishop or knight i.e., a Pawn object should
get converted to a Queen, etc. This is not directly possible in a
statically programming language like C++. In dynamically typed
languages, say for example Python, I could have changed the type of an
object using something like this ``pawnObject.class =  class(Queen)'',
and the pawn object starts behaving as a Queen object. To get this
support in C++, I should use some extra levels of indirection through
which I could write several solutions easily. But this approach is out
of question because I try to minimize extra run-time indirections.

Upon trying this Object Oriented solution further when implementing
undo, redo operations by using design patterns like ``memento'', I found
that a purist object-oriented approach was though giving elegant
solutions had some extra indirections, because of which I had written
some work-around solutions in non-object oriented way. This approach I
had pushed further and I had got a solution now which is a mixture of
generic, functional, procedural and object oriented paradigms.

5. 2 Compile-time Programming:

Lets see an situation in my project, in which I arrived at a good
solution using Compile-time programming. The example is as follows:

The following function is executed by a class say ``GameManager''
whenever a user or a chess AI program makes a move.

	bool moveValid(const Position& from, const Position& to);

As the declaration says, the return value is true if the move made is
valid; false otherwise.

An efficient implementation of the above function is as follows:

Solution 1:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    if (id == WROOK || id == BROOK)

	        return rookMoveValid(from, to, board);

    	    else if (id == WKNIGHT || id == BKNIGHT)

          	   return knightMoveValid(from, to, board);

    	    else if (id == WBISHOP || id == BBISHOP)

              return bishopMoveValid(from, to, board);

    	    else if (id == WQUEEN || id == BQUEEN)

		   return queenMoveValid(from, to, board);

    	    else if (id == WKING || id == BKING)

   		   return kingMoveValid(from, to, board);

    	    else if (id == WPAWN || id == BPAWN)

		   return pawnMoveValid(from, to, board);

    	    return false;

	}

The above solution is an efficient one, but it is a bad practice to
implement this way, because of the following reasons:

I need to move a piece from one position to another in a lot of
functions that means I have to duplicate the above code at many places.
We all know that code duplication should be avoided, which helps in
easier maintainability of the code.

Large if-else blocks also makes it difficult to write reusable code. For
example, ``Chinese Chess'' has one more piece ``Cannon'' in addition to
the above pieces (the names of the chessmen are different than standard
chess names). If I want to resuse my chess project to

design ``Chinese Chess'' then I got to add another ``if condition'' as
in the above code, at all

the places that has such functionality.

Solution 2: Object Oriented Solution

Here I give a solution using Object Oriented Paradigm to avoid the above
mentioned two problems.

The following is a basic Object Oriented design for the chessmen in my
project.

	class Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&) = 0;

    	    virtual void move(const Position&, Board&);

	    // other member functions and data removed for clarity.

     };

The above ``Piece''' base class specifies a contract that should be
implemented by all its derived classes i.e., all the concrete chessmen.

The concrete classes are as follows:

	class Rook : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

	class Knight : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

Similarly Bishop, Queen, King and Pawn classes.

Now the code for the ``moveValid'' function would be as follows:

	bool Board::moveValid(const Position& from, const Position& to) {

    	    Piece *p = board.piece(from);

    	    return p && p->moveValid(to, board);

   	}

The above one is an elegant solution. It is as simple as saying in plain
english, ``get a piece from a position, and ask it to move to another
posiion''.

Unlike in Solution 1, here the board object is not concerned which piece
its going to move. It is guaranteed that whatever the Piece would be,
its going to support the ``moveValid'' function. And 

through dynamic binding the big ``if-else'' block in Solution 1 is
translated into simple code.

But this clarity comes at a cost in Object Oriented world. To understand
the cost of dynamic binding lets see the object representation for a
concrete piece like ``Rook''. The layout in memory for an object of
class ``Rook'' would be as follows:

			   Figure 3: A Rook Object layout

Any classes that has virtual functions would have a virtual table (per
class) that contains the RTTI (runtime type information) and the virtual
functions. Every object of such class has a ``vptr'' (virtual table
pointer) member pointer pointing to the vtable (virtual table).

The line ``p->moveValid(to, board)'' is translated into the following
assembly code by the compiler.

	; Note: function_offset and vptr_offset known at compile time

	load [object_address + vptr_offset], reg1

	load [reg1 + function_offset], reg2

	call reg2

As seen in the above assembly code, dynamic binding does two
dereferences (one for obtaining the vtable address, and another to
obtain the appropriate function; ``moveValid'' in this case) then the
actual function call. The above code is resuable too, say if I added
another piece ``Cannon'' for chines chess, then I need to write another
class ``Cannon'' which would derive from ``Piece'', and no changes are
required for the ``moveValid'' function.

One thing to be noticed in solution 1 is that: on an average six if
conditions would be executed  before the appropriate ``xxMoveValid''
function call. But a clever compiler in the case of Solution 1 could
inline all these ``xxMoveValid'' functions, there by avoiding the
function call itself. I agree that the C++ compiler cannot inline
functions that are not simple, however, it is possible to write the code
using techniques like tighter loops, functors (functions as values), etc
which are unrolled by the compiler, and

could be inlined.

Where as in the case of Solution 2, due to dynamic binding it is
impossible to inline the functions.

Hence, even that the Solution 2 is elegant it comes with an cost (2
dereferences and actual function call), which is undesirable in this
project where I am trying to increase the execution speed of the overall
application.

Solution 3: A better solution (one less dereference):

The following is the solution I arrived at after studying the dynamic
binding (especially how virtuals work through vtables). Here I kind of
create manual vtable which is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool (*moveValid_[12])(const Position&, const Position&, const Board&) 
	=

    			{ 

        			pawnMoveValid, knightMoveValid, bishopMoveValid,   

        			rookMoveValid, queenMoveValid, kingMoveValid, 

        			pawnMoveValid, knightMoveValid, bishopMoveValid, 

        			rookMoveValid, queenMoveValid, kingMoveValid

    			};

Here ``moveValid_'' is a  array [12] of function pointers. Now the
moveValid function could be written as

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && (*moveValid_[id])(from, to, board);

	}

As can be seen from the above code, now we have one dereference to the
actual function then the actual function call.

Solution 4: Compile-time Programming

This is the final solution I created which has the same benefits as
Solution 1, and none of its draw backs. The Solution is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	typedef boost::tuple

    		<		

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

			RookMoveValid, QueenMoveValid, KingMoveValid,

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

  			RookMoveValid, QueenMoveValid, KingMoveValid

    		> TUPLE;

	TUPLE moveValidFunctors;

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && call(moveValidFunctors, id, from, to,
board);

	}

	

The above ``moveValid'' is as elegant as the Solution 2 version and as
efficient as Solution 1.

The compiler translates the line ``call(moveValidFunctors, id, from, to,
board)'' to the following big ``if-else'' block.

	return id == 11 ? KingMoveValid(from, to, board)

		: (id == 10 ? QueenMoveValid(from, to, board)

		   ... 

		: (id ==  0 ? PawnMoveValid(from, to, board)))...);

I have written this ``call'' construct using Templates and partial
Template Specialization. Note that this conversion would take at compile
time, and hence once the compiler is done, the ``call'' construct
vanishes replacing itself by the big ``if-else'' block

6. Symbian

The following are a few concepts which I thought are worth mentioning.
These topics would be explained in detail in Symbian OS or Symbian C++
books. 

Standard C++ didn't had exceptions when Symbian OS was designed
initially. After exceptions were added to standard C++ it was found that
the language techniques used to support exceptional handling 

adds a good amount of overheads to the compiled code and also some
run-time overheads, regardless of whether exceptions were actually
thrown or not. So developers of Symbian OS didn't find exception
handling suitable to Symbian C++ because they wanted the Symbian OS and
the client code to be compact. Since Symbian C++ has a different way of
dealing with memory, its lays certain restrictions on the types that we
can create. These are called T, C and R classes. T classes are ones like
the primitive ones which do not need explicit destructors, and C classes
are the ones in which the virtuals are involved, and R classes represent
the resource classes.

Leaves

A simple, good and lightweight exception handling solution called
``leaves'' was developed for Symbian OS. A leave is used to propagate an
error which occurs because of exceptional conditions (such as being out
of memory or disk space) to higher-level code which can handle it. A
Symbian OS leave is equivalent to a C++ throw and a TRAP harness is used
to catch the leave. In fact, a TRAP harness is effectively a combination
of try and catch.

TRAP and leave are analogous to the setjmp() and longjmp() methods,
respectively - setjmp() tores information about the location to be
``jumped to'' in a jump buffer, which is used by ``longjmp()'' to direct
the code to jump to that point.

Cleanup Stack

The stack memory is freed as the stack unwinds, but otherwise the stack
frame is abandoned and no object destructors are called (which is unlike
a standard C++ exception). This means the destructors of any local
variables or arguments passed by value, or objects created as member
variables of either of these, will not be called. Some objects are
``leave-safe'' - they do not need destructors and contain only data
which can be destroyed as stack memory is freed by the leave. This data
may consist of the basic, built-in types or other objects which contain
such types. In Symbian OS these are called T classes, the characteristic
of which is that they may safely be created on the stack in functions
where code may leave. If a local variable is a pointer to an object on
the heap, when a leave occurs the pointer is destroyed without freeing
that heap memory, which becomes unrecoverable, causing a memory leak.
The memory is said to be orphaned. This means that C classes objects,
which are always created on the heap are not leave safe. R class objects
are generally not leave-safe either, since the resources they own must
be freed in the event of a leave (through a call to the appropriate
Close() or Release() type function). If this call cannot made by an
object accessible after the leave, the resource is orphaned.

Various techniques are used to effectively do the cleanup activities of
resources through Cleanup Stack.

I have read and understood the above concepts and several others related
to Symbian, such as

descriptors, dynamic buffers, event-driven multitasking using Active
Objects, Symbian OS Threads and Processes, graphics for display and
interaction etc.

I have resolved several issues while I was doing the port of Ax Chess to
Symbian OS. Some of issues were lack of STL and BOOST because of which I
had to write the appropriate constructs, and since Symbian C++ compiler
is not so sophisticated as standard C++ compilers like g++, Comeau C++,
MS Visual Studio C++  compiler,etc., I had written work-arounds for the
compile-time programming techniques I have used.

7. Memory Management

This is the area that I didn't think when I submitted the this project's
proposal. But during the course of this project I found that custom
memory management would improve the performance. The following is a
discussion on why custom memory management would be helpful.

Datastructures provided by STL are used, which currently manage memory
automatically.

Internally they call new/delete for memory allocation and deallocation.
The above mentioned dynamic memory allocators/dealloactors matter when
efficieny is  concerned. For example: Each "new" operation executes a OS
call to get memory allocated from free store, and each "delete" involves
in returning the allocated memory to the free  pool. These are costly
operations. And using "new/delete"s frequently in a chess AI program is
going to cost too much.

Created a Garbage Collector, which uses Mark-Sweep (with Compaction)
Algorithm. This project is made thread-safe using POSIX Threads, Mutex,
Condition variables etc. The Garbage Collector exposes a pointer
abstraction gc_ptr<T>, which has allocation speed faster than the
standard new operator, and can be approximated to the speed of the
allocation on stack space. However,

sweep does take time to reclaim storage space occupied by out-of-scope
pointers, and also to compact the active memory under use. Conversions
between gc_ptr of base and derived types are taken care at compile-time,
which ensures compile-time type safety; avoiding any run-time safety
overhead.

By default the Garbage Collector can be used in a multi-threaded
environment, but it can be configured at compile-time as a
single-threaded one, thus removing multithread specific overhead,
unnecessary in a single-thread environment. This type of Garbage
Collector can be used in projects where heap-based

memory allocations should be very fast. For example, a chess AI program
can use this garbage collector, to build large trees (of search-worthy
moves and search the best move) during the computers turn of play, and
can reclaim the storage when it is idle i.e., during the opponents turn.
This method drastically speeds-up performance when compared to the
standard new operator that itself spends a lot of time during
allocation.

There are other garbage collection algorithms available like reference
counting, mark sweep, copying, etc. I found that the mark-sweep one
suits best to the chess AI's situtation. Because all I do care is that
the memory allocations should be very efficient, and even though the
sweep is complex and inefficient, that doesn't matter because it is
supposed to be called in the idle phase of the chess AI program.

Currently this GC isn't integrated with "Ax Chess" as I haven't finished
testing the GC.

8. Screenshots

The following are a few screenshots showing some features of the
implementation.

 

		Figure 4: Ax Chess ported to Symbian OS (S60 devices), running on
emulator

 

	

				   Figure 5: A checkmate condition.

					Figure 6: A stalemate condition

The following is a screen-shot of my character user interface that uses
the chess API; showing the steps of a simple checkmate:

Note: White pieces are represented using lower-case letters and black
pieces are in upper case letters, as can be seen using the ``draw''
command.

		

				Figure 7: CUI using the chess API

9. Submitted Code & Installation instructions

For this project, you need to have a good C++ compiler. I would
recommend g++, comeau C++ compiler or MS Visual Studio 2005 C++
compiler.

And you need to have the BOOST library installed on your system.

For installing boost, check the instructions from the boost website 

  HYPERLINK "http://www.boost.org/" http://www.boost.org/ 

or for gentoo and debian based systems, here is a simple procedure

  HYPERLINK
"http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-d
ebianubuntu/"
http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-de
bianubuntu/ 

I have hosted my project code at savannah website. The url is

  HYPERLINK "http://savannah.nongnu.org/projects/ax-chess/"
http://savannah.nongnu.org/projects/ax-chess/ 

To download the project code, use the following command:

cvs -z3 -d:pserver:anonymous@cvs.savannah.nongnu.org:/sources/ax-chess
co ax-chess

The above command would create a directory ``ax-chess'' in your present
working directory.

Type ``make'' to compile the project. And  use ``./cuigamemanager'' at
the shell prompt to test 

Ax Chess.

I am also submitting the code as a tar.gz file to the ODU CS department
as part of the MS Project requirements. The zipped file would contain
both Ax Chess project and the port of Ax Chess for Symbian OS.

10. Conclusion

This project had been a great learning experience; I am a better
programmer now. There is plenty left to do. I believe that a fresh
review of my complete code would give me some more ideas to improve it.
The following are some the concepts that I have learned.

1) Several concepts of C++. For example, few would be Internal
representation of Objects, Templates, 2) Compile-time computations,
Policy based design.

3) Idea about different programming paradigms and efficiency
considerations.

4) STL and BOOST

5) Memory Management and Garbage Collection.

6) Symbian OS Internals and Symbian C++

7) Various Tools like emacs, g++, gdb, make, cppunit, gprof, Metrowerks
CodeWarrior, etc

MS PROJECT (FALL 2006)

Ax Chess, and efficient representation of Chess targeted for a chess AI
program and a mobile device

Submitted by Azhar Ali

Project Advisor: Dr. Mohammad Zubair

ABSTRACT

	   This project, Ax Chess, is a two player chess engine/game. Most of
the features of

	   chess, such as valid moves, checkmate, stalemate, threefold
repetition, fifty move

	   rule, etc., are implemented. This project exposes a chess api that
can be integrated

	   by a gui chess interface, a mobile chess interface and/or an
artificial chess engine.

	   Design and Efficiency aspects are be studied through out the
project. And a best

	   design which would utilize memory and processor's speed efficiently
is produced;

	   suitable to low-memory devices like Series 60 Symbian Mobile Phones.

Contents

Introduction

Motivation

Technologies/Tools Used

Features of Ax Chess

Approach towards Solution

5.1 Object Oriented Design

5.2 Compile-time Programming

Symbian

Memory Management

Screenshots (Implementation's output)

Submitted Code & Installation instructions

Conclusion

1. Introduction

This project essentially consists of two phases.

Phase I: This phase solely concentrates on the implementation of Ax
Chess. 

Throughout the course of this project, I constantly tried to refine the
code to incorporate

"compile time programming" techniques, which made the code elegant,
succinct and highly

maintainable; and in turn helped the compiler to generate efficient
machine code. I had also focused

on using different programming paradigms, particularly Generic
Programming Paradigm (using

parametric polymorphism, which compared to subtype polymorphism is very
efficient), Functional

Paradigm (through which, we could avoid loops with tighter code
generation), Object Oriented

Paradigm, Procedural Paradigm etc; and evaluated the best one(s) for my
project from the perspective of both an efficient implementation for a
chess AI and also low-memory devices.

Phase II: The project code for PC would also be ported to Symbian OS,
using Symbian C++, which is

a much restricted version of Standard C++. Because of the inherent
constrained environment of a

mobile phone (when compared to PC, of course), unlike Standard C++,
Symbian C++ has a completely

different way of managing memory, exception handling, etc. The Symbian
C++ port is done considering all these aspects. And another impediment
for the port is the lack of the Standard Template

Library and the Boost Library for the Symbian environment. I had written
handcrafted versions for some of those library features.

2. Motivation

2.1 Need for an Efficient Chess Representation

To understand the need for an efficient ``chess representation'' like Ax
Chess, lets consider the

following example of how a basic chess Artificial Intelligence (AI)
program works:

The following figure (Figure 1) shows the tree of board positions
generated by a minimax algorithm after playing one move by both sides:

As we can see from the Figure 1, when the game of chess begins, white
has a choice of 20 moves. Followed by a white's move, black has 20 moves
in reply. Thus 400 different positions arise after one move by both
sides. This number grows to 20,000 after two moves and astronomically
later.

Techniques like alpha-beta search, killer heuristics, etc., are employed
to prune such trees.The way a chess AI program works is by searching the
above mentioned tree to a certain depth for both sides, and deeper along
highly tactical lines. 

It is to be noted that the chess AI consults the ``chess
representation'' at every node of the moves tree, to

get the result of the move such as checkmate, stalemate, etc. The chess
AI program uses a depth first search to traverse the above tree, so it
backtracks a lot and needs the support of undo operations from the
``chess representation''. The undo (and also redo) mechanism and the
different chess algorithms are important operations, because their
implementation's efficiency multiplies by a large factor (actually by
the number of move nodes in a chess tree), when used by chess AI.

Currently, the strongest chess playing software ``Deep Fritz 10'' can
see 18-ply (i.e., 9 moves on both sides) deep. This means that the chess
representation's functionality would be executed millions of times.

	Figure 1: Chess AI Tree generated by minimax algorithm after one move
by both sides

2.2 Why yet another one?

There are a lot of excellent chess playing softwares like Fritz,
Extreme, Crafty, etc for PC and Chess Tiger, etc., for Smart Phones. A
lot of effort is going on to improve these softwares. To get into such
development stream one needs experience like programming a simple chess
AI and understanding the real efficiency concerns which are involved in
the chess AI computations. The aim of this project is to get such
experience.

3. Technologies/Tools used

The following are the list of technologies and tools used

C++, STL, BOOST, Symbian C++

emacs, g++, gdb, make, cppunit, gprof

Symbian 8.0a SDK, Metrowerks CodeWarrior, Microsoft Visual Studio 2003

I choose C++ as my programming language, because of its flexibility. It
gives me complete control over the system, and allows me to think in
more than one paradigms

Using STL and BOOST, I got the following benefits

more efficient

better portability

concise code

better thinking process because of high level constructs

automatic memory management without sacrificing efficiency

support for custom memory allocators

etc

I used Gentoo 2.6 as my development platform, and tested it Ubuntu 6.10
and Windows XP also.

There were no portability problems.

4. Features of Ax Chess

The following are the features provided by Ax Chess:

Valid Moves for all Pieces:

	The movement algorithms for all pieces are take care of, and all things
related to them like 	enpassant, castling, pawn promotion.

Check

	A player's king is under threat.

Checkmate

	A player's king is under threat and he cannot escape that situation.

Stalemate

	A players's king is not under threat, but he has no legal moves to
make.

Threefold-repetition

	If the same board position occurs for three consecutive moves, then the
player could claim a 	draw. Note that the same board position need not
occur in consecutive moves. For ex: if certain 	pattern of moves are
repeated such that the board position is repeated thrice, then the
player 	could claim a draw.

 

50 Move Rule

	If no piece has been captured in 50 consecutive moves, then the player
can claim a draw.

Minimal Draw Algorithm

	If both sides have minimal pieces with which either cannot win, an
algorithm detects this and 	reports a draw.

Undo & Redo

	The Undo and Redo algorithms are exposed in a simple manner, so the
user of this project can 	request undo and redo of any number of moves
(if any).

Chess API

	The above features and some others needed by the chess AI are exposed
as an API. The API is 	given as follows:

	enum MoveResult { INVALIDMOVE, VALIDMOVE, CHECK, CHECKMATE, 

				  STALEMATE, DRAW, THREEFOLDREPETITION,

				  FIFTYMOVERULE };

	// string format: d2d4, e7e5, b1c3, etc.,

	MoveResult move(const string&);

	// pos (0, 0) & (0, 7) => black rook, (7, 0) & (7, 7) => white rook

	MoveResult move(const Move&);

	bool whiteTurn();

	const PieceID* chessBoardIterator();

	void undo(size_t nmoves = 1);

	void redo(size_t nmoves = 1);

	void pawnPromoter(PieceID (*)(PieceID));

	void recordPossibleMoves(const Position&, vector<Position>&);

	void generate_moves(vector<Move>&);

5. Approach towards Solution

5.1 Object-Oriented Design

My initial approach towards this project was an Object-Oriented
Solution. The following diagram shows part of my initial design related
to the chessmen.

		Figure 2: Part of Object Oriented Design for chessmen

I have found Object Oriented Design such as the one above constraining
to my particular project, because of the following reasons:

1)  Cost of Dynamic binding: 

I have a detailed discussion on the cost of dynamic binding in the
section ``compile-time programming''.

2) Object Model Inconsistency

 In the real-world at any time I have at most 32 pieces on the chess
board. That means even in situations like pawn promotion, a pawn is
promoted to a queen, rook, bishop or knight i.e., a Pawn object should
get converted to a Queen, etc. This is not directly possible in a
statically programming language like C++. In dynamically typed
languages, say for example Python, I could have changed the type of an
object using something like this ``pawnObject.class =  class(Queen)'',
and the pawn object starts behaving as a Queen object. To get this
support in C++, I should use some extra levels of indirection through
which I could write several solutions easily. But this approach is out
of question because I try to minimize extra run-time indirections.

Upon trying this Object Oriented solution further when implementing
undo, redo operations by using design patterns like ``memento'', I found
that a purist object-oriented approach was though giving elegant
solutions had some extra indirections, because of which I had written
some work-around solutions in non-object oriented way. This approach I
had pushed further and I had got a solution now which is a mixture of
generic, functional, procedural and object oriented paradigms.

5. 2 Compile-time Programming:

Lets see an situation in my project, in which I arrived at a good
solution using Compile-time programming. The example is as follows:

The following function is executed by a class say ``GameManager''
whenever a user or a chess AI program makes a move.

	bool moveValid(const Position& from, const Position& to);

As the declaration says, the return value is true if the move made is
valid; false otherwise.

An efficient implementation of the above function is as follows:

Solution 1:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    if (id == WROOK || id == BROOK)

	        return rookMoveValid(from, to, board);

    	    else if (id == WKNIGHT || id == BKNIGHT)

          	   return knightMoveValid(from, to, board);

    	    else if (id == WBISHOP || id == BBISHOP)

              return bishopMoveValid(from, to, board);

    	    else if (id == WQUEEN || id == BQUEEN)

		   return queenMoveValid(from, to, board);

    	    else if (id == WKING || id == BKING)

   		   return kingMoveValid(from, to, board);

    	    else if (id == WPAWN || id == BPAWN)

		   return pawnMoveValid(from, to, board);

    	    return false;

	}

The above solution is an efficient one, but it is a bad practice to
implement this way, because of the following reasons:

I need to move a piece from one position to another in a lot of
functions that means I have to duplicate the above code at many places.
We all know that code duplication should be avoided, which helps in
easier maintainability of the code.

Large if-else blocks also makes it difficult to write reusable code. For
example, ``Chinese Chess'' has one more piece ``Cannon'' in addition to
the above pieces (the names of the chessmen are different than standard
chess names). If I want to resuse my chess project to

design ``Chinese Chess'' then I got to add another ``if condition'' as
in the above code, at all

the places that has such functionality.

Solution 2: Object Oriented Solution

Here I give a solution using Object Oriented Paradigm to avoid the above
mentioned two problems.

The following is a basic Object Oriented design for the chessmen in my
project.

	class Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&) = 0;

    	    virtual void move(const Position&, Board&);

	    // other member functions and data removed for clarity.

     };

The above ``Piece''' base class specifies a contract that should be
implemented by all its derived classes i.e., all the concrete chessmen.

The concrete classes are as follows:

	class Rook : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

	class Knight : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

Similarly Bishop, Queen, King and Pawn classes.

Now the code for the ``moveValid'' function would be as follows:

	bool Board::moveValid(const Position& from, const Position& to) {

    	    Piece *p = board.piece(from);

    	    return p && p->moveValid(to, board);

   	}

The above one is an elegant solution. It is as simple as saying in plain
english, ``get a piece from a position, and ask it to move to another
posiion''.

Unlike in Solution 1, here the board object is not concerned which piece
its going to move. It is guaranteed that whatever the Piece would be,
its going to support the ``moveValid'' function. And 

through dynamic binding the big ``if-else'' block in Solution 1 is
translated into simple code.

But this clarity comes at a cost in Object Oriented world. To understand
the cost of dynamic binding lets see the object representation for a
concrete piece like ``Rook''. The layout in memory for an object of
class ``Rook'' would be as follows:

			   Figure 3: A Rook Object layout

Any classes that has virtual functions would have a virtual table (per
class) that contains the RTTI (runtime type information) and the virtual
functions. Every object of such class has a ``vptr'' (virtual table
pointer) member pointer pointing to the vtable (virtual table).

The line ``p->moveValid(to, board)'' is translated into the following
assembly code by the compiler.

	; Note: function_offset and vptr_offset known at compile time

	load [object_address + vptr_offset], reg1

	load [reg1 + function_offset], reg2

	call reg2

As seen in the above assembly code, dynamic binding does two
dereferences (one for obtaining the vtable address, and another to
obtain the appropriate function; ``moveValid'' in this case) then the
actual function call. The above code is resuable too, say if I added
another piece ``Cannon'' for chines chess, then I need to write another
class ``Cannon'' which would derive from ``Piece'', and no changes are
required for the ``moveValid'' function.

One thing to be noticed in solution 1 is that: on an average six if
conditions would be executed  before the appropriate ``xxMoveValid''
function call. But a clever compiler in the case of Solution 1 could
inline all these ``xxMoveValid'' functions, there by avoiding the
function call itself. I agree that the C++ compiler cannot inline
functions that are not simple, however, it is possible to write the code
using techniques like tighter loops, functors (functions as values), etc
which are unrolled by the compiler, and

could be inlined.

Where as in the case of Solution 2, due to dynamic binding it is
impossible to inline the functions.

Hence, even that the Solution 2 is elegant it comes with an cost (2
dereferences and actual function call), which is undesirable in this
project where I am trying to increase the execution speed of the overall
application.

Solution 3: A better solution (one less dereference):

The following is the solution I arrived at after studying the dynamic
binding (especially how virtuals work through vtables). Here I kind of
create manual vtable which is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool (*moveValid_[12])(const Position&, const Position&, const Board&) 
	=

    			{ 

        			pawnMoveValid, knightMoveValid, bishopMoveValid,   

        			rookMoveValid, queenMoveValid, kingMoveValid, 

        			pawnMoveValid, knightMoveValid, bishopMoveValid, 

        			rookMoveValid, queenMoveValid, kingMoveValid

    			};

Here ``moveValid_'' is a  array [12] of function pointers. Now the
moveValid function could be written as

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && (*moveValid_[id])(from, to, board);

	}

As can be seen from the above code, now we have one dereference to the
actual function then the actual function call.

Solution 4: Compile-time Programming

This is the final solution I created which has the same benefits as
Solution 1, and none of its draw backs. The Solution is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	typedef boost::tuple

    		<		

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

			RookMoveValid, QueenMoveValid, KingMoveValid,

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

  			RookMoveValid, QueenMoveValid, KingMoveValid

    		> TUPLE;

	TUPLE moveValidFunctors;

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && call(moveValidFunctors, id, from, to,
board);

	}

	

The above ``moveValid'' is as elegant as the Solution 2 version and as
efficient as Solution 1.

The compiler translates the line ``call(moveValidFunctors, id, from, to,
board)'' to the following big ``if-else'' block.

	return id == 11 ? KingMoveValid(from, to, board)

		: (id == 10 ? QueenMoveValid(from, to, board)

		   ... 

		: (id ==  0 ? PawnMoveValid(from, to, board)))...);

I have written this ``call'' construct using Templates and partial
Template Specialization. Note that this conversion would take at compile
time, and hence once the compiler is done, the ``call'' construct
vanishes replacing itself by the big ``if-else'' block

6. Symbian

The following are a few concepts which I thought are worth mentioning.
These topics would be explained in detail in Symbian OS or Symbian C++
books. 

Standard C++ didn't had exceptions when Symbian OS was designed
initially. After exceptions were added to standard C++ it was found that
the language techniques used to support exceptional handling 

adds a good amount of overheads to the compiled code and also some
run-time overheads, regardless of whether exceptions were actually
thrown or not. So developers of Symbian OS didn't find exception
handling suitable to Symbian C++ because they wanted the Symbian OS and
the client code to be compact. Since Symbian C++ has a different way of
dealing with memory, its lays certain restrictions on the types that we
can create. These are called T, C and R classes. T classes are ones like
the primitive ones which do not need explicit destructors, and C classes
are the ones in which the virtuals are involved, and R classes represent
the resource classes.

Leaves

A simple, good and lightweight exception handling solution called
``leaves'' was developed for Symbian OS. A leave is used to propagate an
error which occurs because of exceptional conditions (such as being out
of memory or disk space) to higher-level code which can handle it. A
Symbian OS leave is equivalent to a C++ throw and a TRAP harness is used
to catch the leave. In fact, a TRAP harness is effectively a combination
of try and catch.

TRAP and leave are analogous to the setjmp() and longjmp() methods,
respectively - setjmp() tores information about the location to be
``jumped to'' in a jump buffer, which is used by ``longjmp()'' to direct
the code to jump to that point.

Cleanup Stack

The stack memory is freed as the stack unwinds, but otherwise the stack
frame is abandoned and no object destructors are called (which is unlike
a standard C++ exception). This means the destructors of any local
variables or arguments passed by value, or objects created as member
variables of either of these, will not be called. Some objects are
``leave-safe'' - they do not need destructors and contain only data
which can be destroyed as stack memory is freed by the leave. This data
may consist of the basic, built-in types or other objects which contain
such types. In Symbian OS these are called T classes, the characteristic
of which is that they may safely be created on the stack in functions
where code may leave. If a local variable is a pointer to an object on
the heap, when a leave occurs the pointer is destroyed without freeing
that heap memory, which becomes unrecoverable, causing a memory leak.
The memory is said to be orphaned. This means that C classes objects,
which are always created on the heap are not leave safe. R class objects
are generally not leave-safe either, since the resources they own must
be freed in the event of a leave (through a call to the appropriate
Close() or Release() type function). If this call cannot made by an
object accessible after the leave, the resource is orphaned.

Various techniques are used to effectively do the cleanup activities of
resources through Cleanup Stack.

I have read and understood the above concepts and several others related
to Symbian, such as

descriptors, dynamic buffers, event-driven multitasking using Active
Objects, Symbian OS Threads and Processes, graphics for display and
interaction etc.

I have resolved several issues while I was doing the port of Ax Chess to
Symbian OS. Some of issues were lack of STL and BOOST because of which I
had to write the appropriate constructs, and since Symbian C++ compiler
is not so sophisticated as standard C++ compilers like g++, Comeau C++,
MS Visual Studio C++  compiler,etc., I had written work-arounds for the
compile-time programming techniques I have used.

7. Memory Management

This is the area that I didn't think when I submitted the this project's
proposal. But during the course of this project I found that custom
memory management would improve the performance. The following is a
discussion on why custom memory management would be helpful.

Datastructures provided by STL are used, which currently manage memory
automatically.

Internally they call new/delete for memory allocation and deallocation.
The above mentioned dynamic memory allocators/dealloactors matter when
efficieny is  concerned. For example: Each "new" operation executes a OS
call to get memory allocated from free store, and each "delete" involves
in returning the allocated memory to the free  pool. These are costly
operations. And using "new/delete"s frequently in a chess AI program is
going to cost too much.

Created a Garbage Collector, which uses Mark-Sweep (with Compaction)
Algorithm. This project is made thread-safe using POSIX Threads, Mutex,
Condition variables etc. The Garbage Collector exposes a pointer
abstraction gc_ptr<T>, which has allocation speed faster than the
standard new operator, and can be approximated to the speed of the
allocation on stack space. However,

sweep does take time to reclaim storage space occupied by out-of-scope
pointers, and also to compact the active memory under use. Conversions
between gc_ptr of base and derived types are taken care at compile-time,
which ensures compile-time type safety; avoiding any run-time safety
overhead.

By default the Garbage Collector can be used in a multi-threaded
environment, but it can be configured at compile-time as a
single-threaded one, thus removing multithread specific overhead,
unnecessary in a single-thread environment. This type of Garbage
Collector can be used in projects where heap-based

memory allocations should be very fast. For example, a chess AI program
can use this garbage collector, to build large trees (of search-worthy
moves and search the best move) during the computers turn of play, and
can reclaim the storage when it is idle i.e., during the opponents turn.
This method drastically speeds-up performance when compared to the
standard new operator that itself spends a lot of time during
allocation.

There are other garbage collection algorithms available like reference
counting, mark sweep, copying, etc. I found that the mark-sweep one
suits best to the chess AI's situtation. Because all I do care is that
the memory allocations should be very efficient, and even though the
sweep is complex and inefficient, that doesn't matter because it is
supposed to be called in the idle phase of the chess AI program.

Currently this GC isn't integrated with "Ax Chess" as I haven't finished
testing the GC.

8. Screenshots

The following are a few screenshots showing some features of the
implementation.

 

		Figure 4: Ax Chess ported to Symbian OS (S60 devices), running on
emulator

 

	

				   Figure 5: A checkmate condition.

					Figure 6: A stalemate condition

The following is a screen-shot of my character user interface that uses
the chess API; showing the steps of a simple checkmate:

Note: White pieces are represented using lower-case letters and black
pieces are in upper case letters, as can be seen using the ``draw''
command.

		

				Figure 7: CUI using the chess API

9. Submitted Code & Installation instructions

For this project, you need to have a good C++ compiler. I would
recommend g++, comeau C++ compiler or MS Visual Studio 2005 C++
compiler.

And you need to have the BOOST library installed on your system.

For installing boost, check the instructions from the boost website 

  HYPERLINK "http://www.boost.org/" http://www.boost.org/ 

or for gentoo and debian based systems, here is a simple procedure

  HYPERLINK
"http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-d
ebianubuntu/"
http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-de
bianubuntu/ 

I have hosted my project code at savannah website. The url is

  HYPERLINK "http://savannah.nongnu.org/projects/ax-chess/"
http://savannah.nongnu.org/projects/ax-chess/ 

To download the project code, use the following command:

cvs -z3 -d:pserver:anonymous@cvs.savannah.nongnu.org:/sources/ax-chess
co ax-chess

The above command would create a directory ``ax-chess'' in your present
working directory.

Type ``make'' to compile the project. And  use ``./cuigamemanager'' at
the shell prompt to test 

Ax Chess.

I am also submitting the code as a tar.gz file to the ODU CS department
as part of the MS Project requirements. The zipped file would contain
both Ax Chess project and the port of Ax Chess for Symbian OS.

10. Conclusion

This project had been a great learning experience; I am a better
programmer now. There is plenty left to do. I believe that a fresh
review of my complete code would give me some more ideas to improve it.
The following are some the concepts that I have learned.

1) Several concepts of C++. For example, few would be Internal
representation of Objects, Templates, 2) Compile-time computations,
Policy based design.

3) Idea about different programming paradigms and efficiency
considerations.

4) STL and BOOST

5) Memory Management and Garbage Collection.

6) Symbian OS Internals and Symbian C++

7) Various Tools like emacs, g++, gdb, make, cppunit, gprof, Metrowerks
CodeWarrior, etc

MS PROJECT (FALL 2006)

Ax Chess, and efficient representation of Chess targeted for a chess AI
program and a mobile device

Submitted by Azhar Ali

Project Advisor: Dr. Mohammad Zubair

ABSTRACT

	   This project, Ax Chess, is a two player chess engine/game. Most of
the features of

	   chess, such as valid moves, checkmate, stalemate, threefold
repetition, fifty move

	   rule, etc., are implemented. This project exposes a chess api that
can be integrated

	   by a gui chess interface, a mobile chess interface and/or an
artificial chess engine.

	   Design and Efficiency aspects are be studied through out the
project. And a best

	   design which would utilize memory and processor's speed efficiently
is produced;

	   suitable to low-memory devices like Series 60 Symbian Mobile Phones.

Contents

Introduction

Motivation

Technologies/Tools Used

Features of Ax Chess

Approach towards Solution

5.1 Object Oriented Design

5.2 Compile-time Programming

Symbian

Memory Management

Screenshots (Implementation's output)

Submitted Code & Installation instructions

Conclusion

1. Introduction

This project essentially consists of two phases.

Phase I: This phase solely concentrates on the implementation of Ax
Chess. 

Throughout the course of this project, I constantly tried to refine the
code to incorporate

"compile time programming" techniques, which made the code elegant,
succinct and highly

maintainable; and in turn helped the compiler to generate efficient
machine code. I had also focused

on using different programming paradigms, particularly Generic
Programming Paradigm (using

parametric polymorphism, which compared to subtype polymorphism is very
efficient), Functional

Paradigm (through which, we could avoid loops with tighter code
generation), Object Oriented

Paradigm, Procedural Paradigm etc; and evaluated the best one(s) for my
project from the perspective of both an efficient implementation for a
chess AI and also low-memory devices.

Phase II: The project code for PC would also be ported to Symbian OS,
using Symbian C++, which is

a much restricted version of Standard C++. Because of the inherent
constrained environment of a

mobile phone (when compared to PC, of course), unlike Standard C++,
Symbian C++ has a completely

different way of managing memory, exception handling, etc. The Symbian
C++ port is done considering all these aspects. And another impediment
for the port is the lack of the Standard Template

Library and the Boost Library for the Symbian environment. I had written
handcrafted versions for some of those library features.

2. Motivation

2.1 Need for an Efficient Chess Representation

To understand the need for an efficient ``chess representation'' like Ax
Chess, lets consider the

following example of how a basic chess Artificial Intelligence (AI)
program works:

The following figure (Figure 1) shows the tree of board positions
generated by a minimax algorithm after playing one move by both sides:

As we can see from the Figure 1, when the game of chess begins, white
has a choice of 20 moves. Followed by a white's move, black has 20 moves
in reply. Thus 400 different positions arise after one move by both
sides. This number grows to 20,000 after two moves and astronomically
later.

Techniques like alpha-beta search, killer heuristics, etc., are employed
to prune such trees.The way a chess AI program works is by searching the
above mentioned tree to a certain depth for both sides, and deeper along
highly tactical lines. 

It is to be noted that the chess AI consults the ``chess
representation'' at every node of the moves tree, to

get the result of the move such as checkmate, stalemate, etc. The chess
AI program uses a depth first search to traverse the above tree, so it
backtracks a lot and needs the support of undo operations from the
``chess representation''. The undo (and also redo) mechanism and the
different chess algorithms are important operations, because their
implementation's efficiency multiplies by a large factor (actually by
the number of move nodes in a chess tree), when used by chess AI.

Currently, the strongest chess playing software ``Deep Fritz 10'' can
see 18-ply (i.e., 9 moves on both sides) deep. This means that the chess
representation's functionality would be executed millions of times.

	Figure 1: Chess AI Tree generated by minimax algorithm after one move
by both sides

2.2 Why yet another one?

There are a lot of excellent chess playing softwares like Fritz,
Extreme, Crafty, etc for PC and Chess Tiger, etc., for Smart Phones. A
lot of effort is going on to improve these softwares. To get into such
development stream one needs experience like programming a simple chess
AI and understanding the real efficiency concerns which are involved in
the chess AI computations. The aim of this project is to get such
experience.

3. Technologies/Tools used

The following are the list of technologies and tools used

C++, STL, BOOST, Symbian C++

emacs, g++, gdb, make, cppunit, gprof

Symbian 8.0a SDK, Metrowerks CodeWarrior, Microsoft Visual Studio 2003

I choose C++ as my programming language, because of its flexibility. It
gives me complete control over the system, and allows me to think in
more than one paradigms

Using STL and BOOST, I got the following benefits

more efficient

better portability

concise code

better thinking process because of high level constructs

automatic memory management without sacrificing efficiency

support for custom memory allocators

etc

I used Gentoo 2.6 as my development platform, and tested it Ubuntu 6.10
and Windows XP also.

There were no portability problems.

4. Features of Ax Chess

The following are the features provided by Ax Chess:

Valid Moves for all Pieces:

	The movement algorithms for all pieces are take care of, and all things
related to them like 	enpassant, castling, pawn promotion.

Check

	A player's king is under threat.

Checkmate

	A player's king is under threat and he cannot escape that situation.

Stalemate

	A players's king is not under threat, but he has no legal moves to
make.

Threefold-repetition

	If the same board position occurs for three consecutive moves, then the
player could claim a 	draw. Note that the same board position need not
occur in consecutive moves. For ex: if certain 	pattern of moves are
repeated such that the board position is repeated thrice, then the
player 	could claim a draw.

 

50 Move Rule

	If no piece has been captured in 50 consecutive moves, then the player
can claim a draw.

Minimal Draw Algorithm

	If both sides have minimal pieces with which either cannot win, an
algorithm detects this and 	reports a draw.

Undo & Redo

	The Undo and Redo algorithms are exposed in a simple manner, so the
user of this project can 	request undo and redo of any number of moves
(if any).

Chess API

	The above features and some others needed by the chess AI are exposed
as an API. The API is 	given as follows:

	enum MoveResult { INVALIDMOVE, VALIDMOVE, CHECK, CHECKMATE, 

				  STALEMATE, DRAW, THREEFOLDREPETITION,

				  FIFTYMOVERULE };

	// string format: d2d4, e7e5, b1c3, etc.,

	MoveResult move(const string&);

	// pos (0, 0) & (0, 7) => black rook, (7, 0) & (7, 7) => white rook

	MoveResult move(const Move&);

	bool whiteTurn();

	const PieceID* chessBoardIterator();

	void undo(size_t nmoves = 1);

	void redo(size_t nmoves = 1);

	void pawnPromoter(PieceID (*)(PieceID));

	void recordPossibleMoves(const Position&, vector<Position>&);

	void generate_moves(vector<Move>&);

5. Approach towards Solution

5.1 Object-Oriented Design

My initial approach towards this project was an Object-Oriented
Solution. The following diagram shows part of my initial design related
to the chessmen.

		Figure 2: Part of Object Oriented Design for chessmen

I have found Object Oriented Design such as the one above constraining
to my particular project, because of the following reasons:

1)  Cost of Dynamic binding: 

I have a detailed discussion on the cost of dynamic binding in the
section ``compile-time programming''.

2) Object Model Inconsistency

 In the real-world at any time I have at most 32 pieces on the chess
board. That means even in situations like pawn promotion, a pawn is
promoted to a queen, rook, bishop or knight i.e., a Pawn object should
get converted to a Queen, etc. This is not directly possible in a
statically programming language like C++. In dynamically typed
languages, say for example Python, I could have changed the type of an
object using something like this ``pawnObject.class =  class(Queen)'',
and the pawn object starts behaving as a Queen object. To get this
support in C++, I should use some extra levels of indirection through
which I could write several solutions easily. But this approach is out
of question because I try to minimize extra run-time indirections.

Upon trying this Object Oriented solution further when implementing
undo, redo operations by using design patterns like ``memento'', I found
that a purist object-oriented approach was though giving elegant
solutions had some extra indirections, because of which I had written
some work-around solutions in non-object oriented way. This approach I
had pushed further and I had got a solution now which is a mixture of
generic, functional, procedural and object oriented paradigms.

5. 2 Compile-time Programming:

Lets see an situation in my project, in which I arrived at a good
solution using Compile-time programming. The example is as follows:

The following function is executed by a class say ``GameManager''
whenever a user or a chess AI program makes a move.

	bool moveValid(const Position& from, const Position& to);

As the declaration says, the return value is true if the move made is
valid; false otherwise.

An efficient implementation of the above function is as follows:

Solution 1:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    if (id == WROOK || id == BROOK)

	        return rookMoveValid(from, to, board);

    	    else if (id == WKNIGHT || id == BKNIGHT)

          	   return knightMoveValid(from, to, board);

    	    else if (id == WBISHOP || id == BBISHOP)

              return bishopMoveValid(from, to, board);

    	    else if (id == WQUEEN || id == BQUEEN)

		   return queenMoveValid(from, to, board);

    	    else if (id == WKING || id == BKING)

   		   return kingMoveValid(from, to, board);

    	    else if (id == WPAWN || id == BPAWN)

		   return pawnMoveValid(from, to, board);

    	    return false;

	}

The above solution is an efficient one, but it is a bad practice to
implement this way, because of the following reasons:

I need to move a piece from one position to another in a lot of
functions that means I have to duplicate the above code at many places.
We all know that code duplication should be avoided, which helps in
easier maintainability of the code.

Large if-else blocks also makes it difficult to write reusable code. For
example, ``Chinese Chess'' has one more piece ``Cannon'' in addition to
the above pieces (the names of the chessmen are different than standard
chess names). If I want to resuse my chess project to

design ``Chinese Chess'' then I got to add another ``if condition'' as
in the above code, at all

the places that has such functionality.

Solution 2: Object Oriented Solution

Here I give a solution using Object Oriented Paradigm to avoid the above
mentioned two problems.

The following is a basic Object Oriented design for the chessmen in my
project.

	class Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&) = 0;

    	    virtual void move(const Position&, Board&);

	    // other member functions and data removed for clarity.

     };

The above ``Piece''' base class specifies a contract that should be
implemented by all its derived classes i.e., all the concrete chessmen.

The concrete classes are as follows:

	class Rook : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

	class Knight : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

Similarly Bishop, Queen, King and Pawn classes.

Now the code for the ``moveValid'' function would be as follows:

	bool Board::moveValid(const Position& from, const Position& to) {

    	    Piece *p = board.piece(from);

    	    return p && p->moveValid(to, board);

   	}

The above one is an elegant solution. It is as simple as saying in plain
english, ``get a piece from a position, and ask it to move to another
posiion''.

Unlike in Solution 1, here the board object is not concerned which piece
its going to move. It is guaranteed that whatever the Piece would be,
its going to support the ``moveValid'' function. And 

through dynamic binding the big ``if-else'' block in Solution 1 is
translated into simple code.

But this clarity comes at a cost in Object Oriented world. To understand
the cost of dynamic binding lets see the object representation for a
concrete piece like ``Rook''. The layout in memory for an object of
class ``Rook'' would be as follows:

			   Figure 3: A Rook Object layout

Any classes that has virtual functions would have a virtual table (per
class) that contains the RTTI (runtime type information) and the virtual
functions. Every object of such class has a ``vptr'' (virtual table
pointer) member pointer pointing to the vtable (virtual table).

The line ``p->moveValid(to, board)'' is translated into the following
assembly code by the compiler.

	; Note: function_offset and vptr_offset known at compile time

	load [object_address + vptr_offset], reg1

	load [reg1 + function_offset], reg2

	call reg2

As seen in the above assembly code, dynamic binding does two
dereferences (one for obtaining the vtable address, and another to
obtain the appropriate function; ``moveValid'' in this case) then the
actual function call. The above code is resuable too, say if I added
another piece ``Cannon'' for chines chess, then I need to write another
class ``Cannon'' which would derive from ``Piece'', and no changes are
required for the ``moveValid'' function.

One thing to be noticed in solution 1 is that: on an average six if
conditions would be executed  before the appropriate ``xxMoveValid''
function call. But a clever compiler in the case of Solution 1 could
inline all these ``xxMoveValid'' functions, there by avoiding the
function call itself. I agree that the C++ compiler cannot inline
functions that are not simple, however, it is possible to write the code
using techniques like tighter loops, functors (functions as values), etc
which are unrolled by the compiler, and

could be inlined.

Where as in the case of Solution 2, due to dynamic binding it is
impossible to inline the functions.

Hence, even that the Solution 2 is elegant it comes with an cost (2
dereferences and actual function call), which is undesirable in this
project where I am trying to increase the execution speed of the overall
application.

Solution 3: A better solution (one less dereference):

The following is the solution I arrived at after studying the dynamic
binding (especially how virtuals work through vtables). Here I kind of
create manual vtable which is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool (*moveValid_[12])(const Position&, const Position&, const Board&) 
	=

    			{ 

        			pawnMoveValid, knightMoveValid, bishopMoveValid,   

        			rookMoveValid, queenMoveValid, kingMoveValid, 

        			pawnMoveValid, knightMoveValid, bishopMoveValid, 

        			rookMoveValid, queenMoveValid, kingMoveValid

    			};

Here ``moveValid_'' is a  array [12] of function pointers. Now the
moveValid function could be written as

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && (*moveValid_[id])(from, to, board);

	}

As can be seen from the above code, now we have one dereference to the
actual function then the actual function call.

Solution 4: Compile-time Programming

This is the final solution I created which has the same benefits as
Solution 1, and none of its draw backs. The Solution is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	typedef boost::tuple

    		<		

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

			RookMoveValid, QueenMoveValid, KingMoveValid,

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

  			RookMoveValid, QueenMoveValid, KingMoveValid

    		> TUPLE;

	TUPLE moveValidFunctors;

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && call(moveValidFunctors, id, from, to,
board);

	}

	

The above ``moveValid'' is as elegant as the Solution 2 version and as
efficient as Solution 1.

The compiler translates the line ``call(moveValidFunctors, id, from, to,
board)'' to the following big ``if-else'' block.

	return id == 11 ? KingMoveValid(from, to, board)

		: (id == 10 ? QueenMoveValid(from, to, board)

		   ... 

		: (id ==  0 ? PawnMoveValid(from, to, board)))...);

I have written this ``call'' construct using Templates and partial
Template Specialization. Note that this conversion would take at compile
time, and hence once the compiler is done, the ``call'' construct
vanishes replacing itself by the big ``if-else'' block

6. Symbian

The following are a few concepts which I thought are worth mentioning.
These topics would be explained in detail in Symbian OS or Symbian C++
books. 

Standard C++ didn't had exceptions when Symbian OS was designed
initially. After exceptions were added to standard C++ it was found that
the language techniques used to support exceptional handling 

adds a good amount of overheads to the compiled code and also some
run-time overheads, regardless of whether exceptions were actually
thrown or not. So developers of Symbian OS didn't find exception
handling suitable to Symbian C++ because they wanted the Symbian OS and
the client code to be compact. Since Symbian C++ has a different way of
dealing with memory, its lays certain restrictions on the types that we
can create. These are called T, C and R classes. T classes are ones like
the primitive ones which do not need explicit destructors, and C classes
are the ones in which the virtuals are involved, and R classes represent
the resource classes.

Leaves

A simple, good and lightweight exception handling solution called
``leaves'' was developed for Symbian OS. A leave is used to propagate an
error which occurs because of exceptional conditions (such as being out
of memory or disk space) to higher-level code which can handle it. A
Symbian OS leave is equivalent to a C++ throw and a TRAP harness is used
to catch the leave. In fact, a TRAP harness is effectively a combination
of try and catch.

TRAP and leave are analogous to the setjmp() and longjmp() methods,
respectively - setjmp() tores information about the location to be
``jumped to'' in a jump buffer, which is used by ``longjmp()'' to direct
the code to jump to that point.

Cleanup Stack

The stack memory is freed as the stack unwinds, but otherwise the stack
frame is abandoned and no object destructors are called (which is unlike
a standard C++ exception). This means the destructors of any local
variables or arguments passed by value, or objects created as member
variables of either of these, will not be called. Some objects are
``leave-safe'' - they do not need destructors and contain only data
which can be destroyed as stack memory is freed by the leave. This data
may consist of the basic, built-in types or other objects which contain
such types. In Symbian OS these are called T classes, the characteristic
of which is that they may safely be created on the stack in functions
where code may leave. If a local variable is a pointer to an object on
the heap, when a leave occurs the pointer is destroyed without freeing
that heap memory, which becomes unrecoverable, causing a memory leak.
The memory is said to be orphaned. This means that C classes objects,
which are always created on the heap are not leave safe. R class objects
are generally not leave-safe either, since the resources they own must
be freed in the event of a leave (through a call to the appropriate
Close() or Release() type function). If this call cannot made by an
object accessible after the leave, the resource is orphaned.

Various techniques are used to effectively do the cleanup activities of
resources through Cleanup Stack.

I have read and understood the above concepts and several others related
to Symbian, such as

descriptors, dynamic buffers, event-driven multitasking using Active
Objects, Symbian OS Threads and Processes, graphics for display and
interaction etc.

I have resolved several issues while I was doing the port of Ax Chess to
Symbian OS. Some of issues were lack of STL and BOOST because of which I
had to write the appropriate constructs, and since Symbian C++ compiler
is not so sophisticated as standard C++ compilers like g++, Comeau C++,
MS Visual Studio C++  compiler,etc., I had written work-arounds for the
compile-time programming techniques I have used.

7. Memory Management

This is the area that I didn't think when I submitted the this project's
proposal. But during the course of this project I found that custom
memory management would improve the performance. The following is a
discussion on why custom memory management would be helpful.

Datastructures provided by STL are used, which currently manage memory
automatically.

Internally they call new/delete for memory allocation and deallocation.
The above mentioned dynamic memory allocators/dealloactors matter when
efficieny is  concerned. For example: Each "new" operation executes a OS
call to get memory allocated from free store, and each "delete" involves
in returning the allocated memory to the free  pool. These are costly
operations. And using "new/delete"s frequently in a chess AI program is
going to cost too much.

Created a Garbage Collector, which uses Mark-Sweep (with Compaction)
Algorithm. This project is made thread-safe using POSIX Threads, Mutex,
Condition variables etc. The Garbage Collector exposes a pointer
abstraction gc_ptr<T>, which has allocation speed faster than the
standard new operator, and can be approximated to the speed of the
allocation on stack space. However,

sweep does take time to reclaim storage space occupied by out-of-scope
pointers, and also to compact the active memory under use. Conversions
between gc_ptr of base and derived types are taken care at compile-time,
which ensures compile-time type safety; avoiding any run-time safety
overhead.

By default the Garbage Collector can be used in a multi-threaded
environment, but it can be configured at compile-time as a
single-threaded one, thus removing multithread specific overhead,
unnecessary in a single-thread environment. This type of Garbage
Collector can be used in projects where heap-based

memory allocations should be very fast. For example, a chess AI program
can use this garbage collector, to build large trees (of search-worthy
moves and search the best move) during the computers turn of play, and
can reclaim the storage when it is idle i.e., during the opponents turn.
This method drastically speeds-up performance when compared to the
standard new operator that itself spends a lot of time during
allocation.

There are other garbage collection algorithms available like reference
counting, mark sweep, copying, etc. I found that the mark-sweep one
suits best to the chess AI's situtation. Because all I do care is that
the memory allocations should be very efficient, and even though the
sweep is complex and inefficient, that doesn't matter because it is
supposed to be called in the idle phase of the chess AI program.

Currently this GC isn't integrated with "Ax Chess" as I haven't finished
testing the GC.

8. Screenshots

The following are a few screenshots showing some features of the
implementation.

 

		Figure 4: Ax Chess ported to Symbian OS (S60 devices), running on
emulator

 

	

				   Figure 5: A checkmate condition.

					Figure 6: A stalemate condition

The following is a screen-shot of my character user interface that uses
the chess API; showing the steps of a simple checkmate:

Note: White pieces are represented using lower-case letters and black
pieces are in upper case letters, as can be seen using the ``draw''
command.

		

				Figure 7: CUI using the chess API

9. Submitted Code & Installation instructions

For this project, you need to have a good C++ compiler. I would
recommend g++, comeau C++ compiler or MS Visual Studio 2005 C++
compiler.

And you need to have the BOOST library installed on your system.

For installing boost, check the instructions from the boost website 

  HYPERLINK "http://www.boost.org/" http://www.boost.org/ 

or for gentoo and debian based systems, here is a simple procedure

  HYPERLINK
"http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-d
ebianubuntu/"
http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-de
bianubuntu/ 

I have hosted my project code at savannah website. The url is

  HYPERLINK "http://savannah.nongnu.org/projects/ax-chess/"
http://savannah.nongnu.org/projects/ax-chess/ 

To download the project code, use the following command:

cvs -z3 -d:pserver:anonymous@cvs.savannah.nongnu.org:/sources/ax-chess
co ax-chess

The above command would create a directory ``ax-chess'' in your present
working directory.

Type ``make'' to compile the project. And  use ``./cuigamemanager'' at
the shell prompt to test 

Ax Chess.

I am also submitting the code as a tar.gz file to the ODU CS department
as part of the MS Project requirements. The zipped file would contain
both Ax Chess project and the port of Ax Chess for Symbian OS.

10. Conclusion

This project had been a great learning experience; I am a better
programmer now. There is plenty left to do. I believe that a fresh
review of my complete code would give me some more ideas to improve it.
The following are some the concepts that I have learned.

1) Several concepts of C++. For example, few would be Internal
representation of Objects, Templates, 2) Compile-time computations,
Policy based design.

3) Idea about different programming paradigms and efficiency
considerations.

4) STL and BOOST

5) Memory Management and Garbage Collection.

6) Symbian OS Internals and Symbian C++

7) Various Tools like emacs, g++, gdb, make, cppunit, gprof, Metrowerks
CodeWarrior, etc

MS PROJECT (FALL 2006)

Ax Chess, and efficient representation of Chess targeted for a chess AI
program and a mobile device

Submitted by Azhar Ali

Project Advisor: Dr. Mohammad Zubair

ABSTRACT

	   This project, Ax Chess, is a two player chess engine/game. Most of
the features of

	   chess, such as valid moves, checkmate, stalemate, threefold
repetition, fifty move

	   rule, etc., are implemented. This project exposes a chess api that
can be integrated

	   by a gui chess interface, a mobile chess interface and/or an
artificial chess engine.

	   Design and Efficiency aspects are be studied through out the
project. And a best

	   design which would utilize memory and processor's speed efficiently
is produced;

	   suitable to low-memory devices like Series 60 Symbian Mobile Phones.

Contents

Introduction

Motivation

Technologies/Tools Used

Features of Ax Chess

Approach towards Solution

5.1 Object Oriented Design

5.2 Compile-time Programming

Symbian

Memory Management

Screenshots (Implementation's output)

Submitted Code & Installation instructions

Conclusion

1. Introduction

This project essentially consists of two phases.

Phase I: This phase solely concentrates on the implementation of Ax
Chess. 

Throughout the course of this project, I constantly tried to refine the
code to incorporate

"compile time programming" techniques, which made the code elegant,
succinct and highly

maintainable; and in turn helped the compiler to generate efficient
machine code. I had also focused

on using different programming paradigms, particularly Generic
Programming Paradigm (using

parametric polymorphism, which compared to subtype polymorphism is very
efficient), Functional

Paradigm (through which, we could avoid loops with tighter code
generation), Object Oriented

Paradigm, Procedural Paradigm etc; and evaluated the best one(s) for my
project from the perspective of both an efficient implementation for a
chess AI and also low-memory devices.

Phase II: The project code for PC would also be ported to Symbian OS,
using Symbian C++, which is

a much restricted version of Standard C++. Because of the inherent
constrained environment of a

mobile phone (when compared to PC, of course), unlike Standard C++,
Symbian C++ has a completely

different way of managing memory, exception handling, etc. The Symbian
C++ port is done considering all these aspects. And another impediment
for the port is the lack of the Standard Template

Library and the Boost Library for the Symbian environment. I had written
handcrafted versions for some of those library features.

2. Motivation

2.1 Need for an Efficient Chess Representation

To understand the need for an efficient ``chess representation'' like Ax
Chess, lets consider the

following example of how a basic chess Artificial Intelligence (AI)
program works:

The following figure (Figure 1) shows the tree of board positions
generated by a minimax algorithm after playing one move by both sides:

As we can see from the Figure 1, when the game of chess begins, white
has a choice of 20 moves. Followed by a white's move, black has 20 moves
in reply. Thus 400 different positions arise after one move by both
sides. This number grows to 20,000 after two moves and astronomically
later.

Techniques like alpha-beta search, killer heuristics, etc., are employed
to prune such trees.The way a chess AI program works is by searching the
above mentioned tree to a certain depth for both sides, and deeper along
highly tactical lines. 

It is to be noted that the chess AI consults the ``chess
representation'' at every node of the moves tree, to

get the result of the move such as checkmate, stalemate, etc. The chess
AI program uses a depth first search to traverse the above tree, so it
backtracks a lot and needs the support of undo operations from the
``chess representation''. The undo (and also redo) mechanism and the
different chess algorithms are important operations, because their
implementation's efficiency multiplies by a large factor (actually by
the number of move nodes in a chess tree), when used by chess AI.

Currently, the strongest chess playing software ``Deep Fritz 10'' can
see 18-ply (i.e., 9 moves on both sides) deep. This means that the chess
representation's functionality would be executed millions of times.

	Figure 1: Chess AI Tree generated by minimax algorithm after one move
by both sides

2.2 Why yet another one?

There are a lot of excellent chess playing softwares like Fritz,
Extreme, Crafty, etc for PC and Chess Tiger, etc., for Smart Phones. A
lot of effort is going on to improve these softwares. To get into such
development stream one needs experience like programming a simple chess
AI and understanding the real efficiency concerns which are involved in
the chess AI computations. The aim of this project is to get such
experience.

3. Technologies/Tools used

The following are the list of technologies and tools used

C++, STL, BOOST, Symbian C++

emacs, g++, gdb, make, cppunit, gprof

Symbian 8.0a SDK, Metrowerks CodeWarrior, Microsoft Visual Studio 2003

I choose C++ as my programming language, because of its flexibility. It
gives me complete control over the system, and allows me to think in
more than one paradigms

Using STL and BOOST, I got the following benefits

more efficient

better portability

concise code

better thinking process because of high level constructs

automatic memory management without sacrificing efficiency

support for custom memory allocators

etc

I used Gentoo 2.6 as my development platform, and tested it Ubuntu 6.10
and Windows XP also.

There were no portability problems.

4. Features of Ax Chess

The following are the features provided by Ax Chess:

Valid Moves for all Pieces:

	The movement algorithms for all pieces are take care of, and all things
related to them like 	enpassant, castling, pawn promotion.

Check

	A player's king is under threat.

Checkmate

	A player's king is under threat and he cannot escape that situation.

Stalemate

	A players's king is not under threat, but he has no legal moves to
make.

Threefold-repetition

	If the same board position occurs for three consecutive moves, then the
player could claim a 	draw. Note that the same board position need not
occur in consecutive moves. For ex: if certain 	pattern of moves are
repeated such that the board position is repeated thrice, then the
player 	could claim a draw.

 

50 Move Rule

	If no piece has been captured in 50 consecutive moves, then the player
can claim a draw.

Minimal Draw Algorithm

	If both sides have minimal pieces with which either cannot win, an
algorithm detects this and 	reports a draw.

Undo & Redo

	The Undo and Redo algorithms are exposed in a simple manner, so the
user of this project can 	request undo and redo of any number of moves
(if any).

Chess API

	The above features and some others needed by the chess AI are exposed
as an API. The API is 	given as follows:

	enum MoveResult { INVALIDMOVE, VALIDMOVE, CHECK, CHECKMATE, 

				  STALEMATE, DRAW, THREEFOLDREPETITION,

				  FIFTYMOVERULE };

	// string format: d2d4, e7e5, b1c3, etc.,

	MoveResult move(const string&);

	// pos (0, 0) & (0, 7) => black rook, (7, 0) & (7, 7) => white rook

	MoveResult move(const Move&);

	bool whiteTurn();

	const PieceID* chessBoardIterator();

	void undo(size_t nmoves = 1);

	void redo(size_t nmoves = 1);

	void pawnPromoter(PieceID (*)(PieceID));

	void recordPossibleMoves(const Position&, vector<Position>&);

	void generate_moves(vector<Move>&);

5. Approach towards Solution

5.1 Object-Oriented Design

My initial approach towards this project was an Object-Oriented
Solution. The following diagram shows part of my initial design related
to the chessmen.

		Figure 2: Part of Object Oriented Design for chessmen

I have found Object Oriented Design such as the one above constraining
to my particular project, because of the following reasons:

1)  Cost of Dynamic binding: 

I have a detailed discussion on the cost of dynamic binding in the
section ``compile-time programming''.

2) Object Model Inconsistency

 In the real-world at any time I have at most 32 pieces on the chess
board. That means even in situations like pawn promotion, a pawn is
promoted to a queen, rook, bishop or knight i.e., a Pawn object should
get converted to a Queen, etc. This is not directly possible in a
statically programming language like C++. In dynamically typed
languages, say for example Python, I could have changed the type of an
object using something like this ``pawnObject.class =  class(Queen)'',
and the pawn object starts behaving as a Queen object. To get this
support in C++, I should use some extra levels of indirection through
which I could write several solutions easily. But this approach is out
of question because I try to minimize extra run-time indirections.

Upon trying this Object Oriented solution further when implementing
undo, redo operations by using design patterns like ``memento'', I found
that a purist object-oriented approach was though giving elegant
solutions had some extra indirections, because of which I had written
some work-around solutions in non-object oriented way. This approach I
had pushed further and I had got a solution now which is a mixture of
generic, functional, procedural and object oriented paradigms.

5. 2 Compile-time Programming:

Lets see an situation in my project, in which I arrived at a good
solution using Compile-time programming. The example is as follows:

The following function is executed by a class say ``GameManager''
whenever a user or a chess AI program makes a move.

	bool moveValid(const Position& from, const Position& to);

As the declaration says, the return value is true if the move made is
valid; false otherwise.

An efficient implementation of the above function is as follows:

Solution 1:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    if (id == WROOK || id == BROOK)

	        return rookMoveValid(from, to, board);

    	    else if (id == WKNIGHT || id == BKNIGHT)

          	   return knightMoveValid(from, to, board);

    	    else if (id == WBISHOP || id == BBISHOP)

              return bishopMoveValid(from, to, board);

    	    else if (id == WQUEEN || id == BQUEEN)

		   return queenMoveValid(from, to, board);

    	    else if (id == WKING || id == BKING)

   		   return kingMoveValid(from, to, board);

    	    else if (id == WPAWN || id == BPAWN)

		   return pawnMoveValid(from, to, board);

    	    return false;

	}

The above solution is an efficient one, but it is a bad practice to
implement this way, because of the following reasons:

I need to move a piece from one position to another in a lot of
functions that means I have to duplicate the above code at many places.
We all know that code duplication should be avoided, which helps in
easier maintainability of the code.

Large if-else blocks also makes it difficult to write reusable code. For
example, ``Chinese Chess'' has one more piece ``Cannon'' in addition to
the above pieces (the names of the chessmen are different than standard
chess names). If I want to resuse my chess project to

design ``Chinese Chess'' then I got to add another ``if condition'' as
in the above code, at all

the places that has such functionality.

Solution 2: Object Oriented Solution

Here I give a solution using Object Oriented Paradigm to avoid the above
mentioned two problems.

The following is a basic Object Oriented design for the chessmen in my
project.

	class Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&) = 0;

    	    virtual void move(const Position&, Board&);

	    // other member functions and data removed for clarity.

     };

The above ``Piece''' base class specifies a contract that should be
implemented by all its derived classes i.e., all the concrete chessmen.

The concrete classes are as follows:

	class Rook : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

	class Knight : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

Similarly Bishop, Queen, King and Pawn classes.

Now the code for the ``moveValid'' function would be as follows:

	bool Board::moveValid(const Position& from, const Position& to) {

    	    Piece *p = board.piece(from);

    	    return p && p->moveValid(to, board);

   	}

The above one is an elegant solution. It is as simple as saying in plain
english, ``get a piece from a position, and ask it to move to another
posiion''.

Unlike in Solution 1, here the board object is not concerned which piece
its going to move. It is guaranteed that whatever the Piece would be,
its going to support the ``moveValid'' function. And 

through dynamic binding the big ``if-else'' block in Solution 1 is
translated into simple code.

But this clarity comes at a cost in Object Oriented world. To understand
the cost of dynamic binding lets see the object representation for a
concrete piece like ``Rook''. The layout in memory for an object of
class ``Rook'' would be as follows:

			   Figure 3: A Rook Object layout

Any classes that has virtual functions would have a virtual table (per
class) that contains the RTTI (runtime type information) and the virtual
functions. Every object of such class has a ``vptr'' (virtual table
pointer) member pointer pointing to the vtable (virtual table).

The line ``p->moveValid(to, board)'' is translated into the following
assembly code by the compiler.

	; Note: function_offset and vptr_offset known at compile time

	load [object_address + vptr_offset], reg1

	load [reg1 + function_offset], reg2

	call reg2

As seen in the above assembly code, dynamic binding does two
dereferences (one for obtaining the vtable address, and another to
obtain the appropriate function; ``moveValid'' in this case) then the
actual function call. The above code is resuable too, say if I added
another piece ``Cannon'' for chines chess, then I need to write another
class ``Cannon'' which would derive from ``Piece'', and no changes are
required for the ``moveValid'' function.

One thing to be noticed in solution 1 is that: on an average six if
conditions would be executed  before the appropriate ``xxMoveValid''
function call. But a clever compiler in the case of Solution 1 could
inline all these ``xxMoveValid'' functions, there by avoiding the
function call itself. I agree that the C++ compiler cannot inline
functions that are not simple, however, it is possible to write the code
using techniques like tighter loops, functors (functions as values), etc
which are unrolled by the compiler, and

could be inlined.

Where as in the case of Solution 2, due to dynamic binding it is
impossible to inline the functions.

Hence, even that the Solution 2 is elegant it comes with an cost (2
dereferences and actual function call), which is undesirable in this
project where I am trying to increase the execution speed of the overall
application.

Solution 3: A better solution (one less dereference):

The following is the solution I arrived at after studying the dynamic
binding (especially how virtuals work through vtables). Here I kind of
create manual vtable which is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool (*moveValid_[12])(const Position&, const Position&, const Board&) 
	=

    			{ 

        			pawnMoveValid, knightMoveValid, bishopMoveValid,   

        			rookMoveValid, queenMoveValid, kingMoveValid, 

        			pawnMoveValid, knightMoveValid, bishopMoveValid, 

        			rookMoveValid, queenMoveValid, kingMoveValid

    			};

Here ``moveValid_'' is a  array [12] of function pointers. Now the
moveValid function could be written as

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && (*moveValid_[id])(from, to, board);

	}

As can be seen from the above code, now we have one dereference to the
actual function then the actual function call.

Solution 4: Compile-time Programming

This is the final solution I created which has the same benefits as
Solution 1, and none of its draw backs. The Solution is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	typedef boost::tuple

    		<		

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

			RookMoveValid, QueenMoveValid, KingMoveValid,

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

  			RookMoveValid, QueenMoveValid, KingMoveValid

    		> TUPLE;

	TUPLE moveValidFunctors;

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && call(moveValidFunctors, id, from, to,
board);

	}

	

The above ``moveValid'' is as elegant as the Solution 2 version and as
efficient as Solution 1.

The compiler translates the line ``call(moveValidFunctors, id, from, to,
board)'' to the following big ``if-else'' block.

	return id == 11 ? KingMoveValid(from, to, board)

		: (id == 10 ? QueenMoveValid(from, to, board)

		   ... 

		: (id ==  0 ? PawnMoveValid(from, to, board)))...);

I have written this ``call'' construct using Templates and partial
Template Specialization. Note that this conversion would take at compile
time, and hence once the compiler is done, the ``call'' construct
vanishes replacing itself by the big ``if-else'' block

6. Symbian

The following are a few concepts which I thought are worth mentioning.
These topics would be explained in detail in Symbian OS or Symbian C++
books. 

Standard C++ didn't had exceptions when Symbian OS was designed
initially. After exceptions were added to standard C++ it was found that
the language techniques used to support exceptional handling 

adds a good amount of overheads to the compiled code and also some
run-time overheads, regardless of whether exceptions were actually
thrown or not. So developers of Symbian OS didn't find exception
handling suitable to Symbian C++ because they wanted the Symbian OS and
the client code to be compact. Since Symbian C++ has a different way of
dealing with memory, its lays certain restrictions on the types that we
can create. These are called T, C and R classes. T classes are ones like
the primitive ones which do not need explicit destructors, and C classes
are the ones in which the virtuals are involved, and R classes represent
the resource classes.

Leaves

A simple, good and lightweight exception handling solution called
``leaves'' was developed for Symbian OS. A leave is used to propagate an
error which occurs because of exceptional conditions (such as being out
of memory or disk space) to higher-level code which can handle it. A
Symbian OS leave is equivalent to a C++ throw and a TRAP harness is used
to catch the leave. In fact, a TRAP harness is effectively a combination
of try and catch.

TRAP and leave are analogous to the setjmp() and longjmp() methods,
respectively - setjmp() tores information about the location to be
``jumped to'' in a jump buffer, which is used by ``longjmp()'' to direct
the code to jump to that point.

Cleanup Stack

The stack memory is freed as the stack unwinds, but otherwise the stack
frame is abandoned and no object destructors are called (which is unlike
a standard C++ exception). This means the destructors of any local
variables or arguments passed by value, or objects created as member
variables of either of these, will not be called. Some objects are
``leave-safe'' - they do not need destructors and contain only data
which can be destroyed as stack memory is freed by the leave. This data
may consist of the basic, built-in types or other objects which contain
such types. In Symbian OS these are called T classes, the characteristic
of which is that they may safely be created on the stack in functions
where code may leave. If a local variable is a pointer to an object on
the heap, when a leave occurs the pointer is destroyed without freeing
that heap memory, which becomes unrecoverable, causing a memory leak.
The memory is said to be orphaned. This means that C classes objects,
which are always created on the heap are not leave safe. R class objects
are generally not leave-safe either, since the resources they own must
be freed in the event of a leave (through a call to the appropriate
Close() or Release() type function). If this call cannot made by an
object accessible after the leave, the resource is orphaned.

Various techniques are used to effectively do the cleanup activities of
resources through Cleanup Stack.

I have read and understood the above concepts and several others related
to Symbian, such as

descriptors, dynamic buffers, event-driven multitasking using Active
Objects, Symbian OS Threads and Processes, graphics for display and
interaction etc.

I have resolved several issues while I was doing the port of Ax Chess to
Symbian OS. Some of issues were lack of STL and BOOST because of which I
had to write the appropriate constructs, and since Symbian C++ compiler
is not so sophisticated as standard C++ compilers like g++, Comeau C++,
MS Visual Studio C++  compiler,etc., I had written work-arounds for the
compile-time programming techniques I have used.

7. Memory Management

This is the area that I didn't think when I submitted the this project's
proposal. But during the course of this project I found that custom
memory management would improve the performance. The following is a
discussion on why custom memory management would be helpful.

Datastructures provided by STL are used, which currently manage memory
automatically.

Internally they call new/delete for memory allocation and deallocation.
The above mentioned dynamic memory allocators/dealloactors matter when
efficieny is  concerned. For example: Each "new" operation executes a OS
call to get memory allocated from free store, and each "delete" involves
in returning the allocated memory to the free  pool. These are costly
operations. And using "new/delete"s frequently in a chess AI program is
going to cost too much.

Created a Garbage Collector, which uses Mark-Sweep (with Compaction)
Algorithm. This project is made thread-safe using POSIX Threads, Mutex,
Condition variables etc. The Garbage Collector exposes a pointer
abstraction gc_ptr<T>, which has allocation speed faster than the
standard new operator, and can be approximated to the speed of the
allocation on stack space. However,

sweep does take time to reclaim storage space occupied by out-of-scope
pointers, and also to compact the active memory under use. Conversions
between gc_ptr of base and derived types are taken care at compile-time,
which ensures compile-time type safety; avoiding any run-time safety
overhead.

By default the Garbage Collector can be used in a multi-threaded
environment, but it can be configured at compile-time as a
single-threaded one, thus removing multithread specific overhead,
unnecessary in a single-thread environment. This type of Garbage
Collector can be used in projects where heap-based

memory allocations should be very fast. For example, a chess AI program
can use this garbage collector, to build large trees (of search-worthy
moves and search the best move) during the computers turn of play, and
can reclaim the storage when it is idle i.e., during the opponents turn.
This method drastically speeds-up performance when compared to the
standard new operator that itself spends a lot of time during
allocation.

There are other garbage collection algorithms available like reference
counting, mark sweep, copying, etc. I found that the mark-sweep one
suits best to the chess AI's situtation. Because all I do care is that
the memory allocations should be very efficient, and even though the
sweep is complex and inefficient, that doesn't matter because it is
supposed to be called in the idle phase of the chess AI program.

Currently this GC isn't integrated with "Ax Chess" as I haven't finished
testing the GC.

8. Screenshots

The following are a few screenshots showing some features of the
implementation.

 

		Figure 4: Ax Chess ported to Symbian OS (S60 devices), running on
emulator

 

	

				   Figure 5: A checkmate condition.

					Figure 6: A stalemate condition

The following is a screen-shot of my character user interface that uses
the chess API; showing the steps of a simple checkmate:

Note: White pieces are represented using lower-case letters and black
pieces are in upper case letters, as can be seen using the ``draw''
command.

		

				Figure 7: CUI using the chess API

9. Submitted Code & Installation instructions

For this project, you need to have a good C++ compiler. I would
recommend g++, comeau C++ compiler or MS Visual Studio 2005 C++
compiler.

And you need to have the BOOST library installed on your system.

For installing boost, check the instructions from the boost website 

  HYPERLINK "http://www.boost.org/" http://www.boost.org/ 

or for gentoo and debian based systems, here is a simple procedure

  HYPERLINK
"http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-d
ebianubuntu/"
http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-de
bianubuntu/ 

I have hosted my project code at savannah website. The url is

  HYPERLINK "http://savannah.nongnu.org/projects/ax-chess/"
http://savannah.nongnu.org/projects/ax-chess/ 

To download the project code, use the following command:

cvs -z3 -d:pserver:anonymous@cvs.savannah.nongnu.org:/sources/ax-chess
co ax-chess

The above command would create a directory ``ax-chess'' in your present
working directory.

Type ``make'' to compile the project. And  use ``./cuigamemanager'' at
the shell prompt to test 

Ax Chess.

I am also submitting the code as a tar.gz file to the ODU CS department
as part of the MS Project requirements. The zipped file would contain
both Ax Chess project and the port of Ax Chess for Symbian OS.

10. Conclusion

This project had been a great learning experience; I am a better
programmer now. There is plenty left to do. I believe that a fresh
review of my complete code would give me some more ideas to improve it.
The following are some the concepts that I have learned.

1) Several concepts of C++. For example, few would be Internal
representation of Objects, Templates, 2) Compile-time computations,
Policy based design.

3) Idea about different programming paradigms and efficiency
considerations.

4) STL and BOOST

5) Memory Management and Garbage Collection.

6) Symbian OS Internals and Symbian C++

7) Various Tools like emacs, g++, gdb, make, cppunit, gprof, Metrowerks
CodeWarrior, etc

MS PROJECT (FALL 2006)

Ax Chess, and efficient representation of Chess targeted for a chess AI
program and a mobile device

Submitted by Azhar Ali

Project Advisor: Dr. Mohammad Zubair

ABSTRACT

	   This project, Ax Chess, is a two player chess engine/game. Most of
the features of

	   chess, such as valid moves, checkmate, stalemate, threefold
repetition, fifty move

	   rule, etc., are implemented. This project exposes a chess api that
can be integrated

	   by a gui chess interface, a mobile chess interface and/or an
artificial chess engine.

	   Design and Efficiency aspects are be studied through out the
project. And a best

	   design which would utilize memory and processor's speed efficiently
is produced;

	   suitable to low-memory devices like Series 60 Symbian Mobile Phones.

Contents

Introduction

Motivation

Technologies/Tools Used

Features of Ax Chess

Approach towards Solution

5.1 Object Oriented Design

5.2 Compile-time Programming

Symbian

Memory Management

Screenshots (Implementation's output)

Submitted Code & Installation instructions

Conclusion

1. Introduction

This project essentially consists of two phases.

Phase I: This phase solely concentrates on the implementation of Ax
Chess. 

Throughout the course of this project, I constantly tried to refine the
code to incorporate

"compile time programming" techniques, which made the code elegant,
succinct and highly

maintainable; and in turn helped the compiler to generate efficient
machine code. I had also focused

on using different programming paradigms, particularly Generic
Programming Paradigm (using

parametric polymorphism, which compared to subtype polymorphism is very
efficient), Functional

Paradigm (through which, we could avoid loops with tighter code
generation), Object Oriented

Paradigm, Procedural Paradigm etc; and evaluated the best one(s) for my
project from the perspective of both an efficient implementation for a
chess AI and also low-memory devices.

Phase II: The project code for PC would also be ported to Symbian OS,
using Symbian C++, which is

a much restricted version of Standard C++. Because of the inherent
constrained environment of a

mobile phone (when compared to PC, of course), unlike Standard C++,
Symbian C++ has a completely

different way of managing memory, exception handling, etc. The Symbian
C++ port is done considering all these aspects. And another impediment
for the port is the lack of the Standard Template

Library and the Boost Library for the Symbian environment. I had written
handcrafted versions for some of those library features.

2. Motivation

2.1 Need for an Efficient Chess Representation

To understand the need for an efficient ``chess representation'' like Ax
Chess, lets consider the

following example of how a basic chess Artificial Intelligence (AI)
program works:

The following figure (Figure 1) shows the tree of board positions
generated by a minimax algorithm after playing one move by both sides:

As we can see from the Figure 1, when the game of chess begins, white
has a choice of 20 moves. Followed by a white's move, black has 20 moves
in reply. Thus 400 different positions arise after one move by both
sides. This number grows to 20,000 after two moves and astronomically
later.

Techniques like alpha-beta search, killer heuristics, etc., are employed
to prune such trees.The way a chess AI program works is by searching the
above mentioned tree to a certain depth for both sides, and deeper along
highly tactical lines. 

It is to be noted that the chess AI consults the ``chess
representation'' at every node of the moves tree, to

get the result of the move such as checkmate, stalemate, etc. The chess
AI program uses a depth first search to traverse the above tree, so it
backtracks a lot and needs the support of undo operations from the
``chess representation''. The undo (and also redo) mechanism and the
different chess algorithms are important operations, because their
implementation's efficiency multiplies by a large factor (actually by
the number of move nodes in a chess tree), when used by chess AI.

Currently, the strongest chess playing software ``Deep Fritz 10'' can
see 18-ply (i.e., 9 moves on both sides) deep. This means that the chess
representation's functionality would be executed millions of times.

	Figure 1: Chess AI Tree generated by minimax algorithm after one move
by both sides

2.2 Why yet another one?

There are a lot of excellent chess playing softwares like Fritz,
Extreme, Crafty, etc for PC and Chess Tiger, etc., for Smart Phones. A
lot of effort is going on to improve these softwares. To get into such
development stream one needs experience like programming a simple chess
AI and understanding the real efficiency concerns which are involved in
the chess AI computations. The aim of this project is to get such
experience.

3. Technologies/Tools used

The following are the list of technologies and tools used

C++, STL, BOOST, Symbian C++

emacs, g++, gdb, make, cppunit, gprof

Symbian 8.0a SDK, Metrowerks CodeWarrior, Microsoft Visual Studio 2003

I choose C++ as my programming language, because of its flexibility. It
gives me complete control over the system, and allows me to think in
more than one paradigms

Using STL and BOOST, I got the following benefits

more efficient

better portability

concise code

better thinking process because of high level constructs

automatic memory management without sacrificing efficiency

support for custom memory allocators

etc

I used Gentoo 2.6 as my development platform, and tested it Ubuntu 6.10
and Windows XP also.

There were no portability problems.

4. Features of Ax Chess

The following are the features provided by Ax Chess:

Valid Moves for all Pieces:

	The movement algorithms for all pieces are take care of, and all things
related to them like 	enpassant, castling, pawn promotion.

Check

	A player's king is under threat.

Checkmate

	A player's king is under threat and he cannot escape that situation.

Stalemate

	A players's king is not under threat, but he has no legal moves to
make.

Threefold-repetition

	If the same board position occurs for three consecutive moves, then the
player could claim a 	draw. Note that the same board position need not
occur in consecutive moves. For ex: if certain 	pattern of moves are
repeated such that the board position is repeated thrice, then the
player 	could claim a draw.

 

50 Move Rule

	If no piece has been captured in 50 consecutive moves, then the player
can claim a draw.

Minimal Draw Algorithm

	If both sides have minimal pieces with which either cannot win, an
algorithm detects this and 	reports a draw.

Undo & Redo

	The Undo and Redo algorithms are exposed in a simple manner, so the
user of this project can 	request undo and redo of any number of moves
(if any).

Chess API

	The above features and some others needed by the chess AI are exposed
as an API. The API is 	given as follows:

	enum MoveResult { INVALIDMOVE, VALIDMOVE, CHECK, CHECKMATE, 

				  STALEMATE, DRAW, THREEFOLDREPETITION,

				  FIFTYMOVERULE };

	// string format: d2d4, e7e5, b1c3, etc.,

	MoveResult move(const string&);

	// pos (0, 0) & (0, 7) => black rook, (7, 0) & (7, 7) => white rook

	MoveResult move(const Move&);

	bool whiteTurn();

	const PieceID* chessBoardIterator();

	void undo(size_t nmoves = 1);

	void redo(size_t nmoves = 1);

	void pawnPromoter(PieceID (*)(PieceID));

	void recordPossibleMoves(const Position&, vector<Position>&);

	void generate_moves(vector<Move>&);

5. Approach towards Solution

5.1 Object-Oriented Design

My initial approach towards this project was an Object-Oriented
Solution. The following diagram shows part of my initial design related
to the chessmen.

		Figure 2: Part of Object Oriented Design for chessmen

I have found Object Oriented Design such as the one above constraining
to my particular project, because of the following reasons:

1)  Cost of Dynamic binding: 

I have a detailed discussion on the cost of dynamic binding in the
section ``compile-time programming''.

2) Object Model Inconsistency

 In the real-world at any time I have at most 32 pieces on the chess
board. That means even in situations like pawn promotion, a pawn is
promoted to a queen, rook, bishop or knight i.e., a Pawn object should
get converted to a Queen, etc. This is not directly possible in a
statically programming language like C++. In dynamically typed
languages, say for example Python, I could have changed the type of an
object using something like this ``pawnObject.class =  class(Queen)'',
and the pawn object starts behaving as a Queen object. To get this
support in C++, I should use some extra levels of indirection through
which I could write several solutions easily. But this approach is out
of question because I try to minimize extra run-time indirections.

Upon trying this Object Oriented solution further when implementing
undo, redo operations by using design patterns like ``memento'', I found
that a purist object-oriented approach was though giving elegant
solutions had some extra indirections, because of which I had written
some work-around solutions in non-object oriented way. This approach I
had pushed further and I had got a solution now which is a mixture of
generic, functional, procedural and object oriented paradigms.

5. 2 Compile-time Programming:

Lets see an situation in my project, in which I arrived at a good
solution using Compile-time programming. The example is as follows:

The following function is executed by a class say ``GameManager''
whenever a user or a chess AI program makes a move.

	bool moveValid(const Position& from, const Position& to);

As the declaration says, the return value is true if the move made is
valid; false otherwise.

An efficient implementation of the above function is as follows:

Solution 1:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    if (id == WROOK || id == BROOK)

	        return rookMoveValid(from, to, board);

    	    else if (id == WKNIGHT || id == BKNIGHT)

          	   return knightMoveValid(from, to, board);

    	    else if (id == WBISHOP || id == BBISHOP)

              return bishopMoveValid(from, to, board);

    	    else if (id == WQUEEN || id == BQUEEN)

		   return queenMoveValid(from, to, board);

    	    else if (id == WKING || id == BKING)

   		   return kingMoveValid(from, to, board);

    	    else if (id == WPAWN || id == BPAWN)

		   return pawnMoveValid(from, to, board);

    	    return false;

	}

The above solution is an efficient one, but it is a bad practice to
implement this way, because of the following reasons:

I need to move a piece from one position to another in a lot of
functions that means I have to duplicate the above code at many places.
We all know that code duplication should be avoided, which helps in
easier maintainability of the code.

Large if-else blocks also makes it difficult to write reusable code. For
example, ``Chinese Chess'' has one more piece ``Cannon'' in addition to
the above pieces (the names of the chessmen are different than standard
chess names). If I want to resuse my chess project to

design ``Chinese Chess'' then I got to add another ``if condition'' as
in the above code, at all

the places that has such functionality.

Solution 2: Object Oriented Solution

Here I give a solution using Object Oriented Paradigm to avoid the above
mentioned two problems.

The following is a basic Object Oriented design for the chessmen in my
project.

	class Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&) = 0;

    	    virtual void move(const Position&, Board&);

	    // other member functions and data removed for clarity.

     };

The above ``Piece''' base class specifies a contract that should be
implemented by all its derived classes i.e., all the concrete chessmen.

The concrete classes are as follows:

	class Rook : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

	class Knight : public Piece {

	 public:

    	    Piece(Color, const Position&);

 	

    	    virtual bool moveValid(const Position&, const Board&);

    	    virtual void move(const Position&, Board&);

     };

Similarly Bishop, Queen, King and Pawn classes.

Now the code for the ``moveValid'' function would be as follows:

	bool Board::moveValid(const Position& from, const Position& to) {

    	    Piece *p = board.piece(from);

    	    return p && p->moveValid(to, board);

   	}

The above one is an elegant solution. It is as simple as saying in plain
english, ``get a piece from a position, and ask it to move to another
posiion''.

Unlike in Solution 1, here the board object is not concerned which piece
its going to move. It is guaranteed that whatever the Piece would be,
its going to support the ``moveValid'' function. And 

through dynamic binding the big ``if-else'' block in Solution 1 is
translated into simple code.

But this clarity comes at a cost in Object Oriented world. To understand
the cost of dynamic binding lets see the object representation for a
concrete piece like ``Rook''. The layout in memory for an object of
class ``Rook'' would be as follows:

			   Figure 3: A Rook Object layout

Any classes that has virtual functions would have a virtual table (per
class) that contains the RTTI (runtime type information) and the virtual
functions. Every object of such class has a ``vptr'' (virtual table
pointer) member pointer pointing to the vtable (virtual table).

The line ``p->moveValid(to, board)'' is translated into the following
assembly code by the compiler.

	; Note: function_offset and vptr_offset known at compile time

	load [object_address + vptr_offset], reg1

	load [reg1 + function_offset], reg2

	call reg2

As seen in the above assembly code, dynamic binding does two
dereferences (one for obtaining the vtable address, and another to
obtain the appropriate function; ``moveValid'' in this case) then the
actual function call. The above code is resuable too, say if I added
another piece ``Cannon'' for chines chess, then I need to write another
class ``Cannon'' which would derive from ``Piece'', and no changes are
required for the ``moveValid'' function.

One thing to be noticed in solution 1 is that: on an average six if
conditions would be executed  before the appropriate ``xxMoveValid''
function call. But a clever compiler in the case of Solution 1 could
inline all these ``xxMoveValid'' functions, there by avoiding the
function call itself. I agree that the C++ compiler cannot inline
functions that are not simple, however, it is possible to write the code
using techniques like tighter loops, functors (functions as values), etc
which are unrolled by the compiler, and

could be inlined.

Where as in the case of Solution 2, due to dynamic binding it is
impossible to inline the functions.

Hence, even that the Solution 2 is elegant it comes with an cost (2
dereferences and actual function call), which is undesirable in this
project where I am trying to increase the execution speed of the overall
application.

Solution 3: A better solution (one less dereference):

The following is the solution I arrived at after studying the dynamic
binding (especially how virtuals work through vtables). Here I kind of
create manual vtable which is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	bool (*moveValid_[12])(const Position&, const Position&, const Board&) 
	=

    			{ 

        			pawnMoveValid, knightMoveValid, bishopMoveValid,   

        			rookMoveValid, queenMoveValid, kingMoveValid, 

        			pawnMoveValid, knightMoveValid, bishopMoveValid, 

        			rookMoveValid, queenMoveValid, kingMoveValid

    			};

Here ``moveValid_'' is a  array [12] of function pointers. Now the
moveValid function could be written as

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && (*moveValid_[id])(from, to, board);

	}

As can be seen from the above code, now we have one dereference to the
actual function then the actual function call.

Solution 4: Compile-time Programming

This is the final solution I created which has the same benefits as
Solution 1, and none of its draw backs. The Solution is as follows:

 	enum PieceID {WPAWN, WKNIGHT, WBISHOP, WROOK, WQUEEN, WKING,

	     	         BPAWN, BKNIGHT, BBISHOP, BROOK, BQUEEN, BKING, NONE};

	typedef boost::tuple

    		<		

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

			RookMoveValid, QueenMoveValid, KingMoveValid,

			PawnMoveValid, KnightMoveValid, BishopMoveValid,

  			RookMoveValid, QueenMoveValid, KingMoveValid

    		> TUPLE;

	TUPLE moveValidFunctors;

	bool moveValid(const Position& from, const Position& to) {

    	    PieceID id = board.piece(from);

    	    return id != NONE && call(moveValidFunctors, id, from, to,
board);

	}

	

The above ``moveValid'' is as elegant as the Solution 2 version and as
efficient as Solution 1.

The compiler translates the line ``call(moveValidFunctors, id, from, to,
board)'' to the following big ``if-else'' block.

	return id == 11 ? KingMoveValid(from, to, board)

		: (id == 10 ? QueenMoveValid(from, to, board)

		   ... 

		: (id ==  0 ? PawnMoveValid(from, to, board)))...);

I have written this ``call'' construct using Templates and partial
Template Specialization. Note that this conversion would take at compile
time, and hence once the compiler is done, the ``call'' construct
vanishes replacing itself by the big ``if-else'' block

6. Symbian

The following are a few concepts which I thought are worth mentioning.
These topics would be explained in detail in Symbian OS or Symbian C++
books. 

Standard C++ didn't had exceptions when Symbian OS was designed
initially. After exceptions were added to standard C++ it was found that
the language techniques used to support exceptional handling 

adds a good amount of overheads to the compiled code and also some
run-time overheads, regardless of whether exceptions were actually
thrown or not. So developers of Symbian OS didn't find exception
handling suitable to Symbian C++ because they wanted the Symbian OS and
the client code to be compact. Since Symbian C++ has a different way of
dealing with memory, its lays certain restrictions on the types that we
can create. These are called T, C and R classes. T classes are ones like
the primitive ones which do not need explicit destructors, and C classes
are the ones in which the virtuals are involved, and R classes represent
the resource classes.

Leaves

A simple, good and lightweight exception handling solution called
``leaves'' was developed for Symbian OS. A leave is used to propagate an
error which occurs because of exceptional conditions (such as being out
of memory or disk space) to higher-level code which can handle it. A
Symbian OS leave is equivalent to a C++ throw and a TRAP harness is used
to catch the leave. In fact, a TRAP harness is effectively a combination
of try and catch.

TRAP and leave are analogous to the setjmp() and longjmp() methods,
respectively - setjmp() tores information about the location to be
``jumped to'' in a jump buffer, which is used by ``longjmp()'' to direct
the code to jump to that point.

Cleanup Stack

The stack memory is freed as the stack unwinds, but otherwise the stack
frame is abandoned and no object destructors are called (which is unlike
a standard C++ exception). This means the destructors of any local
variables or arguments passed by value, or objects created as member
variables of either of these, will not be called. Some objects are
``leave-safe'' - they do not need destructors and contain only data
which can be destroyed as stack memory is freed by the leave. This data
may consist of the basic, built-in types or other objects which contain
such types. In Symbian OS these are called T classes, the characteristic
of which is that they may safely be created on the stack in functions
where code may leave. If a local variable is a pointer to an object on
the heap, when a leave occurs the pointer is destroyed without freeing
that heap memory, which becomes unrecoverable, causing a memory leak.
The memory is said to be orphaned. This means that C classes objects,
which are always created on the heap are not leave safe. R class objects
are generally not leave-safe either, since the resources they own must
be freed in the event of a leave (through a call to the appropriate
Close() or Release() type function). If this call cannot made by an
object accessible after the leave, the resource is orphaned.

Various techniques are used to effectively do the cleanup activities of
resources through Cleanup Stack.

I have read and understood the above concepts and several others related
to Symbian, such as

descriptors, dynamic buffers, event-driven multitasking using Active
Objects, Symbian OS Threads and Processes, graphics for display and
interaction etc.

I have resolved several issues while I was doing the port of Ax Chess to
Symbian OS. Some of issues were lack of STL and BOOST because of which I
had to write the appropriate constructs, and since Symbian C++ compiler
is not so sophisticated as standard C++ compilers like g++, Comeau C++,
MS Visual Studio C++  compiler,etc., I had written work-arounds for the
compile-time programming techniques I have used.

7. Memory Management

This is the area that I didn't think when I submitted the this project's
proposal. But during the course of this project I found that custom
memory management would improve the performance. The following is a
discussion on why custom memory management would be helpful.

Datastructures provided by STL are used, which currently manage memory
automatically.

Internally they call new/delete for memory allocation and deallocation.
The above mentioned dynamic memory allocators/dealloactors matter when
efficieny is  concerned. For example: Each "new" operation executes a OS
call to get memory allocated from free store, and each "delete" involves
in returning the allocated memory to the free  pool. These are costly
operations. And using "new/delete"s frequently in a chess AI program is
going to cost too much.

Created a Garbage Collector, which uses Mark-Sweep (with Compaction)
Algorithm. This project is made thread-safe using POSIX Threads, Mutex,
Condition variables etc. The Garbage Collector exposes a pointer
abstraction gc_ptr<T>, which has allocation speed faster than the
standard new operator, and can be approximated to the speed of the
allocation on stack space. However,

sweep does take time to reclaim storage space occupied by out-of-scope
pointers, and also to compact the active memory under use. Conversions
between gc_ptr of base and derived types are taken care at compile-time,
which ensures compile-time type safety; avoiding any run-time safety
overhead.

By default the Garbage Collector can be used in a multi-threaded
environment, but it can be configured at compile-time as a
single-threaded one, thus removing multithread specific overhead,
unnecessary in a single-thread environment. This type of Garbage
Collector can be used in projects where heap-based

memory allocations should be very fast. For example, a chess AI program
can use this garbage collector, to build large trees (of search-worthy
moves and search the best move) during the computers turn of play, and
can reclaim the storage when it is idle i.e., during the opponents turn.
This method drastically speeds-up performance when compared to the
standard new operator that itself spends a lot of time during
allocation.

There are other garbage collection algorithms available like reference
counting, mark sweep, copying, etc. I found that the mark-sweep one
suits best to the chess AI's situtation. Because all I do care is that
the memory allocations should be very efficient, and even though the
sweep is complex and inefficient, that doesn't matter because it is
supposed to be called in the idle phase of the chess AI program.

Currently this GC isn't integrated with "Ax Chess" as I haven't finished
testing the GC.

8. Screenshots

The following are a few screenshots showing some features of the
implementation.

 

		Figure 4: Ax Chess ported to Symbian OS (S60 devices), running on
emulator

 

	

				   Figure 5: A checkmate condition.

					Figure 6: A stalemate condition

The following is a screen-shot of my character user interface that uses
the chess API; showing the steps of a simple checkmate:

Note: White pieces are represented using lower-case letters and black
pieces are in upper case letters, as can be seen using the ``draw''
command.

		

				Figure 7: CUI using the chess API

9. Submitted Code & Installation instructions

For this project, you need to have a good C++ compiler. I would
recommend g++, comeau C++ compiler or MS Visual Studio 2005 C++
compiler.

And you need to have the BOOST library installed on your system.

For installing boost, check the instructions from the boost website 

  HYPERLINK "http://www.boost.org/" http://www.boost.org/ 

or for gentoo and debian based systems, here is a simple procedure

  HYPERLINK
"http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-d
ebianubuntu/"
http://beans.seartipy.com/2006/03/15/installing-c-boost-on-gentoo-and-de
bianubuntu/ 

I have hosted my project code at savannah website. The url is

  HYPERLINK "http://savannah.nongnu.org/projects/ax-chess/"
http://savannah.nongnu.org/projects/ax-chess/ 

To download the project code, use the following command:

cvs -z3 -d:pserver:anonymous@cvs.savannah.nongnu.org:/sources/ax-chess
co ax-chess

The above command would create a directory ``ax-chess'' in your present
working directory.

Type ``make'' to compile the project. And  use ``./cuigamemanager'' at
the shell prompt to test 

Ax Chess.

I am also submitting the code as a tar.gz file to the ODU CS department
as part of the MS Project requirements. The zipped file would contain
both Ax Chess project and the port of Ax Chess for Symbian OS.

10. Conclusion

This project had been a great learning experience; I am a better
programmer now. There is plenty left to do. I believe that a fresh
review of my complete code would give me some more ideas to improve it.
The following are some the concepts that I have learned.

1) Several concepts of C++. For example, few would be Internal
representation of Objects, Templates, 2) Compile-time computations,
Policy based design.

3) Idea about different programming paradigms and efficiency
considerations.

4) STL and BOOST

5) Memory Management and Garbage Collection.

6) Symbian OS Internals and Symbian C++

7) Various Tools like emacs, g++, gdb, make, cppunit, gprof, Metrowerks
CodeWarrior, etc