World Chess Move Generation Speed Competition 2015

[Henk]

It should be obvious what I mean. Counting material only means counting material only during evaluation and nothing more.

Not much double Dutch.

By the way I don't understand why you react on my post for it always ends into a quarrel. Moderators might be sick of it.

[Roger Brown]

It should be obvious what I mean. Counting material only means counting material only during evaluation and nothing more.

Not much double Dutch.

By the way I don't understand why you react on my post for it always ends into a quarrel. Moderators might be sick of it.

Hello Henk,

The moderators are perfectly capable of speaking about their feelings of nausea.

This forum facilitates discussion. It is not your own private page where you can post what you will without discourse - which you seem to want to encourage in any event.

The member has spotted an item of interest to him in the discussion and has pointed it out. It may be that it is of no consequence. It may be that it is of importance.

His reaction seems fine to me thus far.

Later.

[Henk]

I don't know what Alvaro means.

Wait. Yes when computing Kiwipete perft(4) speed is about 1 million nodes per second. But that's because my perft implementation is very bad.

[AlvaroBegue]

I don't know what Alvaro means.

Wait. Yes when computing Kiwipete perft(4) speed is about 1 million nodes per second. But that's because my perft implementation is very bad.

I'll try to be constructive. Can you start with your search routine, simplify it dramatically to not use alpha-beta or any reductions/extensions, and then modify it to return the number of nodes visited? That would give you a Perft implementation, and it can't possibly be any slower than your search. It would actually be significantly faster.

[Sven]

Well, qperft does not do fully legal move generation. It doesn't generate illegal moves with pinned pieces (which saves it some time), so the only moves that would have to be tested to see if it puts itself in check are King moves and e.p. capture. So it makes those at the 1-ply level. And it then tests for check using the 0x88 attack test for all non-Pawns in the piece list, and testing the two board squares from which it could be checked by a Pawn.

If the side to move is not in check then the only pieces that can capture it's king are the pieces located on the squares of the x-ray queen moves of the square that is not longer occupied by the move of the side to move if that move is not a king move or an en passant move

Am I right ? Unfortunately that does not work in Skipper. But I don't know why.

A possible reason is that your description above is hard to understand. Rewrite the phrase in way that can easily be transformed into a simple algorithm. Also it seems your definition does not deal with a king being attacked by a knight. The most simple way to detect whether a king has been left in check (i.e., is attacked by an enemy piece) is to test for attacks in all possible directions starting at the king square:
- is it attacked by a pawn,
- by a knight,
- by a king,
- by a rook or queen on a horizonal/vertical ray, or
- by a bishop or queen on a diagonal ray?
You can try to be more clever by using information about the last move, as you mentioned, but you do not get this for free. If you do so, and it does not work, then watch out for the bug, or go the simple way first and postpone the clever way.

A pseudo-legal move can be illegal in one of these four cases:
- it is a check evasion,
- it is a king move,
- it is an ep capture, or
- it is a move of a pinned piece.
All other pseudo-legal moves are legal and do not require a make-unmake for legality testing.
The set of moves given above can even be reduced a bit in some cases but doing so usually does not give you another drastical improvement.

Code: Select all

bool MoveIsLegal(Move move)
{
    bool legal = true; // most pseudo-legal moves are legal
    Color self = sideToMove;
    if (inCheckFlag || IsKingMove(move) || IsEpMove(move) || IsPinned(move.from)) // move could be illegal
    {
        do(move);
        legal = !IsAttackedBy(KingSquare(self), Opponent(self));
        undo(move);
    }
    return legal;
}

MoveList LegalMoves()
{
    MoveList pMoves = PseudoLegalMoves();
    MoveList moves;
    inCheckFlag = IsInCheck();
    DetectPins();
    foreach (move in pMoves)
    {
        if (MoveIsLegal(move))
        {
            moves.add(move);
        }
    }
    return moves;
}

Regarding IsPinned(), even if Skipper is not a bitboard engine you can still use a bitboard for that purpose. DetectPins() finds all pieces pinned to the king of the moving side and stores their locations in a 64-bit number. IsPinned() maps the given square to a bit position and does a simple AND.

