Speed and Board Storing Choices

[Sven Schüle]

Another question: If removing Making/UnMaking from the move generator speeds your engine up by a factor of 5, this process is obviously much slower than the rest of your engine, and you might get additional speedup by reducing its cost (because moves still need to be made before branching).

I am confused about what you are talking about. How can I determine if removing making and unmaking speeds my engine by 5? I kind of need that code for the alpha beta to work at all. I tried removing it before by using a copy of the board to make the move, but I think you can guess how slow that was

I think what Fritz meant was that you removed the legality check which included making and unmaking all moves. This raised your nps from 16600 to roughly 90000.

Sven

[Fritz Grau]

I am confused about what you are talking about. How can I determine if removing making and unmaking speeds my engine by 5? I kind of need that code for the alpha beta to work at all.

I agree with Svens explanation of the factor of 5 .
Of course you do need to make/unmake your moves. What I was trying to say was that if making/unmaking in the move generator had accounted for 80% of your search time (perhaps around 35 calls per node in middlegame) before you removed it, then the need to make/unmake moves before/after alpha-beta calls (around 5 calls per node?) is likely to have become a new bottleneck since you accelerated the move generator, so it would remain worthwhile to see whether some time can be gained during MakeMove.

My suggestions about memory allocations were probably wrong because I was mistaken about your method of unmaking moves: I assumed that you were doing something like copying the whole game history (i.e. the list of ALL previous moves each time you branch into a child node) at each node. However, your undo struct showed me that you store the game history incrementally. Perhaps you can find a way to accelerate the actual legality check?

I tried removing it before by using a copy of the board to make the move, but I think you can guess how slow that was

Admittedly, my engine does just that: It does not only copy the board (64 bytes) but a lot of auxiliary information including attack tables, amounting to more than 1,5kbytes at each node; but the CPU wastes only 6% of the search time on this process, while the total cost of making a move is around 20% of the search time, so it is not the bottleneck of my engine.

[Uri Blass]

<snipped>

I am not using any bitboards, so I do not know which pieces are pinned.

knowing which pieces are pinned has nothing to do with bitboards.
There are bitboard programs who have not this knowledge and movei knows which pieces are pinned not based on bitboards.

Uri

[BrettVsop]

Admittedly, my engine does just that: It does not only copy the board (64 bytes) but a lot of auxiliary information including attack tables, amounting to more than 1,5kbytes at each node; but the CPU wastes only 6% of the search time on this process, while the total cost of making a move is around 20% of the search time, so it is not the bottleneck of my engine.

I think, once I implement bitboards, that i will do the same thing. Atm I have to loop through each square to copy a board, but with a bitboard all I need to do is about 10 copies. The second option sounds alot faster.

I am going to go through the code and see what I can speed up. Thanks alot guys, you have helped alot. I will let you know what happens.

[BrettVsop]

Ok I redid some things that I expect will speed it up. The main change that I made was to UndoMove. I made the structure bigger so that I did not need to check for castling or en passant rules. I also changed back to MinMax search so that I can find the problems easier.

My question: What is good, average, and poor search times? Could you give me some rough numbers to let me know how many nodes per second I should be getting so that I know when I am at a decent speed?

At the moment I am at
milliseconds 4563
nodes 72990

which comes to about 16k nodes per second. Where does this rank on a scale of good to bad? By the way I changed some things back to where they were. I am searching for legal moves and Evaluate is counting moves for both players. So I have a few areas I know I can work on.

Thanks

[Aleks Peshkov]

I also changed back to MinMax search so that I can find the problems easier.

At the moment I am at
milliseconds 4563
nodes 72990

which comes to about 16k nodes per second. Where does this rank on a scale of good to bad?

Your node count for minimax search of initial position looks very strange. And 16 knps is about 100 times slower then average...

I suggest you to create a search function calculating perft numbers, so you can validate your move generator and compare its speed with well-known results.

[BrettVsop]

First off I want to verify that I am counting nodes and time correctly.

