sorting at root

[Guetti]

Ok, I just found a terrible bug in my code, which is to embarrassing to even speak off. But the root off the problem is in the sorting of the moves at the root.
The plan is to take the number of nodes that are searched for each move at the root and use it as a weight to sort the move at the root, meaning more nodes (larger subtree) equals in a higher score. Moves with higher scores are searched first.
I don't know if this is the best way to sort at root, I think I stole the idea from Bob, but it currently doesn't matter that much, and it is a method that is implementable in my very rudimentary search.
Now the problem is, the nodecount is stored in a unsigned long long, whereas my sorting values are normal ints. This implies that I have to scale down the nodecounts in order not to overflow the sorting values. And I wonder how this could best be done, not leading to a division by zero error like my current approach. (lol, now I spilled the beans anyway).

[Dann Corbit]

Ok, I just found a terrible bug in my code, which is to embarrassing to even speak off. But the root off the problem is in the sorting of the moves at the root.
The plan is to take the number of nodes that are searched for each move at the root and use it as a weight to sort the move at the root, meaning more nodes (larger subtree) equals in a higher score. Moves with higher scores are searched first.
I don't know if this is the best way to sort at root, I think I stole the idea from Bob, but it currently doesn't matter that much, and it is a method that is implementable in my very rudimentary search.
Now the problem is, the nodecount is stored in a unsigned long long, whereas my sorting values are normal ints. This implies that I have to scale down the nodecounts in order not to overflow the sorting values. And I wonder how this could best be done, not leading to a division by zero error like my current approach. (lol, now I spilled the beans anyway).

It seems simpler to change your comparison function/method than to change the node counts.

Post the code that performs the ordering and I am sure that someone can fix it for you.

[Guetti]

Ok, I just found a terrible bug in my code, which is to embarrassing to even speak off. But the root off the problem is in the sorting of the moves at the root.
The plan is to take the number of nodes that are searched for each move at the root and use it as a weight to sort the move at the root, meaning more nodes (larger subtree) equals in a higher score. Moves with higher scores are searched first.
I don't know if this is the best way to sort at root, I think I stole the idea from Bob, but it currently doesn't matter that much, and it is a method that is implementable in my very rudimentary search.
Now the problem is, the nodecount is stored in a unsigned long long, whereas my sorting values are normal ints. This implies that I have to scale down the nodecounts in order not to overflow the sorting values. And I wonder how this could best be done, not leading to a division by zero error like my current approach. (lol, now I spilled the beans anyway).

It seems simpler to change your comparison function/method than to change the node counts.

Post the code that performs the ordering and I am sure that someone can fix it for you.

Ok, if I get your point I could just use an array of uint64 at the root for the sorting. Would be a solution, yes.

[bob]

Ok, I just found a terrible bug in my code, which is to embarrassing to even speak off. But the root off the problem is in the sorting of the moves at the root.
The plan is to take the number of nodes that are searched for each move at the root and use it as a weight to sort the move at the root, meaning more nodes (larger subtree) equals in a higher score. Moves with higher scores are searched first.
I don't know if this is the best way to sort at root, I think I stole the idea from Bob, but it currently doesn't matter that much, and it is a method that is implementable in my very rudimentary search.
Now the problem is, the nodecount is stored in a unsigned long long, whereas my sorting values are normal ints. This implies that I have to scale down the nodecounts in order not to overflow the sorting values. And I wonder how this could best be done, not leading to a division by zero error like my current approach. (lol, now I spilled the beans anyway).

The simplest approach is to always put the PV move at the top, by artificially inflating its node count to the max value you can store. Let the others get sorted by node count and don't use anything else at all. This works and is what I have been doing for a long time... That way you don't have to co-mingle ints and long long ints...

[Dann Corbit]

Ok, I just found a terrible bug in my code, which is to embarrassing to even speak off. But the root off the problem is in the sorting of the moves at the root.
The plan is to take the number of nodes that are searched for each move at the root and use it as a weight to sort the move at the root, meaning more nodes (larger subtree) equals in a higher score. Moves with higher scores are searched first.
I don't know if this is the best way to sort at root, I think I stole the idea from Bob, but it currently doesn't matter that much, and it is a method that is implementable in my very rudimentary search.
Now the problem is, the nodecount is stored in a unsigned long long, whereas my sorting values are normal ints. This implies that I have to scale down the nodecounts in order not to overflow the sorting values. And I wonder how this could best be done, not leading to a division by zero error like my current approach. (lol, now I spilled the beans anyway).

It seems simpler to change your comparison function/method than to change the node counts.

