Problem with the PV extraction.

[alexlitov]

Hello.

I am currently trying to make a chess-based game (lots of different pieces, custom board size etc).
So i neded to make some AI to play against.

I wrote standart minimax and it works fine, but when i decided to implement PV extraction and storage for faster move ordering i got the problem: PV line i get from the script makes 0 sense).
For example in this position https://ibb.co/b3WKCLm , it makes move Qb3 move (which is i guess fine, getting max depth 5 ), but PV is ( Qb3, Qd5, ed, Qh4.... what???... etc);

I thought that its a search issue, so i played a couple of games with it. It play somewhat fine, with no terrible blunders (except occasional, i suppose due to horizon - i did not implement Qiescence yet)
I am inexperienced programmer, so any help will be appreciated.

Code of the search (with PV update in it)
- i make it in Unity, so it is c# code.

Code: Select all

 
   public int Negamax (aiBoard mBoard, Int32 move, int a, int b, int cDepth)
    {
        int curr_score = 0;
        int max_piece_score = 0;
        int i = 0;
        Moves toCheck = new Moves();
        List<Int32> sortedList = new List<Int32>();

        if (move != M_NOMOVE)
        {
            //   Score -= GetMoveDelta()
            mBoard = MakeMove(move, mBoard);
        }

        pv_length[cDepth] = cDepth;

        if (cDepth == 0)
        {
            a = Score(mBoard);
            nodes_searched++;
        }
        else
        {
            toCheck = BadMoveGenerator(mBoard.isBlackMove, mBoard);

            foreach (Int32 m in toCheck.PromotingMoves)
            {
                curr_score = -Negamax(mBoard, m, line, -b, -a, cDepth - 1);
                if (curr_score > a)
                {
                    if (curr_score >= b)
                    {
                        a = b;
                        goto ReturnMove;
                    }

                    a = curr_score;
                    MoveFound[cDepth] = m;

                    PV_Line[cDepth, cDepth] = m;
                    for (i = cDepth + 1; i < maxDepth; i++)
                            PV_Line[cDepth, i] = PV_Line[cDepth + 1, i];

                       
                }

            }
            foreach (Int32 m in toCheck.CaptureMoves)
            {... exact the same as above, but Capture moves as input
               
            }
            foreach (Int32 m in toCheck.QMoves)
            {... exact the same as above, but Quiet moves as input            }
        }
    ReturnMove:

        mBoard = TakeMove(move, mBoard);

        return a;
    }

I visualize PV line as

Code: Select all

Debug.Log(PrintMove(PV_Line[6, 6]) + " " + PrintMove(PV_Line[5, 5]) ...

I tryed to print whole PV_Line array, in also do not make sense.
I am confused now, i guess my code is terribly wrong somewhere, but after 2 days of struggling i decided to seek help.

[H.G.Muller]

The code looks a bit different from what I am used to. Because normally one also keeps a variable for the 'ply level' of each node (say cPly), which strictly increments by 1 in a daughter, next to cDepth, which is the remaining search depth. Because in a more advanced search you will have reductions and extensions, so that cDepth will not always decrement by exactly 1. You could then get gaps or overwrites when you use it as index in the PV array. So normally one uses cPly for that, and it counts in the other direction.

But my impression is that you copy the wrong part of the tri-angular array: the daughter PV should be in PV_Line[cDepth+1, 0...cDepth], not in PV_Line[cDepth+1, cDepth+1 ... maxDepth]. I also think it is wrong to use the diagonal of the tri-angular array; at the end the PV should be in PV_Line[maxDepth, 0...maxDepth]. The PV is not the last branch you would search, so you will search many side branches after you have found the PV. And these will occasionally have moves that score in window, and cause the PV_Line array to be written, overwriting what was the real PV.

[alexlitov]

Thank you so much!

Apparently

Because normally one also keeps a variable for the 'ply level' of each node (say cPly), which strictly increments by 1 in a daughter, next to cDepth, which is the remaining search depth.

this was the main problem. I used TSCP code for a reference, but (as usual) was too rush and straight up assumed that ply is used as sDepth variable in my code. And after i got no results, i tied to edit it in order to make it work.

After this and some changes to the print code i was able to get a PV line.