Simplifying code

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Pio
Posts: 196
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: Simplifying code

Post by Pio » Sun Aug 02, 2020 1:39 pm

Henk wrote:
Sun Aug 02, 2020 12:18 pm
Pio wrote:
Sun Aug 02, 2020 11:41 am
Henk wrote:
Sun Aug 02, 2020 10:40 am
Looks like C# CopyTo is faster than Clone

Code: Select all

 
   private ChessBoardBits Copy()
        { 
            var piecesCopy = new UInt64[(int)none];
            pieces.CopyTo(piecesCopy, 0);        
            return new ChessBoardBits(piecesCopy, Other);
        }
Why not use structs?
Yes that's an idea. I should try that. Hardly ever used structs by the way in C#. Already forgot they existed.
Most people use structs very rarely. I like them and I use them in my engine for my board representation. If I need a copy of my board I just write boardCopy = board. For me it is not a big problem that I always copy the board and that structs are passed by value since my board representation is only 3*64 bits long and most of my functions belongs to my board struct. It will be fun to see how much it simplifies your engine and how much faster it will become 😁

Joost Buijs
Posts: 1176
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Simplifying code

Post by Joost Buijs » Sun Aug 02, 2020 5:40 pm

Pio wrote:
Sun Aug 02, 2020 1:39 pm
Most people use structs very rarely. I like them and I use them in my engine for my board representation. If I need a copy of my board I just write boardCopy = board. For me it is not a big problem that I always copy the board and that structs are passed by value since my board representation is only 3*64 bits long and most of my functions belongs to my board struct. It will be fun to see how much it simplifies your engine and how much faster it will become 😁
Maybe I'm not like most people because I use structs for almost everything that is 'structable'. But I don't get it how you are able to store the whole position in just 3 64 bit words and do anything useful with it. I know you can store a position in something like 21 or 22 bytes, but when you want to use it for a serious chess engine you'll need a lot more information like a 64 byte piece-index, two or three 64 bit hashes, en-passant square, game-phase, and a lot of other stuff.

In my chess engine the position has a size of 32 64 bit integers and that is something you don't want to copy.

Pio
Posts: 196
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: Simplifying code

Post by Pio » Sun Aug 02, 2020 5:46 pm

Joost Buijs wrote:
Sun Aug 02, 2020 5:40 pm
Pio wrote:
Sun Aug 02, 2020 1:39 pm
Most people use structs very rarely. I like them and I use them in my engine for my board representation. If I need a copy of my board I just write boardCopy = board. For me it is not a big problem that I always copy the board and that structs are passed by value since my board representation is only 3*64 bits long and most of my functions belongs to my board struct. It will be fun to see how much it simplifies your engine and how much faster it will become 😁
Maybe I'm not like most people because I use structs for almost everything that is 'structable'. But I don't get it how you are able to store the whole position in just three 64 bit words and do anything useful with it. I know you can store a position in something like 21 or 22 bytes, but when you want to use it for a serious chess engine you'll need a lot more information like a 64 byte piece-index, two or three 64 bit hashes, en-passant square, game-phase, and a lot of other stuff.
I am not saying that I am doing a serious chess engine 😳. I just did it for fun to see if it was possible.

Joost Buijs
Posts: 1176
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Simplifying code

Post by Joost Buijs » Sun Aug 02, 2020 5:47 pm

Pio wrote:
Sun Aug 02, 2020 5:46 pm
Joost Buijs wrote:
Sun Aug 02, 2020 5:40 pm
Pio wrote:
Sun Aug 02, 2020 1:39 pm
Most people use structs very rarely. I like them and I use them in my engine for my board representation. If I need a copy of my board I just write boardCopy = board. For me it is not a big problem that I always copy the board and that structs are passed by value since my board representation is only 3*64 bits long and most of my functions belongs to my board struct. It will be fun to see how much it simplifies your engine and how much faster it will become 😁
Maybe I'm not like most people because I use structs for almost everything that is 'structable'. But I don't get it how you are able to store the whole position in just three 64 bit words and do anything useful with it. I know you can store a position in something like 21 or 22 bytes, but when you want to use it for a serious chess engine you'll need a lot more information like a 64 byte piece-index, two or three 64 bit hashes, en-passant square, game-phase, and a lot of other stuff.
I am not saying that I am doing a serious chess engine 😳. I just did it for fun to see if it was possible.
All right, I understand.

