Feb 6, 2007

[Other] Finally something that made a difference

I kept reading through the move generation code over and over and finally I noticed something significant. In the isAttacked()-method Mediocre was not checking if the piece on the square was of the right color before determining if it could attack the square.

This was caught further down in the code when pieces of the wrong color never matched the attack pattern, but the harm in extra calculating time was already done by then.

This line of code:
if(pieceOnSquare <= 0) continue;
cut another 10-20% off the generation time.

The new times for perft are still not great, but they are atleast getting better:

Depth    Nodes     Time
1 20 0.000
2 400 0.000
3 8902 0.047
4 197281 0.312
5 4865609 7.750
6 119060324 3:23.094


Anonymous said...

Move generation is the most time-consuming part of my engine's code as well, though the terms I'm adding to the evaluation function have brought that up to 20% of the time spent. I found the following change helpful:

Most of the move generations in my engine's search come from the quiescence search (perhaps indicating that my move ordering needs to be improved there). I was getting the captures to search in the quiescence search by getting all possible moves for the position and then picking out the captures. I got a 30% or so speed improvement by making a new routine that just generates capture moves. So instead of calling getMoves(), the quiescence search calls getCaptures(), which just ignores any non-capture moves. I'm not sure if Mediocre already does something like this -- if not you should try it out.

Anonymous said...

The speed of move generator is not very important.
If you have a 20% faster move generator, your engine will be only 1% faster.

More important is:
-bugfree engine
-good tactic (extension, checks and capture at first ply of quiescence)
-good depth (nullmove with R 3, late move reduction, move sorting with history and killer move)

NPS are useless, a very slow engine can have a very high depth search if you make reduction on useless move (lmr).
You should test your engine on tactical test suite like WAC to estimate the level of each version.

Jonatan Pettersson said...

Maybe I made the wrong conclusion, but playing against other engines Mediocre seems to have pretty much the same node count on every ply (sometimes better). But other engines still search a ply or two deeper on every given position.

To me that looks like Mediocre does prune pretty well, but can't compete due to other factors.

Since Mediocre still has a fairly trivial evaluation function I have a hard time seeing where else the problem could be other than things like move generation.

Anonymous said...

Hello and congratulations :)

I also did a chess engine using java long ago and it was not so bad :) Right now I don`t even remember how to code in Java :)

About move generation and speed in general, there is something that you really need to fix: big loops (like i < 120) because you do use them not only when generating moves but also in the evaluation routine. For a chess game you have at most 32 pieces, 16 per side.. so when generating the moves your loop should not be bigger than 16!, aslo it is a good idea to track both kings positions, that way you won't need to scan the board looking for the king and then see if it is in check.

Hope that helps..

Keep the good work my friend :)


ps: sorry for my english :(