Truncated Principal Variation

[CheckersGuy]

In general your code to build a new PV is also unsafe since you rely on the PV of the child node (localPV) not having a greater length (which is the capacity in your case, not the actual PV length) than that of the parent node (cLine). That might break as soon as you introduce some extensions, but even without it I would not keep unsafe code. To overcome that problem you might as well add an explicit "size" member to PVLine, set it to 0 on construction and set it appropriately when building a new PV from current best move and "localPV". But even without that "optimization" you'd better do a correct bounds checking before assigning anything to cLine[p].

I am going to add that as well.
At least, I am getting the full PV now.

Good to read - so the initial problem of this thread is solved!

However, I tested a version, which used the PV for moveOrdering vs one that did not and saw virtually no difference.

Which would indicate that you did not implement using the PV for move ordering correctly ... How did you do it? The principal() function you have shown has a parameter "inPVLine" but you didn't use it.

I made a function that sorts the moves after they were generated. I tested whether the PV-Move actually appears first in the MoveList after sorting, so the sortMethod shouldnt be the issue.

Code: Select all

insertionSort(ArrayList<Move>sucessors,int ply, boolean inPVLine)

I give the PV_Move the highest score and sort the moves only when inPVLine is true.
InPVLine is true for the root and then as in the function principal.

Here is my Code for Iterative Deepening:

Code: Select all

       public void itertiveDeepening(int depth, long time,boolean print) {
        long endTime = System.currentTimeMillis() + time;
        Move currentBest = null;
        mainPVLine =new PVLine(depth);
        for (int i = 1; i <= depth;i++) {
            int value = principal(board, -150000, 150000, i, 0, mainPVLine, true, endTime);

            if (System.currentTimeMillis()>=endTime)
                break;
            currentBest = mainPVLine.line[0];

            if(print){
                System.out.print(String.format("Depth: %d and Value: %d", i, value) + "<<< ");
                printPrincipalVariation();
            }

      
        board.makeMove(currentBest);
    }

[Sven]

I made a function that sorts the moves after they were generated. I tested whether the PV-Move actually appears first in the MoveList after sorting, so the sortMethod shouldnt be the issue.

Code: Select all

insertionSort(ArrayList<Move>sucessors,int ply, boolean inPVLine)

I give the PV_Move the highest score and sort the moves only when inPVLine is true.
InPVLine is true for the root and then as in the function principal.

The question is, what is "the PV_Move" at an arbitrary full-width node in the tree?

The version of principal() that I saw did not use the inPVLine parameter. If you actually use it below the root then you would have to do it like this:

Code: Select all

for (all moves) {
    ...
    childIsInPV = inPVLine && currentMove == rootPV[ply];
    ... search(..., childIsInPV, ...);
    ...
}

The point is, you would need to pass the PV of the root node down the whole tree.

[CheckersGuy]

I made a function that sorts the moves after they were generated. I tested whether the PV-Move actually appears first in the MoveList after sorting, so the sortMethod shouldnt be the issue.

Code: Select all

insertionSort(ArrayList<Move>sucessors,int ply, boolean inPVLine)

I give the PV_Move the highest score and sort the moves only when inPVLine is true.
InPVLine is true for the root and then as in the function principal.

The question is, what is "the PV_Move" at an arbitrary full-width node in the tree?

The version of principal() that I saw did not use the inPVLine parameter. If you actually use it below the root then you would have to do it like this:

Code: Select all

for (all moves) {
    ...
    childIsInPV = inPVLine && currentMove == rootPV[ply];
    ... search(..., childIsInPV, ...);
    ...
}

The point is, you would need to pass the PV of the root node down the whole tree.

I actually saved the PVLine of the root search to a global variable, so I can access it at any time.
If I am in the sortFunktion I check for

Code: Select all

inPvLine==true && mainPVLine.line[ply].equals(move))

and assign the highest score to that move.

[Sven]

I made a function that sorts the moves after they were generated. I tested whether the PV-Move actually appears first in the MoveList after sorting, so the sortMethod shouldnt be the issue.

Code: Select all

insertionSort(ArrayList<Move>sucessors,int ply, boolean inPVLine)

I give the PV_Move the highest score and sort the moves only when inPVLine is true.
InPVLine is true for the root and then as in the function principal.

The question is, what is "the PV_Move" at an arbitrary full-width node in the tree?

The version of principal() that I saw did not use the inPVLine parameter. If you actually use it below the root then you would have to do it like this:

Code: Select all

for (all moves) {
    ...
    childIsInPV = inPVLine && currentMove == rootPV[ply];
    ... search(..., childIsInPV, ...);
    ...
}

The point is, you would need to pass the PV of the root node down the whole tree.

I actually saved the PVLine of the root search to a global variable, so I can access it at any time.
If I am in the sortFunktion I check for

Code: Select all

inPvLine==true && mainPVLine.line[ply].equals(move))

and assign the highest score to that move.