Post the code that performs the ordering and I am sure that someone can fix it for you.

Ok, if I get your point I could just use an array of uint64 at the root for the sorting. Would be a solution, yes.

Don't forget Dr. Hyatt's point to put the pv node first.

So the comparison function will look something like this:

Code: Select all

typedef struct node_info {
    unsigned long long score;   /* for rootnodes, it's the node count. */
    char            Is_PV_Node; /* If this node is the predicted move of the
                                 * principal variation, then 1, else 0. */
}   node_info_t;

int             compare(void *first, void *second)
{
    struct node_info *f = first;
    struct node_info *s = second;
    unsigned long long fscore = f->score;
    unsigned long long sscore = s->score;
    if (f->Is_PV_Node) {
        fscore += 0x8000000000000000;
    }
    if (s->Is_PV_Node) {
        sscore += 0x8000000000000000;
    }
    /* Largest to smallest ordering */
    return fscore > sscore ? -1 : fscore == sscore ? 0 : -1;    
}

It might just be simpler to set the high bit of the count in your counts array for the predicted move, but the idea is the same. And it might be nice to keep the actual count for other things.

[bob]

Ok, I just found a terrible bug in my code, which is to embarrassing to even speak off. But the root off the problem is in the sorting of the moves at the root.
The plan is to take the number of nodes that are searched for each move at the root and use it as a weight to sort the move at the root, meaning more nodes (larger subtree) equals in a higher score. Moves with higher scores are searched first.
I don't know if this is the best way to sort at root, I think I stole the idea from Bob, but it currently doesn't matter that much, and it is a method that is implementable in my very rudimentary search.
Now the problem is, the nodecount is stored in a unsigned long long, whereas my sorting values are normal ints. This implies that I have to scale down the nodecounts in order not to overflow the sorting values. And I wonder how this could best be done, not leading to a division by zero error like my current approach. (lol, now I spilled the beans anyway).

It seems simpler to change your comparison function/method than to change the node counts.

Post the code that performs the ordering and I am sure that someone can fix it for you.

Ok, if I get your point I could just use an array of uint64 at the root for the sorting. Would be a solution, yes.

Don't forget Dr. Hyatt's point to put the pv node first.

What _IS_ this "Dr. Hyatt" stuff? We've only communicated here and thru email a few hundred times at least. "Bob" works better for me.

So the comparison function will look something like this:

Code: Select all

typedef struct node_info {
    unsigned long long score;   /* for rootnodes, it's the node count. */
    char            Is_PV_Node; /* If this node is the predicted move of the
                                 * principal variation, then 1, else 0. */
}   node_info_t;

int             compare(void *first, void *second)
{
    struct node_info *f = first;
    struct node_info *s = second;
    unsigned long long fscore = f->score;
    unsigned long long sscore = s->score;
    if (f->Is_PV_Node) {
        fscore += 0x8000000000000000;
    }
    if (s->Is_PV_Node) {
        sscore += 0x8000000000000000;
    }
    /* Largest to smallest ordering */
    return fscore > sscore ? -1 : fscore == sscore ? 0 : -1;    
}

It might just be simpler to set the high bit of the count in your counts array for the predicted move, but the idea is the same. And it might be nice to keep the actual count for other things.

[Guetti]

Thanks, but I already solved the problem. I had to make a new structure holding the moves and scores for root. Then I could just use the same sorting function at root as before. It is not as elegant and speedy, but I don't care, it sorts only at the root.
It first swaps the PV move to the front, then sorts the moves behind.

Code: Select all

void root_sort(Movelist* mlist, uint64* nvalue, int mvnos, move_t currpv)
{
	
	if (mvnos < 2)
	{
		// Don't sort
      printf("Root_Sort:Not enough moves\n");
		return;
	}
	if (currpv == 0)
	{
		printf("Root_Sort:Invalid Move\n");
		return;
	}
	
	int a, b;
	Movelist tmp;
	
	// Swap PV Move to front
	for (int i = 0; i < mvnos; i++)
	{
		if (mlist[i].move == currpv)
		{
			tmp = mlist[0];
			mlist[0] = mlist[i];
			mlist[i] = tmp;
		}
	}
	
	// sort of moves n>1
	uint64 ts; 
	for (a = 2; a < mvnos; ++a)
	{
		tmp = mlist[a];
		ts = nvalue[a];
		for (b = a - 1; b >= 1 && ts > nvalue[b]; b--)
		{
			mlist[b+1] = mlist[b];
			nvalue[b+1] = nvalue[b];
		}
		mlist[b+1] = tmp;
		nvalue[b+1] = ts;
	}
	
	return;
}