Pio
Posts: 196
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: Simplifying code

Post by Pio » Sun Aug 02, 2020 5:57 pm

Joost Buijs wrote:
Sun Aug 02, 2020 5:47 pm
Pio wrote:
Sun Aug 02, 2020 5:46 pm
Joost Buijs wrote:
Sun Aug 02, 2020 5:40 pm
Pio wrote:
Sun Aug 02, 2020 1:39 pm
Most people use structs very rarely. I like them and I use them in my engine for my board representation. If I need a copy of my board I just write boardCopy = board. For me it is not a big problem that I always copy the board and that structs are passed by value since my board representation is only 3*64 bits long and most of my functions belongs to my board struct. It will be fun to see how much it simplifies your engine and how much faster it will become 😁
Maybe I'm not like most people because I use structs for almost everything that is 'structable'. But I don't get it how you are able to store the whole position in just three 64 bit words and do anything useful with it. I know you can store a position in something like 21 or 22 bytes, but when you want to use it for a serious chess engine you'll need a lot more information like a 64 byte piece-index, two or three 64 bit hashes, en-passant square, game-phase, and a lot of other stuff.
I am not saying that I am doing a serious chess engine 😳. I just did it for fun to see if it was possible.
All right, I understand.
If you don’t try to do a serious chess engine you can’t fail 💡.

Actually I wanted to learn a little bit of bit manipulation but mostly I wanted to test some ideas I have for search and evaluation.

I hope my engine in the next year or two will be okay at finding mates and very good at strangling the position. It will be fun to try to draw a lot better engines by playing completely different chess.

Joost Buijs
Posts: 1176
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Simplifying code

Post by Joost Buijs » Mon Aug 03, 2020 6:36 am

Pio wrote:
Sun Aug 02, 2020 5:57 pm
Joost Buijs wrote:
Sun Aug 02, 2020 5:47 pm
Pio wrote:
Sun Aug 02, 2020 5:46 pm
Joost Buijs wrote:
Sun Aug 02, 2020 5:40 pm
Pio wrote:
Sun Aug 02, 2020 1:39 pm
Most people use structs very rarely. I like them and I use them in my engine for my board representation. If I need a copy of my board I just write boardCopy = board. For me it is not a big problem that I always copy the board and that structs are passed by value since my board representation is only 3*64 bits long and most of my functions belongs to my board struct. It will be fun to see how much it simplifies your engine and how much faster it will become 😁
Maybe I'm not like most people because I use structs for almost everything that is 'structable'. But I don't get it how you are able to store the whole position in just three 64 bit words and do anything useful with it. I know you can store a position in something like 21 or 22 bytes, but when you want to use it for a serious chess engine you'll need a lot more information like a 64 byte piece-index, two or three 64 bit hashes, en-passant square, game-phase, and a lot of other stuff.
I am not saying that I am doing a serious chess engine 😳. I just did it for fun to see if it was possible.
All right, I understand.
If you don’t try to do a serious chess engine you can’t fail 💡.

Actually I wanted to learn a little bit of bit manipulation but mostly I wanted to test some ideas I have for search and evaluation.

I hope my engine in the next year or two will be okay at finding mates and very good at strangling the position. It will be fun to try to draw a lot better engines by playing completely different chess.
It all depends upon the evaluation-function. Most A-B engines have a rather primitive evaluation-function with a very advanced search, with NN engines it's exactly the other way around. My guess is that there must be something in between 'a golden mean' which eventually will give the best results.

I programmed my first chess engine back in 1977, so I'm getting a bit chess tired. Currently I'm busy with totally different things, but I keep watching for new developments.

Sven
Posts: 3883
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Simplifying code

Post by Sven » Mon Aug 03, 2020 11:17 pm