And how do you set inPvLine for the next recursion level?

[CheckersGuy]

I made a function that sorts the moves after they were generated. I tested whether the PV-Move actually appears first in the MoveList after sorting, so the sortMethod shouldnt be the issue.

Code: Select all

insertionSort(ArrayList<Move>sucessors,int ply, boolean inPVLine)

I give the PV_Move the highest score and sort the moves only when inPVLine is true.
InPVLine is true for the root and then as in the function principal.

The question is, what is "the PV_Move" at an arbitrary full-width node in the tree?

The version of principal() that I saw did not use the inPVLine parameter. If you actually use it below the root then you would have to do it like this:

Code: Select all

for (all moves) {
    ...
    childIsInPV = inPVLine && currentMove == rootPV[ply];
    ... search(..., childIsInPV, ...);
    ...
}

The point is, you would need to pass the PV of the root node down the whole tree.

I actually saved the PVLine of the root search to a global variable, so I can access it at any time.
If I am in the sortFunktion I check for

Code: Select all

inPvLine==true && mainPVLine.line[ply].equals(move))

and assign the highest score to that move.

And how do you set inPvLine for the next recursion level?

In my iterative Deepening Code I set inPVline to true. And then I pass inPVLine as a Parameter for the first move and set inPVLine to false for the second to last move.

[Sven]

I made a function that sorts the moves after they were generated. I tested whether the PV-Move actually appears first in the MoveList after sorting, so the sortMethod shouldnt be the issue.

Code: Select all

insertionSort(ArrayList<Move>sucessors,int ply, boolean inPVLine)

I give the PV_Move the highest score and sort the moves only when inPVLine is true.
InPVLine is true for the root and then as in the function principal.

The question is, what is "the PV_Move" at an arbitrary full-width node in the tree?

The version of principal() that I saw did not use the inPVLine parameter. If you actually use it below the root then you would have to do it like this:

Code: Select all

for (all moves) {
    ...
    childIsInPV = inPVLine && currentMove == rootPV[ply];
    ... search(..., childIsInPV, ...);
    ...
}

The point is, you would need to pass the PV of the root node down the whole tree.

I actually saved the PVLine of the root search to a global variable, so I can access it at any time.
If I am in the sortFunktion I check for

Code: Select all

inPvLine==true && mainPVLine.line[ply].equals(move))

and assign the highest score to that move.

And how do you set inPvLine for the next recursion level?

In my iterative Deepening Code I set inPVline to true. And then I pass inPVLine as a Parameter for the first move and set inPVLine to false for the second to last move.

But not each first move of an arbitrary node belongs to the PV. The PV is just one single path from the root to one node. You can only set inPVLine to true on the first move of a node that was already entered with inPVLine == true.

[CheckersGuy]

Maybe I am totally confused but If I pass PVLine=true as a Parameter for the root and when I Encounter the first move of a child's sucessor node pass the pvLine Parameter and for every other move I pass pVLine=false, wouldn`t that be it ? Then pvLine would only be true if a child's parent node was a first move.

I dont know why I can't get this to work.

[Sven]

Maybe I am totally confused but If I pass PVLine=true as a Parameter for the root and when I Encounter the first move of a child's sucessor node pass the pvLine Parameter and for every other move I pass pVLine=false, wouldn`t that be it ? Then pvLine would only be true if a child's parent node was a first move.

I dont know why I can't get this to work.

That is exactly what I meant. If it does not work then there are other reasons, and my next question would be "what exactly does not work?".

[CheckersGuy]

Maybe I am totally confused but If I pass PVLine=true as a Parameter for the root and when I Encounter the first move of a child's sucessor node pass the pvLine Parameter and for every other move I pass pVLine=false, wouldn`t that be it ? Then pvLine would only be true if a child's parent node was a first move.

I dont know why I can't get this to work.

That is exactly what I meant. If it does not work then there are other reasons, and my next question would be "what exactly does not work?".

That there is no difference between using PVMove-Ordering and not. I would expect quite a jump in Performance but apparently there is None.

[Sven]

Maybe I am totally confused but If I pass PVLine=true as a Parameter for the root and when I Encounter the first move of a child's sucessor node pass the pvLine Parameter and for every other move I pass pVLine=false, wouldn`t that be it ? Then pvLine would only be true if a child's parent node was a first move.

I dont know why I can't get this to work.

That is exactly what I meant. If it does not work then there are other reasons, and my next question would be "what exactly does not work?".

That there is no difference between using PVMove-Ordering and not. I would expect quite a jump in Performance but apparently there is None.

By "jump in performance" you obviously mean to reduce the tree size for a fixed-depth search. That should be the result, right. So if trying the PV of the previous iteration first does not result in a smaller tree compared to not doing so then there is still some problem in your search.

For a given position where you do not observe any improvement, you could print the tree, maybe limited to some maximum depth like 3. Do so with and without PV-based ordering, and compare the trees.