Function Speed

[BrettVsop]

I haven't been on in a while, and I am still having trouble with my engine speed.

I have written a calculate preft function and I am using it with another chess program called Roce. This way I can check to see if my numbers are correct.

When I run perft from the starting position with a depth of 3 ply it takes my program 1.8 seconds to run. This is really high I imagine. Roce only takes 0.016 seconds, so I must be doing something really wrong. (I am not sure if 3 ply is correct so I want to clarify: white moves, black moves, then white moves again).

99% of the time perft is running it is waiting for the function GetAllLegalMoves to return
on average GetAllLegalMoves takes 199 microseconds to run.

GetAllLegalMoves simply calls two functions: GetAllMoves, and RemoveIllegalMoves.

Get All Moves is running 17% of the time and takes an average of 35 microseconds each time it runs.

Remove Illegal Moves is running 81% of the time and takes an average of 164 microseconds to run.

I was wondering if anyone can compare these numbers to their engines and let me know if anything is out of the ordinary.

I noticed that each function also will occasionally take 16 milliseconds to run (no matter how short the function is). I am assuming this is when my program loses the cpu for a moment.

[Aleks Peshkov]

If you make RemoveIllegalMoves 2 times faster, your perft will be almost 2 times faster. Hint: it is faster to test a move when it is time to make it and not shuffling move-lists each time. I bet this only can make your perft 2 times faster.

There are clever ways almost never call RemoveIllegalMoves (= test whether king is in check). King cannot be in check after last made move in most cases, if it was not in check before. Really fast engines do so.

[BrettVsop]

if i remove the function that checks for illegal moves then I will run into a problem with stalemate. I will try it though and see how well it affects the speed.

[Pedro Castro]

There are clever ways almost never call RemoveIllegalMoves (= test whether king is in check). King cannot be in check after last made move in most cases, if it was not in check before. Really fast engines do so.

I suppose these programs then must have a function to recognize pinned, for example so that the program will not move a knight pinned by a bishop.

[Pradu]

I suppose these programs then must have a function to recognize pinned, for example so that the program will not move a knight pinned by a bishop.

Yes indeed. For Buzz I create a legal move generator with just a tad bit more overhead than the pseudo-legal move generator. You can do this by checking for pins and stuff like you said. Enpassant is a little tricky though.

[Sven Schüle]

if i remove the function that checks for illegal moves then I will run into a problem with stalemate. I will try it though and see how well it affects the speed.

Hi,

I remember that your speed problems have already been thoroughly discussed in another thread. There were a couple of advices which are of course also valid for perft calculation.

IIRC you make/unmake all moves at the end of move generation only for legality check, before presenting the resulting move list to the search (or perft). This is far too expensive.

Decide whether you want to have legal or pseudolegal move generation. Depending on this, there are a couple of tricks to ensure correct play, and they have all been mentioned in that other thread.

But in both cases, the move generator should not make/unmake all moves, this should only be done as part of the search (or here: the perft calculation), because you get "(N+1) * (cost of make+unmake)" per node instead of 1 * ..., where N is the average number of pseudolegal moves at a node.

For perft, it would be possible to check whether the enemy king is in check right after makeMove(), and to unmake and decrement the counter if it is, so that you do not count nodes below an illegal move.

Find below my current perft code, just for illustration. The legality check is done at the beginning of the recursive function, which is right after makeMove().

I know that it can be done even a lot easier, but that's another issue.

Code: Select all

uint64 Searcher::getPerftValue(
    uint argMaxDepth)
{
    Position & currentPos = m_game.getCurrentPosition();

    if (currentPos.isIllegal()) {
        return 0;
    }
    if (argMaxDepth == 0) {
        return 1;
    }
    if (currentPos.isTechnicalDrawn()) {
        // leaves above maximum depth do not count
        return 0;
    }

    uint numberOfChecks = 0;   // ignored here
    SquareId checkSqrId = NoSqrId; // will be used by move generator
    // using side effects ...
    (void) currentPos.isOwnKingInCheck(numberOfChecks, checkSqrId);

    bool mustExpand = false;
    m_moveGenerator.generate(
        currentPos, currentPos.m_moveList, true, checkSqrId, mustExpand);
    // no move ordering here
    if (!mustExpand) {
        // leaves above maximum depth do not count
        return 0;
    }

    uint64 nLeafNodesInSubtree = 0;
    uint nLegalMoves = 0;
    MoveList & moveList = currentPos.m_moveList;
    MoveListEntry * move = moveList.m_first;
    for (uint n = 0; n < moveList.m_size; n++, move++) {
        makeMove(*move, 0);
        uint64 nLeafNodes = getPerftValue(argMaxDepth - 1);
        if (nLeafNodes > 0) {
            ++nLegalMoves;
            nLeafNodesInSubtree += nLeafNodes;
        }
        unmakeLastMove();
    }
    if (nLegalMoves == 0) {
        // leaves above maximum depth do not count
        return 0;
    } else {
        return nLeafNodesInSubtree;
    }
}

Regards,
Sven

[BrettVsop]

Wow, I was able to speed it up big time. It turns out my problem was using too many classes.

I had a class that kept track of the board, another that kept track of the special rules, and a move generation class. Each of those classes had to use functions to access each other. I guess each call added up, because I combined them all into one class and it is ten times faster.

I see what you are saying with the LegalMove generation. That is really redundant, I am now going to remove the LegalMove testing, because it is unnecessary.

Thanks

[Jaco van Niekerk]

OO is brilliant for "Software Engineering"
OO is terrible for "Programming"

Chess is not "Software Engineering"

If you are using Java - avoid "new" as much as you can and make use of PDT's for move/board representation, etc. Better yet, use "static" data and functions for the time sensitive stuff.

Just my 2c.

[Aleks Peshkov]

and make use of PDT's for move/board representation,

What is PDT?

[Sven Schüle]

and make use of PDT's for move/board representation,

What is PDT?

Primitive Data Type (e.g. int, bool)

Sven

[Onno Garms]

OO is brilliant for "Software Engineering"
OO is terrible for "Programming"

Chess is not "Software Engineering"

OO and software engineering need not compromize performance.

For example, in my engine, Board is a class. Functions that get a board as a struct by a pointer and member functions differ only by syntax, not by semantics or performance.

It is true that an OO overkill can cause a severe slowdown. But inefficient programs can be written under any programming paradigm.

If you are using Java

I think using Java isn't a good idea at all.

- avoid "new" as much as you can

ACK

and make use of PDT's for move/board representation, etc.

I agree for move but not for board.

[Jaco van Niekerk]

I used to think that Java is a terrible language for a chess engine, but lately I've changed my opinion. I think that a well written Java engine can easily attain 2600+ elo. When using PDTs and static methods, a Java program comes very close to standard C and under certain very specific circumstances may even match (or even, dare I say, outperform it ).

However, I have found that Java OO is rather slow if overused. This topic is a heated debate and perhaps those interested should google previous similar discussions.

[Aleks Peshkov]

When using PDTs and static methods, a Java program comes very close to standard C

True programmer write Fortran program on any language?

[Tord Romstad]

OO is brilliant for "Software Engineering"
OO is terrible for "Programming"

Chess is not "Software Engineering"

How do you define "Software Engineering"? I think I would define it as a rigorous and diciplined approach to programming and testing, with attention to detail and a solid strategy for avoiding bugs. By this definition, chess programming is definitely software engineering.

My opinion about OO is that it is currently somewhat overhyped, but certainly a very useful tool for some (but not all) types of programming problems. For chess, using OO is fine if you prefer to do so, but I personally don't think it offers any significant advantages.

Tord