Henk wrote:
Fri Jul 31, 2020 11:20 am
[...] nested ?: at the last statement of this method are hardly readable.

Code: Select all

    (IMovePrioQ, IMoveBase, int, int) NextMove( SearchParam p, IMovePrioQ prioQ, int stage, int i, bool allowStandPat)
        {         
            var end = i >= prioQ.Count();
            var (j, nextStage) = end ? (0, stage+1) : (i, stage);
            var nextPrioQ = (end && (nextStage == 2 || nextStage == 3)) ? new MovePrioQ(  
                       (nextStage == 2 ? p.position.CollectCapturesPromotions(true): p.position.CollectNonCaptures()
                       ).Select(m =>
                         (ComputePriority(PSQTableEval, allowStandPat, KillerMoves,
                          MoveRatings, m, p.position, p.depth), m)).ToImmutableList()).Sort()
                 : prioQ;
            var mv = j < nextPrioQ.Count() ? nextPrioQ[j]: null;
            return  (mv == null 
                || nextStage > 1 &&   !LegalMove(p.inCheck, mv, p.position)
                || nextStage == 3 && allowStandPat && !p.position.GivesCheck(mv)
                || nextStage > 3
                    )  
            ? (nextStage > 3) ? (nextPrioQ, null, -1, -1): NextMove(p, nextPrioQ, nextStage, j + 1, allowStandPat)        
            : (nextPrioQ, mv, j, nextStage);
        }
  
I could imagine the following might be slightly more readable, and maybe even a bit more accurate:

Code: Select all

IMovePrioQ CollectPseudoLegalMoves(SearchParam p, int stage, bool allowStandPat)
{
    // ASSERT(stage == 2 || stage == 3);
    return new MovePrioQ((stage == 2 ? p.position.CollectCapturesPromotions(true): p.position.CollectNonCaptures())
                            .Select(m => (ComputePriority(PSQTableEval, allowStandPat, KillerMoves, MoveRatings, m, p.position, p.depth), m))
                            .ToImmutableList()
                        ).Sort();
}

(IMovePrioQ, IMoveBase, int, int) NextMove( SearchParam p, IMovePrioQ prioQ, int stage, int i, bool allowStandPat)
{
    // ASSERT(stage >= 1 && stage <= 3);
    // ASSERT(i >= 0);
    if (stage > 3)
    {
        return (prioQ, null, -1, -1);
    }
    if (i >= prioQ.Count())
    {
        if (stage + 1 > 3)
        {
            return (prioQ, null, -1, -1);
        }
        return NextMove(p, CollectPseudoLegalMoves(p, stage + 1, allowStandPat), stage + 1, 0, allowStandPat);
    }
    var mv = prioQ[i];
    if ((stage > 1  && !LegalMove(p.inCheck, mv, p.position))
     || (stage == 3 && allowStandPat && !p.position.GivesCheck(mv)))
    {
        return NextMove(p, prioQ, stage, i + 1, allowStandPat);
    }
    // NOTE:
    // I suggest to switch the order of "i" and "stage" in the return tuple for consistency with the
    // order of parameters of NextMove()
    return (prioQ, mv, stage, i);
}
Some comments:
1) I moved the pure move generation part into a separate function CollectPseudoLegalMoves().
2) I tried to avoid ?: expressions as much as possible, and only used them when their meaning was immediately obvious.
3) I did not follow the "single point of return" philosophy since I favor the "early return in special case" philosophy which also saves a lot of indentation. One may of course insert some "else" or "else if" statements if that style is preferred.
4) I started by expanding all logical paths through the code into separate blocks, then removed all unreachable parts (due to conditions that were always false), then simplified again by avoiding variables that were used only once.
5) By doing the above, I think I also avoided a pathological case where a call of NextMove() with stage < 3, i >= prioQ.Count() and nextPrioQ.Count() == 0 led to a recursive call of NextMove() fed again with nextPrioQ and i=1.
6) I do not like the approach of replacing loops by recursion very much, I just left it in here in order to not change everything at once ...
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

