Beginning to Program...

[sje]

This is long, but I think it's worth posting.

The CTBX(n) macro produces (1 << N)

Code: Select all

// Chess man

typedef enum
{
  CTManNil = -1,
  CTManWhitePawn,
  CTManWhiteKnight,
  CTManWhiteBishop,
  CTManWhiteRook,
  CTManWhiteQueen,
  CTManWhiteKing,
  CTManBlackPawn,
  CTManBlackKnight,
  CTManBlackBishop,
  CTManBlackRook,
  CTManBlackQueen,
  CTManBlackKing,
  CTManVacant,
  CTManExtra
} CTMan;

#define CTManLen   (CTManExtra + 1)
#define CTManRCLen (CTManBlackKing + 1)

#define CTForEachMan(theIndex)   CTIndexLoop(theIndex, CTManLen)
#define CTForEachManRC(theIndex) CTIndexLoop(theIndex, CTManRCLen)

#define CTMaskManWhite 0x003f
#define CTMaskManBlack 0x0fc0

inline bool IsNil(const CTMan theMan) {return theMan < 0;}
inline bool IsNotNil(const CTMan theMan) {return theMan >= 0;}

inline bool IsRC(const CTMan theMan)
{
  return theMan < CTManRCLen;
}

inline bool IsValidMan(const CTMan theMan)
{
  return (theMan >= 0) && (theMan < CTManLen);
}

inline bool IsValidManRC(const CTMan theMan)
{
  return (theMan >= 0) && (theMan < CTManRCLen);
}

inline bool IsWhite(const CTMan theMan)
{
  return CTMaskManWhite & CTBX(theMan);
}

inline bool IsBlack(const CTMan theMan)
{
  return CTMaskManBlack & CTBX(theMan);
}

inline CTColor MapToColorRC(const CTMan theMan)
{
  return (theMan < CTManBlackPawn) ? CTColorWhite : CTColorBlack;
}

inline CTPiece MapToPieceRC(const CTMan theMan)
{
  return (CTPiece)
    ((theMan < CTManBlackPawn) ?
      (int) theMan : (int) (theMan - CTManBlackPawn));
}

inline bool IsPawn(const CTMan theMan)
{
  return 0x0041 & CTBX(theMan);
}

inline bool IsKnight(const CTMan theMan)
{
  return 0x0082 & CTBX(theMan);
}

inline bool IsBishop(const CTMan theMan)
{
  return 0x0104 & CTBX(theMan);
}

inline bool IsRook(const CTMan theMan)
{
  return 0x0208 & CTBX(theMan);
}

inline bool IsQueen(const CTMan theMan)
{
  return 0x0410 & CTBX(theMan);
}

inline bool IsKing(const CTMan theMan)
{
  return 0x0820 & CTBX(theMan);
}

inline bool IsVacant(const CTMan theMan)
{
  return theMan == CTManVacant;
}

inline bool IsNotVacant(const CTMan theMan)
{
  return theMan != CTManVacant;
}

inline bool IsWhitePawn(const CTMan theMan)
{
  return theMan == CTManWhitePawn;
}

inline bool IsBlackPawn(const CTMan theMan)
{
  return theMan == CTManBlackPawn;
}

inline bool IsWhiteKnight(const CTMan theMan)
{
  return theMan == CTManWhiteKnight;
}

inline bool IsBlackKnight(const CTMan theMan)
{
  return theMan == CTManBlackKnight;
}

inline bool IsWhiteBishop(const CTMan theMan)
{
  return theMan == CTManWhiteBishop;
}

inline bool IsBlackBishop(const CTMan theMan)
{
  return theMan == CTManBlackBishop;
}

inline bool IsWhiteRook(const CTMan theMan)
{
  return theMan == CTManWhiteRook;
}

inline bool IsBlackRook(const CTMan theMan)
{
  return theMan == CTManBlackRook;
}

inline bool IsWhiteQueen(const CTMan theMan)
{
  return theMan == CTManWhiteQueen;
}

inline bool IsBlackQueen(const CTMan theMan)
{
  return theMan == CTManBlackQueen;
}

inline bool IsWhiteKing(const CTMan theMan)
{
  return theMan == CTManWhiteKing;
}

inline bool IsBlackKing(const CTMan theMan)
{
  return theMan == CTManBlackKing;
}

inline bool IsStep(const CTMan theMan)
{
  return 0x08e3 & CTBX(theMan);
}

inline bool IsSweep(const CTMan theMan)
{
  return 0x071c & CTBX(theMan);
}