I am incrementing NodeCount in the main loop. Is that correct?

Code: Select all

while (GetNextMove())
{
   nodecount++;
   MakeMove
   Val = Min();
   UndoMove;
   if (val < Min)
      Min = Val
}

Second, can you explain the code behind perf? I really do not know how that function works? Also where can I find well known results?

Thanks

[Aleks Peshkov]

Second, can you explain the code behind perf? I really do not know how that function works? Also where can I find well known results?

http://www.albert.nu/programs/sharper/perft.htm

[H.G.Muller]

Second, can you explain the code behind perf? I really do not know how that function works? Also where can I find well known results?

Thanks

Just disable the beta cutoff, and the node count should be a perft count

[Teemu Pudas]

Second, can you explain the code behind perf? I really do not know how that function works? Also where can I find well known results?

Thanks

Just disable the beta cutoff, and the node count should be a perft count

No, perft only counts nodes that are exactly x plies from root.

[H.G.Muller]

OK, so he has to compare to the added results of all depths. More important is if all the moves that are made are legal, or not.

But the main question here is if the figures are in the right ball park, not if they are exactly right. His nps seems a factor 100 too low...

[BrettVsop]

No need to disable beta cut off, I am using MinMax.

Let me explain my code a little more because I am not sure how differently I am doing things then most.

I send a call to GenerateMoveList which comes up with a list of all the good moves (all the moves have equal value). This function generates a list of all possible legal moves. It then makes a move and asks MinMax to generate a value for the move. Afterwards it undoes the move and loops to the next one. I do not increment NodeCount in this function.

The psudocode for MinMax I posted in the last thread. In the main loop of that function is where I increment NodeCounter.

So at a depth of zero (which is really one, because it does not count the moves made in GenerateMoveList) I get zero nodes.