Henk
Posts: 6556
Joined: Mon May 27, 2013 8:31 am

Re: Simplifying code

Post by Henk » Tue Aug 04, 2020 9:57 am

I copy pasted your code in my solution. But speed got much worse. Factor two.
Don't know what caused it.

Earlier I did a rewrite myself adding some ugly construction to prevent position.GivesCheck(mv) executing unnecessarily.
This is what it is now. Using your CollectPseudoLegalMoves method by the way plus early return when nextStage > 3

Code: Select all

 (IMovePrioQ, IMoveBase, int, int) NextMove(SearchParam p, IMovePrioQ prioQ, int stage, int i, bool allowStandPat)
        {
            var end = i >= prioQ.Count();
            var (j, nextStage) = end ? (0, stage + 1) : (i, stage);
            var nextPrioQ = (end && (nextStage == 2 || nextStage == 3)) ?
                            CollectPseudoLegalMoves(p, nextStage, allowStandPat)
                 : prioQ;
            if (nextStage > 3)
            {
                return (nextPrioQ, null, -1, -1);
            }
            var mv = j < nextPrioQ.Count() ? nextPrioQ[j] : null;
            var noMove =
                 mv == null
                || nextStage > 1 && !LegalMove(p.inCheck, mv, p.position);

            bool? noMoreMovesInStandPat = null;
            if (!noMove)
            {
                noMoreMovesInStandPat = nextStage == 3 && allowStandPat && p.position.GivesCheck(mv);
                noMove = noMoreMovesInStandPat.Value;
            }

            if (noMove)
            {
                if (noMoreMovesInStandPat.HasValue && noMoreMovesInStandPat.Value)
                    return (nextPrioQ, null, -1, -1);
                else
                    return NextMove(p, nextPrioQ, nextStage, j + 1, allowStandPat);
            }
            else
                return (nextPrioQ, mv, j, nextStage);
        }

Sven
Posts: 3883
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Simplifying code

Post by Sven » Tue Aug 04, 2020 1:00 pm

Henk wrote:
Tue Aug 04, 2020 9:57 am
I copy pasted your code in my solution. But speed got much worse. Factor two.
Don't know what caused it.
Oops, I guess that's because I left a little trap for you in my code snippet :lol:

Code: Select all

    // NOTE:
    // I suggest to switch the order of "i" and "stage" in the return tuple for consistency with the
    // order of parameters of NextMove()
    return (prioQ, mv, stage, i);
should be

Code: Select all

    return (prioQ, mv, i, stage);
if you do not adapt the caller of NextMove() ...
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

Henk
Posts: 6556
Joined: Mon May 27, 2013 8:31 am

Re: Simplifying code

Post by Henk » Tue Aug 04, 2020 1:27 pm

No i did also adapt order of the caller. So I don't understand why it was about two times slower.

But nevermind. I used some ideas of your solution.

I now have this:

Code: Select all

       (IMovePrioQ, IMoveBase, int, int) NextMove(SearchParam p, IMovePrioQ prioQ, int stage, int i, bool allowStandPat)
        {
            if (stage > 3 || i >= prioQ.Count() && stage  == 3)
            {
                return (prioQ, null, -1, -1);
            }
            
            if (i >= prioQ.Count())
            {
                return NextMove(p, CollectPseudoLegalMoves(p, stage + 1, allowStandPat), stage + 1, 0, allowStandPat);
            }
            var mv = prioQ[i];
            var noMove = stage > 1 && !LegalMove(p.inCheck, mv, p.position);

            bool? noMoreMovesInStandPat = null;
            if (!noMove)
            {
                noMoreMovesInStandPat = stage == 3 && allowStandPat && p.position.GivesCheck(mv);
                noMove = noMoreMovesInStandPat.Value;
            }

            if (noMove)
            {
                if (noMoreMovesInStandPat.HasValue && noMoreMovesInStandPat.Value)
                    return (prioQ, null, -1, -1);
                else
                    return NextMove(p, prioQ, stage, i + 1, allowStandPat);
            }
            else
                return (prioQ, mv, i, stage);
        }

Post Reply