Simplifying code

[Henk]

Now I have this for alpha beta search. Don't like it. Too many if statements.

Code: Select all

  
 ISearchResult SearchMoves(IChessPosition position, IMovePrioQ prioQ, IVariation initialVariation, int depth, 
                                     int plyCount, int lb, int ub)
        {
            if (!(TimeManagement.SearchExpired(Level))
                && (initialVariation == null || initialVariation.Value < ub)
                && prioQ.Count() > 0)
            {
                var mv = prioQ.Top();
                var firstVariation = SearchMove(position, mv, initialVariation, depth, plyCount, lb, ub);
                if (firstVariation == null)
                {
                    return null;
                }
                else
                {
                    var nextLb = Max(lb, firstVariation.Value);
                    var remPrioQ = prioQ.Pop();
                    var remResult = SearchMoves(position, remPrioQ, firstVariation, depth, plyCount, nextLb, ub);
                    if (firstVariation != initialVariation)
                    {
                        return ResultBuilder.BuildResult(firstVariation, remResult);
                    }
                    else
                    {
                        return remResult;
                    }
                }
            }
            return null;
        }

What about reordering it like that:

Code: Select all

ISearchResult SearchMoves(IChessPosition position, IMovePrioQ prioQ, IVariation initialVariation, int depth, int plyCount, int lb, int ub)
{
    if (TimeManagement.SearchExpired(Level)
        || (initialVariation && initialVariation.Value >= ub)
        || prioQ.Count() <= 0)
    {
        return null;
    }
    
    var mv = prioQ.Top();
    var firstVariation = SearchMove(position, mv, initialVariation, depth, plyCount, lb, ub);
    if (firstVariation == null)
    {
        return null;
    }
    var nextLb = Max(lb, firstVariation.Value);
    var remPrioQ = prioQ.Pop();
    var remResult = SearchMoves(position, remPrioQ, firstVariation, depth, plyCount, nextLb, ub);
    if (firstVariation != initialVariation)
    {
        return ResultBuilder.BuildResult(firstVariation, remResult);
    }
    return remResult;
}    

Less indentations and if-else blocks by exploiting the "return" statements.

I would have proposed almost the same, for the same reasons. It would improve readability. However, it would not reduce the number of if's. Addressing that would require to know a bit more background.

@Henk: What does "return null" mean in this context? Encountered an illegal move? A leaf node (e.g. mate/stalemate/other draw)? How and where do you differentiate between these?

There is another issue, even a major one I believe: SearchMoves() will be called recursively N times to process a move list ("move priority queue") of length N, unless there is some cutoff inbetween. That means: searching to depth D with an average move list size of N implies that D*N recursive calls are made. This will create really a huge overhead at runtime caused by a very huge runtime stack and a lot of temporary objects being created and destroyed on the fly, which I consider to be a bad design. E.g. for processing one node at one level in the search tree there will be up to N internal move priority queue objects of length N, N-1, N-2, ..., 1, caused by "var remPrioQ = prioQ.Pop();" in combination with the mentioned tail recursion strategy. I would recommend a classical loop instead ...

Finally I do not understand the alpha-beta algorithm in that implementation yet. Where is the code for the AB cutoff? The condition "initialVariation.Value >= ub" does not look like it to me since it causes a "return null" instead of returning a SearchResult carrying either "initialVariation.Value" or "ub" as its value.

Ok here is the loop version. There even was a bug in it for I forgot to ignore curResult if time is up.
(Code below assumes iterative deepening move goes first)
Don't know if recursive version is good enough if you implement prioq as a balanced tree.
Then remPrioQ = prioQ.Pop() is O(log n) .

Code: Select all

     ISearchResult SearchMoves(IChessPosition position, IPositionHistory positionHistory, 
                                  IMovePrioQ prioQ, ISearchResult resultSofar, int depth, 
                                  int plyCount, int lb, int ub)
        {
            var curResult = resultSofar;
            foreach (var mv in prioQ)
            {
                if (TimeManagement.SearchExpired(Level))
                {
                    if (depth == Level)
                    {
                        return curResult;
                    }
                    else
                    {
                        return resultSofar;
                    }
                }
                else if ( curResult.PV != null && curResult.PV.Value >= ub )
                {
                    return curResult;
                }
                else {
                    curResult = SearchMove(position, positionHistory, mv, curResult, depth, plyCount, lb, ub);
                    if (curResult.PV != null)
                    {
                        lb = Max(lb, curResult.PV.Value);
                    }
                }
            }
            return curResult;
        }

[Henk]

Made position immutable so now I get this:

Code: Select all

 var nextPos = position.Move(mv);
 var key = KeyFactory.BuildKey(position.Board);
 var nextPositionHistory = positionHistory.Add(key);
 var nextPsqValue = psqValue + position.CurPlayer * mv.PieceSquareDelta(position, PSQTableEval.PieceSquareTable);

Actually position history and piece square value should be part of position. But sometimes you don't need them.
So copying and updating them would not be necessary when making a move in some cases.

Also made transposition table immutable. Code is running slow by the way.

So code doesn't get simpler.

What will be next step. Creating a monad for counting nodes or handling search result when time is up?

[bob]

Yes looks better. But I saw a video about monads recently. Although i am not sure I understand it.
Don't know anything about category theory.

So maybe I could use something like a monad to hide some obvious recurring tests.

