Guide me through building a chess program

[hgm]

In micro-Max I do the moves at game level through the "exit through second-story window" technique: Before unmaking moves in the root, I test if the move is equal to the move I must play, and if it is, I return from the Search routine without unmaking that move (or doing any of the other actions that unmake would otherwise do).

If you do that for the move the Human entered, and there was no match, the move is not made, and the side-to-move not flipped. (Apparently it was not legal, as the root would try all legal moves.) Because micro-Max has a pseudo-legal move generator, and only discovers if a move is illegal in the daughter node, when it finds a reply that captures the King, I actually have to do this in a two-ply search, and only apply the test if the move is the requested one if the score of the move was not -INFINITY. (King capture immediately returns +INFINITY.)

If the computer is on the move, after time runs out, I copy the best move found so far in the root to the same location as that normally contains the move that the Human entered, and do another iteration with d=2. (Which now should always find the move, unless there was no best move because you were checkmated or stalemated.

[Sapta]

^ Ok, I somewhat understand. W need a 2-ply search when human player gives move.

In micro-Max I do the moves at game level through the "exit through second-story window" technique: Before unmaking moves in the root, I test if the move is equal to the move I must play, and if it is, I return from the Search routine without unmaking that move (or doing any of the other actions that unmake would otherwise do).

Won't this work only when the last or rightmost branch from root is the move computer finds out to be best? How many board positions are kept in memory during the search? :s

[Sapta]

I am reading alpha-beta pruning. We do alpha cut-offs when in a min node, temporary beta value(or upper bound) from child nodes is less than alpha value passed down from ancestors. Similarly beta cut-offs in a max node when upper bound is greater than beta value passed down.

However, in a nega-max framework, it's like we only check for beta cutoffs , ie, all nodes are being treated as max nodes. Really confusing me. The evaluation function at the leaf nodes, they evaluate the board from whose perspective? Also, how many board positions are kept in memory at any time? :/

[Sven]

I am reading alpha-beta pruning. We do alpha cut-offs when in a min node, temporary beta value(or upper bound) from child nodes is less than alpha value passed down from ancestors. Similarly beta cut-offs in a max node when upper bound is greater than beta value passed down.

However, in a nega-max framework, it's like we only check for beta cutoffs , ie, all nodes are being treated as max nodes. Really confusing me. The evaluation function at the leaf nodes, they evaluate the board from whose perspective? Also, how many board positions are kept in memory at any time? :/

In negamax framework the evaluation function must return a value from the perspective of the moving side, which is also the maximizing side in the search. You can achieve that by something like this:

Code: Select all

int evaluate(Board * b, int movingSide) {
    int v = evaluateFromWhitePerspective(b);
    return (movingSide == White) ? v : -v;
}

Most people keep only one current board position in memory, except for status information like ep target square or castling rights that must be restored when undoing moves and is therefore kept on a stack or something similar.

Sven

[hgm]

Won't this work only when the last or rightmost branch from root is the move computer finds out to be best? How many board positions are kept in memory during the search? :s

No, becuse I do the comparison after the search of every move in the root. Like:

Code: Select all

static MoveType userMove;

int Search(ply, ...)
{
  ...
  if(CAN_CAPTURE_KING) return INFINITY;
  for(ALL_MOVES) {
    ...
    MakeMove(move);
    score = -Search(ply+1, ...);
    if(ply == ROOT && score > -INFINITY && move == userMove) return OK_CODE;
    UnMake();
    ...
  }
  ...
  return bestScore;
}

If you call this with userMove initialized to the input move, a legal move would lead to returning OK_CODE and the move is done. As MakeMove also changes stm, flips the evauation, etc., you are immediately ready to play the next move. An illegal move, recognizable by the return of another score, would be refused, and the game state would not be altered.

When you put an invalid move n userMove before calling search, it would do a normal search. You can then copy the best move found to userMove, and call Search again (with a depth of 2 ply) to perform it. (In micro-Max I do this even in the same call: when at the end of an iteration time is up, the best move is copied to userMove, and the depth reset to 2, before the next iteration starts. As the move will always be legal, that will make the root Search all return, with the move done.)

[Sapta]

I get it more or less Thanks for the suggestion. Anyway one of my friends has decided to do the search part with me doing the move ordering.

I read chesswiki and it seems first thing to do is adopt an iterative deepening alpha-beta with PV collection. Now Bruce Moreland site gives 2 ways for it, a function and using TT. Which one should be better in terms of efficiency and ease of coding?

Another thing. Should the move ordering be applied to all lists of move generated at every position (other than the leftmost one at full depth)?

[hgm]

Indeed, in every node of the tree you would have to generate moves, and sort them. The order in which the moves are searched is the major factor in determining the strength of the program. (Apart from crippling bugs, of course.)

[Richard Allbert]

Regarding the

for(i=0; i < 120; ++i)

If you're using 0x88, I assume you have the [128] array, if you're going to loop through like this (eventuall piece lists are a quicker way) make another board array of 64 squares

Code: Select all

enum squarenames {
    A1 = 0, B1,C1,D1,E1,F1,G1,H1,
    A2 = 16, B2,C2,D2,E2,F2,G2,H2,
    A3 = 32, B3,C3,D3,E3,F3,G3,H3,
    A4 = 48, B4,C4,D4,E4,F4,G4,H4,
    A5 = 64, B5,C5,D5,E5,F5,G5,H5,
    A6 = 80, B6,C6,D6,E6,F6,G6,H6,
    A7 = 96, B7,C7,D7,E7,F7,G7,H7,
    A8 = 112, B8,C8,D8,E8,F8,G8,H8
};


const uint squarefrom64[64] = {
    A1, B1,C1,D1,E1,F1,G1,H1,
    A2, B2,C2,D2,E2,F2,G2,H2,
    A3, B3,C3,D3,E3,F3,G3,H3,
    A4, B4,C4,D4,E4,F4,G4,H4,
    A5, B5,C5,D5,E5,F5,G5,H5,
    A6, B6,C6,D6,E6,F6,G6,H6,
    A7, B7,C7,D7,E7,F7,G7,H7,
    A8, B8,C8,D8,E8,F8,G8,H8
};

#define SQFROM64(sq) (squarefrom64[(sq)])

Then you only need to loop through 64 squares

Regards

Richard

[hgm]

Or use the micro-Max way:

for(i=0; i<120; i=i+9&~8) ...

[Sapta]

Nice Thanks Allbert and hgm.

I was reading Transposition table and Zobrist keys. Bruce Moreland, in his website, says to use [Zobristkey()%Table size] as index in an array. What size of array is he using?

In java there's Hashmap class for hash tables. But I feel that the get(key) function used to retrieve entries searches the table. If that's the case, then it would be very slow. So, do I use array for transposition table? Can anyone confirm if my fear is correct or not?

Also it's said everywhere that lots of bugs creep in when implementing hash tables. I really wonder if it's worth the effort. How much important is TT for a chess program's performance?