At one (really two) I get 400 nodes.
At two (really three) I get 9302
At three (really four I get 206720

I think that I have the node counter in the wrong place. I could move it so that it also counts the first moves but that would give me results twenty nodes higher then the ones posted.

According to the website given, I am off.
node expected found
1 20 0
2 400 400
3 8902 9302
4 197281 206720

Even if I correct the position, it appears that my code is also wrong.

Should I only be counting the number of times evaluate is run?

Thanks.

[Roman Hartmann]

Hi,
you have to take care with perfting. Perft n usually doesn't mean to sum up all the nodes to depth n. Perft n means to sum up all the nodes from depth n-1 to depth n (some engines like yace give you the total sum of the nodes as well though).

If you subtract 400 from 9302 you're on 8902 which would be the right number for perft 3. Seems that you're only counting different. For perft 4 your values are off though and might indicate a bug somewhere.

Roman

[BrettVsop]

that makes sense. I have been having trouble with pawn promotion and I think that is where my error is.

[Sven Schüle]

Pawn promotion during the first four plies would surprise me.

20 + 400 + 8902 + 197281 = 206603, so with 206720 you are off by 117 nodes only. I guess you will find this.

Sven

[H.G.Muller]

No need to disable beta cut off, I am using MinMax.

Well, I haven't been following all of the thread, but in the first post you mentioned you were using alpha-beta. If you are doing plain minimax, it is no surprise that you only get to 4 ply in 20 seconds...

[Aleks Peshkov]

I send a call to GenerateMoveList which comes up with a list of all the good moves (all the moves have equal value). This function generates a list of all possible legal moves.

How do you do this?

[BrettVsop]

No need to disable beta cut off, I am using MinMax.

Well, I haven't been following all of the thread, but in the first post you mentioned you were using alpha-beta. If you are doing plain minimax, it is no surprise that you only get to 4 ply in 20 seconds...

The 4 ply in 20 seconds I was getting with AlphaBeta. I reworked some of the code to speed it up and while reworking it I switched back to MinMax. I am sticking with MinMax for a bit until I work out some other problems that I am noticing.

I send a call to GenerateMoveList which comes up with a list of all the good moves (all the moves have equal value). This function generates a list of all possible legal moves.

How do you do this?

Here is the code. I am guessing that this is different then the average approach and I am very interested to hear of alternatives to this.

Code: Select all

bool CAI::IsMoveAcceptable(CReferee *chessboard, SMove move, CMoveList *move_list)
{
   chessboard->Move_Piece(move);

   int iMoveRating = HndCalculation.GetFutureImbalance(chessboard,!chessboard->IsWhitesTurn(),DEPTH);
   
   chessboard->Undo_Move();

   if (iMoveRating > iMoveStrength)
   {
      iMoveStrength = iMoveRating;
      move_list->ClearAllMoves();
   }
   if (iMoveRating == iMoveStrength)
   {
      return true;
   }
   return false;
}

void CAI::GenerateMoveList(CReferee *chessboard, CMoveList *move_list)
{
         //Set Starting Variables
   iMoveStrength = NEG_INFINITY * 100;
   move_list->ClearAllMoves();

         //Loop Through All Moves
   HndMoves.FindAllLegalMoves(chessboard,&temp_move_list);

   int i = 0;
   while (i < temp_move_list.GetMoveCount())
   {
      SMove current_move = temp_move_list.GetMove(i);
      if (IsMoveAcceptable(chessboard, current_move,move_list))
      {
         move_list->AddMove(current_move);
      }
      i++;
   }
}
int CMinMax::GetFutureImbalance(CReferee *chessboard, bool check_white, int iTime)
{
   int iValue = Min(chessboard,check_white,iTime);
   return iValue;
}


[Aleks Peshkov]

Code: Select all

         //Set Starting Variables
   iMoveStrength = NEG_INFINITY * 100;


Calculate how many times Move_Piece(move) called and compare it with actual number of positions in search tree... Pseudo-legal move generation make first number no more 5-10% greater then the second. It is the cost of fast pseudo-legal generation.

Calculate how many CMoveList::AddMove(move) called and compare it with actual number of positions in search tree...

[Sven Schüle]

The 4 ply in 20 seconds I was getting with AlphaBeta. I reworked some of the code to speed it up and while reworking it I switched back to MinMax. I am sticking with MinMax for a bit until I work out some other problems that I am noticing.

I think some important issues have already been identified within this thread regarding your AlphaBeta version:

- the costs of your way of doing the move legality check are high (I proposed a different, common way to restrict legality check to few cases only, all other moves are 100% legal; also, the legality check may be done within AlphaBeta instead of the move generation, which means to have pseudo legal move generation; but even with fully legal move generation the "restricted legality check" will help);
- the costs of having a poor move ordering are very high, your search visits much more nodes than necessary to get the same AlphaBeta result.

Also, move generator bugs seem to be present ("perft") which should be fixed soon.

Considering these issues I can only propose that you proceed like this:

1. continue with the fastest AlphaBeta version you have available (i.e., the one without legality check) just to save a huge amount of testing time (MinMax lets you wait very long for its result, each time you did a small change takes a couple of minutes),
2. then write a function that checks whether the enemy king is in check (and call it e.g. in the very beginning of each node, so that AlphaBeta returns +INFINITY for illegal positions) [EDIT: you probably have it already but use it within FindAllLegalMoves()],
3. then write a perft function and fix your perft numbers,
4. then add some simple move ordering improvements like iterative deepening, killer moves, MVV/LVA,
[EDIT] 4a. then add quiescence search,
5. then add some very simple and cheap positional evaluation criteria,
6. then implement a simple time control and let your search stop on timeout instead of reaching a fixed depth limit,
7. then play many games with fast time control against other engines to see where you are really standing,
...
99. and much later make small performance speedups with negligible effect on your engine's playing strength.

Code: Select all

int CMinMax::GetFutureImbalance(CReferee *chessboard, bool check_white, int iTime)
{
   int iValue = Min(chessboard,check_white,iTime);
   return iValue;
}


What is the meaning of "GetFutureImbalance", and what does your "Min()" function do?

Sven