inline bool IsMajor(const CTMan theMan)
{
  return 0x0618 & CTBX(theMan);
}

inline bool IsMinor(const CTMan theMan)
{
  return 0x0186 & CTBX(theMan);
}

inline bool IsQRBNP(const CTMan theMan)
{
  return 0x07df & CTBX(theMan);
}

inline bool IsQRBN(const CTMan theMan)
{
  return 0x079e & CTBX(theMan);
}

inline bool IsQRP(const CTMan theMan)
{
  return 0x0659 & CTBX(theMan);
}

inline bool IsWhiteKQR(const CTMan theMan)
{
  return 0x0038 & CTBX(theMan);
}

inline bool IsBlackKQR(const CTMan theMan)
{
  return 0x0e00 & CTBX(theMan);
}

inline bool IsWhiteKQB(const CTMan theMan)
{
  return 0x0034 & CTBX(theMan);
}

inline bool IsBlackKQB(const CTMan theMan)
{
  return 0x0d00 & CTBX(theMan);
}

inline bool IsWhiteQRBNP(const CTMan theMan)
{
  return 0x001f & CTBX(theMan);
}

inline bool IsBlackQRBNP(const CTMan theMan)
{
  return 0x07c0 & CTBX(theMan);
}

inline bool IsWhiteQRP(const CTMan theMan)
{
  return 0x0019 & CTBX(theMan);
}

inline bool IsBlackQRP(const CTMan theMan)
{
  return 0x0640 & CTBX(theMan);
}

inline bool IsWhiteQR(const CTMan theMan)
{
  return 0x0018 & CTBX(theMan);
}

inline bool IsBlackQR(const CTMan theMan)
{
  return 0x0600 & CTBX(theMan);
}

inline bool IsWhiteQB(const CTMan theMan)
{
  return 0x0014 & CTBX(theMan);
}

inline bool IsBlackQB(const CTMan theMan)
{
  return 0x0500 & CTBX(theMan);
}

inline bool IsWhiteBN(const CTMan theMan)
{
  return 0x0006 & CTBX(theMan);
}

inline bool IsBlackBN(const CTMan theMan)
{
  return 0x0180 & CTBX(theMan);
}

inline char LCCharFromMan(const CTMan theMan)
{
  return "pnbrqkpnbrqk ?"[theMan];
}

inline char UCCharFromMan(const CTMan theMan)
{
  return "PNBRQKPNBRQK ?"[theMan];
}

inline char MPDCharFromMan(const CTMan theMan)
{
  return "PNBRQKpnbrqk ?"[theMan];
}

[Suji]

I always found it very awkward to encode black pieces as the negative of their white counterpart. It means yourcode has to tak absolute values quite often, and there is no elementary instruction for that. So it likely involves code wth lots of (mispredicted) branches.

So I always use representations where the color can be read from the piece by looking at a single bit. Like BackPiece = WhitePiece+8. Then you can still easily test if a piece is hite or black through "if(piece&8)" in stead of "if(piece<0)" in your current system. But you can also easily extract the piece type through an AND operation stripping off the color bit, for which there exists a single instruction, and no branches are needed: "pieceType = piece&7;". This makes it much easier to write color-independent code.

This makes a lot of sense now that I think about it. I would easily get confused with all of the negatives and positives running around. Also, this is kind of what Dr. Hyatt said here: http://www.cis.uab.edu/hyatt/boardrep.html

So, I've modified my code to be:
class Board
{
private:
int board[128]; //Will keep track of the state of the board
int fifty_move_rule; //Keeps track of the fifty move rule
int total_moves; //Keeps track of the total number of moves
int sidetomove; //Keeps track of the side to move

enum Pieces
{
WhitePawn = 1,
WhiteKnight,
WhiteKing,
WhiteBishop = 5,
WhiteRook,
WhiteQueen,
BlackPawn = 9,
BlackKnight,
BlackKing,
BlackBishop = 13,
BlackRook,
BlackQueen,
};
public:
Board();
int switchside(int sidetomove);

//makemove(); Don't know the return types
//unmakemove();
};

Is this better?

I don't understand Steven's code as I am just starting out in the chess programming world. Hence, I am not going to use it (it is like reading greek.). My first goal is to make a chess program an engine that works, and then I will fine tune it to be the "best" that it can be.

I think an en_passant square is missing and the castling flags.
With this you have basically all the information that is needed to describe
a board or chess position. But that is not enough. You have many choices
before you and you have to make many decisions. Let me write down a few:

1. Is the fast int the best type or the small (unsigned) char?
2. Others mentioned the piece numbers.
3. How do you save the castling rights? Bits in an int or a struct of variables?
4. It is very conveniant to have the positions of the two kings in additional variables.
This means a little bit more effort at make/undo move but helps
everywhere else. There are many more decisions like this.
5. Perhaps you can gain from additional piece lists. (piece -> some lists -> squares)
6. Even if you want to avoid bitboards for each piece type it may be a good
idea to have a bitboard for all occupied squares.
7. Is the in_check flag part of the board or a local variable in the search?
8. Don't use too many classes and member functions. Find a good class structure. (I think I did this wrong.)
- ...
And then the design of moves and move lists has as many possibilities.

Yes the en passant and castling is missing as I have yet to add them in, and I'll answer your questions here as a way to organize my thoughts.

1. I think that will have to wait until the test stage, to figure this out. I don't know this yet.

2. Yes, I hope that they are now acceptable.

3. I think that I will use a struct of variables. They seem to be easier than bits and integers in this case.

4. I've read that it really does make it easier. I might do this although it might make my life a little bit harder later on.

5. Can someone explain this to me? I don't know what this means.

6. That might be a good idea. I might do it.

7. This is going to be part of the search.

8. I will try to do this.

[Harald]

Like the enums piece lists come in many forms. They are additional data
parallel to the board array for faster access to pieces. Imagine you want to
do something with your bishops like generating moves or evaluate them.
Without piece lists you had to write something like

Code: Select all

for ( sq = 0; sq < 128; ++sq )
  if ( board[sq] == WhiteBishop )
    ...

Piece lists could be implemented like this:

Code: Select all

int wPieceCount;        // Do the same for black
int wPieceType[16];
int wPieceIndex[16];
// Looking for bishops
for ( i = 1; i < 16; ++i )  // or i < wPieceCount if you know where the list ends early
  if ( wPieceType[i] == WhiteBishop )
    sq = wPieceIndex[i];
    ...
  // If your pawns and dead pieces are sorted last in the list even after promotions you could do
  // if ( wPieceType[i] == WhitePawn || wPieceType[i] == DeadPiece )
  //   break;
  // But people say it is easier to leave the dead where they died 
  // and resurrect them there in undoMove()

The loop is much shorter now.
wPieceType[0] is always the WhiteKing and wPieceIndex[0] its position.
Of course you have to update this lists in makeMove(), undoMove().
Be careful with promotions.
Some people like 2-dimensional arrays for white and black.
Another possibility is to separate the pawns in their own small list.
That will make the loop for other pieces even shorter.
If you have no better use for the second half of the 0x88 board array
you could store the piece list index for each corresponding piece there.
A lot of new decisions.

Harald

[hgm]

A funny coincidence that I am just remaking all these kind of decisions for a new engine I just started writing, which should be able to handle Chess variants with piece drops, on boards upto 10x10. For attack tests to work, the actual board should be at least 10x19. For using the 'unused half', though, it would be better to take 10x20. There will be many tables that have board format (piece-square, Zobrist keys), and by taking 10x20 arrays, two such tables can be held without any loss of space. The actual board will have a 3-wide band of edge guards around it.

Additional problem is that I would also like the kernel of the engine to run entirely in L1 cache, even on a Pentium IV, which might only have 8KB of L1. But this might be overdoing it...

[Steelman]

Just a couple of tips.

If you are new at programming keep the code simple. So you understand it. If the bitboard are a little confusing now then don't use them. Nothing will kill your motivation for writing a chess program than the frustration of trying to learn to much at once.

Start by figuring out the board representation. Again keep it simple. Then add piece lists. And then figure out how you will store the move tree.

Then I would think the very next step would be how to generate moves. Write a move generator. And make sure you know it works. Bugs can be real frustrating. Test the daylights out of it! And do not continue untill you are sure it works correctly. It may be a good idea to figure out castling, en passant, and pawn promotions. If you don't take care of at this point it may be difficult to add them later.

Then perhaps write a make move and unmake make move functions. And again test the daylights out of it.

Then start on evaluation functions. Then test test test!

Then the search function. And at this point if you have any bugs in any of the code you have allready written and problems begin to appear it may be very difficult to find them.

After this then work on all the stuff you may not have done prior to this. Like 3 move repetition, 50 move rules, etc.

Hopefully you will have a "working" chess program and you will have learned a great deal about programming and programming a chess engine.

And of course you will now be at the point where you will consider a complete rewrite of your program to correct all the things you did wrong to make it faster, better, etc. Maybe even add bitboards.

Good Luck and Have Fun!