3D Chess (openGL) with Artificial Intelligence

• Download demo - 3.05 MB
• Download source - 3.08 MB

Introduction

Chess is a two-player game of strategy in which players take turns trying check the opponent's King. On each turn, a player must move one of his pieces. Each piece has a particular way of moving over the board of 64 squares of alternate black & white ones. For further rules of the game, visit the chess article on Wikipedia.

Background

The chess game has been developed in mainly 5 stages:

1. Board Representation: Two unsigned int numbers are used to represent the board since the compiler is 32 bit. A class having all the functions of 64 bit has been made by overloading all the required operators.
2. Move Generation: All the different pieces' possible moves have been precalculated and stored in bitboard. The calculation becomes easy as it requires only shift operations.
3. Evaluation function: Points have been allotted to the pieces and for protecting & attacking an opponent's piece. Points for checking and checkmating the king are allotted.
4. Depth Searching: Adding evaluation function was not enough, thinking in depth was required, Minmax tree was implemented.
5. End game: The possible moves that led itself to king check were blocked and the condition for checkmate was implemented so that the game could end.

Using the Code

The class defines a bit board which comprises two U32 numbers. This makes a board of 64 bits. All the bitwise operators are overloaded so as to work with two 32 bit numbers.

class U64 
{ 
public: 
    U32 l, h;
    U64()
    {  
        l = 0x0; 
        h = 0x0; 
    }

    U64 operator |(U64); 
    U64 operator &(U64); 
    U64 operator ^(U64); 
    U64 operator ~(void); 
    U64 operator <<(int a); 
    U64 operator >>(int b); 
    void operator =(int sq); 
    void operator |=(int sq); 
 
    void display(); 
    int getAndClearLSB(); 

    bool check(){ 
        if( !( l | h) ) 
            return false; 
        else 
            return true; 
    }  
};

The class defining bitboard of various pieces also defines various boards that are precalculated and stored such as possible moves. The constructor declares the initial status of all the bitboards of various pieces.

class CBoard {

public:   

    int side; 
    U64 Pieces[2][7]; 
    U64 Knightsmove[64]; 
    U64 Kingmove[64]; 
    U64 right_board[64]; 
    U64 left_board[64]; 
    U64 up_board[64]; 
    U64 down_board[64]; 
    U64 _45deg_board[64]; 
    U64 _225deg_board[64]; 
    U64 _135deg_board[64]; 
    U64 _315deg_board[64]; 
    U64 Pawnsmove[64][2]; 
    U64 Pawnsdoublemove[64][2]; 
    U64 Pawnsattackmove[64][2]; 
    U64 fullboard[2]; 
    U64 occupiedboard[2]; 
    U64 unoccupiedboard[2]; 
    U64 enemyboard[2]; 
    U64 notfriendlyboard[2]; 
    U64 friendlyboard[2]; 
    U64 attackboard[2]; 
    U64 doubledpawn[2]; 
    U64 isolatedpawn[2]; 
    U64 backwardpawn[2]; 
    U64 kngchk[7]; 

    void validmove();
    CBoard(); 
}bitboard;

I would like to demonstrate the generation of rook's possible moves using bit shift operations. First, precalculate the following bitboards:

• right_board[64] - A bitboard for every square with all squares to the right of the square set
• left_board[64] - A bitboard for every square with all squares to the left of the square set
• up_board[64] - A bitboard for every square with all squares above the square set
• down_board[64] - A bitboard for every square with all squares below the square set

To calculate the squares to the right where the rook can move to, we do the following:

//right_moves = right_board[sq] AND occupiedboard

We do this because the first piece will stop the rook moving to the right. Because the first piece will stop the rook, we need to fill in all the squares to the right of the piece (<< 1 means shift left one, < 2 means shift left 2, etc):

right_moves = (right_moves<<1) OR (right_moves<<2) OR (right_moves<<3) OR 
(right_moves<<4) OR (right_moves<<5) OR (right_moves<<6)

To get rid of the bits that overflowed to the next row, we AND the result with right_board:

right_moves = right_moves AND right_board

This is all the squares to the right where the rook can't move to. To get the squares where the rook can move to, we exclusive OR the board with right_board:

right_moves = right_moves XOR right_board

You will notice that that all the squares to the right of the rook where it can move to. But what if the pawn on F3 was a black pawn? Then we can't capture it, thus we need one last operation: right_moves = right moves AND enemy_and_empty_squares.

inline U64 genRookAttackBoard(int sq)
{     
    bool side=bitboard.side;
    U64 leftboard = (bitboard.occupiedboard[side] & bitboard.left_board[sq]); 
    leftboard = (leftboard>>1)|(leftboard>>2)|(leftboard>>3)|
	(leftboard>>4)|(leftboard>>5)|(leftboard>>6); 
    leftboard = (leftboard & bitboard.left_board[sq])^bitboard.left_board[sq]; 
 
    U64 rightboard = (bitboard.occupiedboard[side] & bitboard.right_board[sq]); 
    rightboard = (rightboard<<1)|(rightboard<<2)|(rightboard<<3)|
                 (rightboard<<4)|(rightboard<<5)|(rightboard<<6); 
    rightboard = (rightboard & bitboard.right_board[sq]) ^ bitboard.right_board[sq]; 
 
    U64 upboard = (bitboard.occupiedboard[side] & bitboard.up_board[sq]); 
    upboard = (upboard<<8)|(upboard<<16)|(upboard<<24)|
              (upboard<<32)|(upboard<<40)|(upboard<<48); 
    upboard = (upboard & bitboard.up_board[sq]) ^ bitboard.up_board[sq]; 

    U64 downboard = (bitboard.occupiedboard[side] & bitboard.down_board[sq]); 
    downboard = (downboard>>8)|(downboard>>16)|(downboard>>24)|
                (downboard>>32)|(downboard>>40)|(downboard>>48); 
    downboard = (downboard & bitboard.down_board[sq]) ^ bitboard.down_board[sq]; 

    return (leftboard | rightboard | upboard | downboard) & 
	bitboard.notfriendlyboard[side]; 
}