If side to move:
- is not in check (before it makes a move)
- does not do a king move
then knight attacks of opponent cause no illegal moves.
Same holds for pawn attacks. Only sliding pieces (might) count if they are one the line between move.Start square and king.Location square.

Yes, no doubt about that. But read what I wrote. I was talking about general IsKingInCheck after a move, not restricted to not being in check before that move and/or not making a king move.

I also wrote that you can of course be more clever than that. You could, for instance, have two different IsKingInCheck functions, a general one and a restricted one, where the latter is applied for moves of pinned pieces and for ep captures only. You can even go further and make a difference between "absolute pins" (where moving them is *always* illegal, as for pinned knights, diagonally pinned rooks, horizontally or vertically pinned bishops, horizontally pinned pawns, and diagonally pinned pawns where the pawn can't capture the pinning piece) and "relative pins", so that you can save the make-IsKingInCheck-unmake operation for all "absolute pins". My point was also that all that additional intelligence does not necessarily result in a considerable gain of performance, and that it will usually add complexity that can increase the number of bugs.

You are free to state that X and Y do not work for you. But if someone proposes Z and you say Z is incorrect then it is also up to you to either find something else than X, Y and Z that works for you, or find out which of your statements about X, Y, and Z is incorrect

[Henk]

Yes avoiding bugs is most important. That's why Skipper only counts material. But that's not enough to beat Fairy-max.

[Yesterday I heard there are three golden rules. Developing light pieces, at least one pawn in center, and castling.]

I think I can optimize my KingInCheck method a bit for the line between last move start square and the king contain blockers and when one blocker is found starting at the king, search along that line can be stopped.

Optimizing perft has less priority. But it can be a gain for it reduces testing time after implementation of move generation changed.

I don't do legal move generation when Skipper tries to play normal chess and that is necessary when computing perft.

[Henk]

Maybe it's an idea to organize a tournament where evaluation is limited to counting material only. See how many duplicate games are played.

[Sven]

I think I can optimize my KingInCheck method a bit for the line between last move start square and the king contain blockers and when one blocker is found starting at the king, search along that line can be stopped.

So obviously you have a separate KingInCheck function to detect illegal king moves and illegal check evasions, right? If so, how does it work?

[Henk]

At this moment it looks like this. Target is king. attacker is side to move.
A line is created between king square and lastMove.Start square using all possible queen moves.

Code: Select all

      public bool CanCapture(ColorSign attacker,  ulong target, IMoveBase lastMove)
        {
             PieceIterator pieceIter = null;

            if (lastMove != null && !(lastMove is EPMove))
            {
                ulong queenStartXRays = lastMove.Start.XRayMoves(ChessPiece.Sort.whiteQueen);
                ulong startAttackers = 0;
                if ((queenStartXRays & target) != 0)
                {
                    var line = queenStartXRays & ChessBoard.GetField(BitBoardIndex.Instance, target).XRayMoves(ChessPiece.Sort.whiteQueen); 
                    startAttackers |= Board.GetSliders(attacker)
                                                 & line;
               }
                else
                {
                    if ((lastMove.End.XRayMoves() & target) == 0)
                    {
                        return false;
                    }
                }
                pieceIter = new PieceIterator(PieceIterator.Direction.Forward);
                pieceIter.Reset(startAttackers | lastMove.End.BitCoord);
            }
            else
            {
                pieceIter = new PieceIterator(PieceIterator.Direction.Forward);
                pieceIter.Reset(Board.Pieces(attacker));
            }
          


            IPiece curPiece = null; 
            while ((curPiece = pieceIter.Next(ChessBoard)) != null)
            {             
                MoveBase move = curPiece.FindCaptureMove(target);
                if (move != null)
                    return true;
            }
            return false;
        }

First simple change is to reuse the iterator instead of creating new ones.

[Henk]

A line is created between king square and lastMove.Start square 'anding' all possible queen moves on both squares.