Chess program!

[JLBorges]

> how would I use this bitset to represent all I need to?

Eventually you would probably decide use more than one representation for a chess position.

The idea of a bitboard is this: each of the 64 squares are represented by one bit in a bitset. The square may be empty (false/0) or contain a piece (true/1). The square may contain any one of 12 different types of pieces (white, black) x (King, Queen, Bishop, Knight, Rook, Pawn) - so we need 12 bitsets, one for each piece type, adding up to 768 bits in all.

for example (just for exposition):

struct bitboard
{
    enum { N = 8 } ;
    typedef std::bitset<N*N> bitset ;
    // empty, white king, white queen, ..., black rook, black pawn
    enum piece_t { WK = 0, WQ, WB, WN, WR, WP, BK, BQ, BB, BN, BR, BP,
                    NTYPES = BP+1, NOTHING } ;
    bitset board[ NTYPES ]  ;
    enum col_t { A, B, C, D, E, F, G, H } ;

    static inline std::size_t offset( col_t col, int row ) // eg. E5
    { return col*N + row ; }

    inline bool empty( col_t col, int row ) const // is this square empty?
    {
        const auto pos = offset( col, row ) ;
        for( const bitset& bs : board ) if( bs[pos] ) return false ;
        return true ;
    }

    inline piece_t piece( col_t col, int row ) const
    {
        const auto pos = offset( col, row ) ;
        for( int i=0 ; i<NTYPES ; ++i ) if( board[i][pos] ) return piece_t(i) ;
        return NOTHING ;
    }

    // etc
};

See: http://en.wikipedia.org/wiki/Bitboard

[ResidentBiscuit]

Wiki is currently blacked out :/
This seems overly complicated though. Mind explaining your choices?

[sohguanh]

With today advanced PC and servers, I doubt we need to squeeze every memory space by resorting to bit vector as the chess data structure. Array of int is sufficient imho.

Unless there are valid reason besides saving memory space in using bit vector. Perhaps the chess is to be run in embedded device when memory is small? Even that is changing with nowadays smart-phones specs rivaling that of desktop PC.

[ResidentBiscuit]

This is just for my own personal satisfaction (and boredom). I would like to have an efficient program, but size is not really a concern of mine. I'm not sure if looping through 12 bitboards is better, or if having one array of struct that holds everything I need.

[sohguanh]

If you have program long enough, you would know it is much easier to develop and troubleshoot array of int over bit vector. To use bit vector confidently, you most likely need to some functions that can output the bit vector value in human-readable format for easy debugging later.

[JLBorges]

> This seems overly complicated though. Mind explaining your choices?

Seems to be a bit pointless at this moment. In any case, you would eventually need more than one representation of the board anyway - so start with the array of structures for now.


> I would like to have an efficient program

One reason for using bitboards is that they are extremely efficient.
http://www.fzibi.com/cchess/bitboards.htm


> but size is not really a concern of mine

It would become a concern even if it is not one right now.

In typical chess positions there will be of the order of 30 legal moves.
The number holds fairly constant until the game is nearly finished as shown by De Groot,
who averaged the number of legal moves in a large number of master games.
Thus a move for White and then one for Black gives about 1000 possibilities.

- Claude Shannon in "Programming a Computer for Playing Chess"

This means that if you want a look-ahead of just four moves deep, the complete search tree would have a 1000 billion leaf nodes. Hence the need to prune the search and store as many previously analysed positions as possible in a hashtable.
http://www.netlib.org/utk/lsi/pcwLSI/text/node346.html

[ResidentBiscuit]

This means that if you want a look-ahead of just four moves deep, the complete search tree would have a 1000 billion leaf nodes

Am I reading this right?? Would that mean, I would have to take into account 1000 billion possibilities??

[JLBorges]

> Would that mean, I would have to take into account 1000 billion possibilities??

Yes, approximately that many, if the search is a brute-force search where every possible move is evaluated. You just can't do that - the numbers are way way too big - so the tree needs to be pruned intelligently. And results of previous evaluation of many positions must be stored - we don't want to re-traverse the entire sub-tree every time.

Google for 'Shannon number'.

[Caprico]

A machine operating at the rate of one variation per micro-second would require over 1090 years to calculate the first move!

I read this, and I was like :O Wow... Never ever in my life imagined that programming a Chess AI would be this complicated!

[ausairman]

This is probably not what you were after, but I'd like to point out the possibility of using a neural network, which could be trained to play chess quite effectively. This is of course a whole other can of worms, but it's probably less tedious and certainly more interesting (IMHO) than programming a chess AI directly.

A forward-feeding neural net with gaussian mutation could learn chess in a matter of minutes and could probably beat a human within a few hours. However, being nondeterministic, a neural net would probably never be able to play a "perfect game"; or at least this would take orders of magnitude longer for the computer to figure out than a simple possibilities map (those billion possibilites you were talking about).

There is quite a popular, freely available neural network system called NEAT (neuro-evolution of augmenting topologies) which I used quite a bit before I developed my own system. The same guy who wrote NEAT also created a program called HyperNEAT, which is essentially a geometrically aware version of NEAT, meaning that it can notice patterns spatially. In terms of chess, this might mean that when it figures out that it can move the pawn from 2A to 3A, then it would more rapidly learn that it can also move the pawn from 2B to 3B; whereas a conventional neural network learning algorithm would take just as long to figure out either move.

Both NEAT and HyperNEAT are available in C++.

Just a thought :)

[ResidentBiscuit]

As interesting as this sounds, and I'll definitely look it up out of curiosity, this sounds waaay beyond my current skill level