Monad is a functor plus a flatten operation I understood.
Already unfamiliar with functors.

Good to hear that you think a lot about theory ... But what is your goal? To have a working chess engine that plays decent chess and has source code without bugs that can be maintained and changed quite easily (which is somehow related to "being simple" and "you like it"!)? Or to have an engine that matches common formal theories?

I hate bugs and code i can't understand or change easily.
Today and previous week I had to undo my changes after repairing 1000 compile time errors. Much misery.
Almost impossible to replace bitboards by something else in my source code.

So code should be written such that it is easy to make changes. That is most important.

my comment to the above is the multiple returns make code harder to read. The cleanest function has one entry and one exit. (hard to have more than one entry but in ASM or old FORTRAN it was easy to do). It sometimes helps (multiple returns) but often it makes the code harder to read unless you have long blocks of code, each with its own return. No point making it hard to read, which makes it hard to modify.

[Henk]

My C# code for computing perft using LINQ. Using LinQ only makes it slower.

Code: Select all

      public static ulong Perft(IChessPosition pos, int depth)=>          
            depth == 1 ? (ulong)ListLegalMoves(pos, pos.InCheck(null, OpponentColor(pos.CurPlayerColor))).Count
            : ListLegalMoves(pos, pos.InCheck(null, OpponentColor(pos.CurPlayerColor)))
              .Select(mv => Perft(pos.Move(mv), depth - 1)).Aggregate((x,y)=> y= x + y);
  

Pity C# has not much room for let expressions.Otherwise I would write
let moves = ListLegalMoves(pos, pos.InCheck(null, OpponentColor(pos.CurPlayerColor) in ..

[odomobo]

Instead of calling .Aggregate(), you can call .Sum() to simplify. Even though the performance for perft isn't the biggest concern, there are 2 issues with using LinQ IMO:

1. It creates additional objects, which need to be GCd.
2. You lose some control over the sequence in which the code is executed.

It can be really convenient for things that aren't in a tight loop, though.

[Henk]

Ok Sum works if I return long instead of ulong.

Another example of linQ in my code. This time for collecting capture moves during move generation. One of most expensive operations.

Code: Select all

       public IImmutableList<IMoveBase> CollectCaptures(ulong source, ulong target,  
            bool excludePromotions) =>
             new BitBoardIterator(source).Select(b =>
              {
                  var sq = BoardSquares[b];
                  var sort = Board.PieceSort(sq);
                  return CollectCaptures(sq.Moves(sort, Board.Occupiers) & target,
                                  sq.MovesDict[(int)sort], excludePromotions);
              }
            ).Aggregate((x, y) => x.AddRange(y));
        

        private IImmutableList<IMoveBase> CollectCaptures( ulong captures, BitCoordMoveDict mvDict, 
                                                            bool excludePromotions)
             => new BitBoardIterator(captures)
                          .Where(e=>!(excludePromotions && mvDict[e] is Promotion))
                          .Select(e=>mvDict[e])
                          .ToImmutableList();

By the way using immutable lists in my source code is even more expensive. Wasting 30% of cpu time.

[Henk]

Error. It is not immutableList but immutable dictionary making it slow.

Looks like I'm an expert in writing horrible code. For instance this one.
I mean 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);
        }
  

[Sven]

Looks like I'm an expert in writing horrible code. For instance this one.
I mean nested ?: at the last statement of this method are hardly readable.

Not the only reason ...

Recursive call of NextMove()? Why?

What is the purpose of variable "j"? Maybe choose a better name ... "i" can be understood from the context ...

Better use symbolic constants instead of magic numbers 1, 2, 3 for the various stages ...

Why do you try to put as much code as possible into one line?

Why do I get the feeling that this method has a bunch of side effects that can hardly be controlled?

Keep it simple and stupid

[Henk]

Looks like I'm an expert in writing horrible code. For instance this one.
I mean nested ?: at the last statement of this method are hardly readable.

Not the only reason ...

Recursive call of NextMove()? Why?

What is the purpose of variable "j"? Maybe choose a better name ... "i" can be understood from the context ...

Better use symbolic constants instead of magic numbers 1, 2, 3 for the various stages ...

Why do you try to put as much code as possible into one line?

Why do I get the feeling that this method has a bunch of side effects that can hardly be controlled?

Keep it simple and stupid

- Tried to write it functional. So recursion instead of loops.
- j is succesor of i
- yes for debugging nested expressions is terrible. Although there will be more temporary variables with silly names.

Don't understand why this method would give side effects. Or what do you mean.
Reason for latests rewrites was to minimize side effects as much as possible.

Looks like Initial stupid code was best. Rewrite only makes it less natural or divergent from initial idea.
Its like gumming in a drawing. I remember teacher said use gum sparingly.

By the way when nextStage == 3 && allowStandPat && !p.position.GivesCheck(mv) method should terminate while it doesn't.
Instead It calls nextmove and terminates. So bit inefficient/clumsy.

[Henk]

No matter what. You can't optimize this:

Code: Select all

       public ulong StraightMoves(ulong occupiers) => 
            StraightMovesArr[((StraightOcc & occupiers) * StraightMagic) >> StraightNShift];

        public ulong DiagonalMoves(ulong occupiers) =>
            DiagonalMovesArr[((DiagonalOcc & occupiers) * DiagonalMagic) >> DiagonalNShift];