| |
Main
Date: 06 Oct 2006 13:22:29
From: OrhanOzturk
Subject: Scoring goodness of move ordering
|
Is it possible to assign a score, for example out of 100, to show how
good was the program's move ordering after a search ?
I am asking this, because i am testing different move ordering methods
alone or combined with other heuristics. I ended with that there should
be some kind of scoring to measure goodness of the move ordering to
understand the affect of methods.
Currently i am using (searched node count) / (minimax tree node count)
ratio. This ratio gives me the
search tree's size compared to minimax tree.But as you can estimate it
is too time consuming and i cant use it while my program plays a real
game.I just can use it when my program is in benchk mode. So im
looking for a simple way of measuring it.
I dont want to use node counts directly, bec when the quescient search
goes too deep it exploits the node counts.Then i cant compare the
nodes. Depending on the heuristics i test, the Quescient search
sometimes triggered many times, while just a few times in other
heuristics. So i cant use it.
To avoid this i just compared the nodes searched in Search() function,
but this resulted in different PV's and scores.
Which methods are the experienced programmers ( B.Hyatt, B.Moreland )
using to achieve this ?
Thanks in advance.
|
|
| |
Date: 16 Oct 2006 02:00:34
From: OrhanOzturk
Subject: Re: Scoring goodness of move ordering
|
I have objections to this code ...But it is another story...
Simon Krahnke yazdi:
> * OrhanOzturk <[email protected]> (2006-10-13) schrieb:
>
> >> Another to do it, just maintain two counters, one for each parent, the
> >> other for each child.
> >>
> >> b = children/parents
> >
> > How ? Honestly it seems not easy ...
>
> children = parents = 0
>
> search
> do stuff
> generate moves
> parents++
> for each move
> children++
> recurse, eventually cut
>
> float ebf = ((float) children) / parents;
>
> mfg, simon .... l
|
| |
Date: 13 Oct 2006 03:13:48
From: OrhanOzturk
Subject: Re: Scoring goodness of move ordering
|
> Another to do it, just maintain two counters, one for each parent, the
> other for each child.
>
> b = children/parents
How ? Honestly it seems not easy ...
Simon Krahnke yazdi:
> * OrhanOzturk <[email protected]> (16:15) schrieb:
>
> > n = b^d simply gives b = n ^ ( 1 / d) ....No more math needed : )
>
> That is just the same.
>
> > I think you missed something,
>
> Read my post?
>
> > This includes and measures everything in
> > the game.. Every heuristic that is applied any methods used. Selective
> > searching,forward pruning, null move, extensions,hashing etc...
>
> Yeah, switch it all off.
>
> Another to do it, just maintain two counters, one for each parent, the
> other for each child.
>
> b = children/parents
>
> That one doesn't care about the depth of the cuts. And shares none of
> the of the above "problems".
>
> mfg, simon .... l
|
| |
Date: 12 Oct 2006 07:15:15
From: OrhanOzturk
Subject: Re: Scoring goodness of move ordering
|
n = b^d simply gives b = n ^ ( 1 / d) ....No more math needed : )
I think you missed something, This includes and measures everything in
the game.. Every heuristic that is applied any methods used. Selective
searching,forward pruning, null move, extensions,hashing etc...
I just want to measure goodness of move ordering. I think it is better
a formula (as suggested in this thread) : #of beta cuts on first move
/ total beta cuts ...
Thanks anyway for your time.
Regards
Simon Krahnke yazdi:
> * OrhanOzturk <[email protected]> (10:05) schrieb:
>
> > Do you have a reference / link that proves / explains the formula you
> > have given ?
>
> Well, theory says that the number of computed nodes n is b^d. (^ to the
> power of).
>
> thus log(n) = logb(b^d) = d * log(b)
> and log(n) / d = log(b),
> exp(log(b) / d) = exp(log(b)) = b
>
> That would be the exact average value for a minimax tree. Every
> optimization in the search like alpha beta cuts, pruning yields in a
> smaller value. Extensions, re-searches, quiescense search may yield in a
> bigger value.
>
> And an erly cut near the root is better than a late cut near a leaf.
>
> mfg, simon .... l
|
| |
Date: 12 Oct 2006 01:05:57
From: OrhanOzturk
Subject: Re: Scoring goodness of move ordering
|
Do you have a reference / link that proves / explains the formula you
have given ?
Simon Krahnke yazdi:
> * Harald Luessen <[email protected]> (14:12) schrieb:
>
> > On 6 Oct 2006 "OrhanOzturk" wrote:
> >
> >>Is it possible to assign a score, for example out of 100, to show how
> >>good was the program's move ordering after a search ?
> >
> > Some people use a first move hit/cut rate, that is the percentage
> > of the first tried move in each position being the best or leading
> > to a beta cut. IIRC percentages over 80% are good.
>
> But the first move is from the hash table, that is not exactly move
> ordering.
>
> mfg, simon .... l
|
| |
Date: 08 Oct 2006 14:12:47
From: Harald Luessen
Subject: Re: Scoring goodness of move ordering
|
On 6 Oct 2006 "OrhanOzturk" wrote:
>Is it possible to assign a score, for example out of 100, to show how
>good was the program's move ordering after a search ?
Some people use a first move hit/cut rate, that is the percentage
of the first tried move in each position being the best or leading
to a beta cut. IIRC percentages over 80% are good.
Harald
|
| | |
Date: 15 Oct 2006 16:56:57
From: Simon Krahnke
Subject: Re: Scoring goodness of move ordering
|
* OrhanOzturk <[email protected] > (2006-10-13) schrieb:
>> Another to do it, just maintain two counters, one for each parent, the
>> other for each child.
>>
>> b = children/parents
>
> How ? Honestly it seems not easy ...
children = parents = 0
search
do stuff
generate moves
parents++
for each move
children++
recurse, eventually cut
float ebf = ((float) children) / parents;
mfg, simon .... l
|
| | |
Date: 12 Oct 2006 19:21:14
From: Simon Krahnke
Subject: Re: Scoring goodness of move ordering
|
* OrhanOzturk <[email protected] > (16:15) schrieb:
> n = b^d simply gives b = n ^ ( 1 / d) ....No more math needed : )
That is just the same.
> I think you missed something,
Read my post?
> This includes and measures everything in
> the game.. Every heuristic that is applied any methods used. Selective
> searching,forward pruning, null move, extensions,hashing etc...
Yeah, switch it all off.
Another to do it, just maintain two counters, one for each parent, the
other for each child.
b = children/parents
That one doesn't care about the depth of the cuts. And shares none of
the of the above "problems".
mfg, simon .... l
|
| | |
Date: 12 Oct 2006 11:09:21
From: Simon Krahnke
Subject: Re: Scoring goodness of move ordering
|
* OrhanOzturk <[email protected] > (10:05) schrieb:
> Do you have a reference / link that proves / explains the formula you
> have given ?
Well, theory says that the number of computed nodes n is b^d. (^ to the
power of).
thus log(n) = logb(b^d) = d * log(b)
and log(n) / d = log(b),
exp(log(b) / d) = exp(log(b)) = b
That would be the exact average value for a minimax tree. Every
optimization in the search like alpha beta cuts, pruning yields in a
smaller value. Extensions, re-searches, quiescense search may yield in a
bigger value.
And an erly cut near the root is better than a late cut near a leaf.
mfg, simon .... l
|
| | |
Date: 08 Oct 2006 14:54:22
From: Simon Krahnke
Subject: Re: Scoring goodness of move ordering
|
* Harald Luessen <[email protected] > (14:12) schrieb:
> On 6 Oct 2006 "OrhanOzturk" wrote:
>
>>Is it possible to assign a score, for example out of 100, to show how
>>good was the program's move ordering after a search ?
>
> Some people use a first move hit/cut rate, that is the percentage
> of the first tried move in each position being the best or leading
> to a beta cut. IIRC percentages over 80% are good.
But the first move is from the hash table, that is not exactly move
ordering.
mfg, simon .... l
|
| |
Date: 07 Oct 2006 04:07:27
From: OrhanOzturk
Subject: Re: Scoring goodness of move ordering
|
Do you have a sample code ?
Simon Krahnke yazdi:
> * OrhanOzturk <[email protected]> (12:25) schrieb:
>
> > You cant calculate average branching factor if you are using alpha -
> > beta pruning.
>
> Of cource you can.
>
> mfg, simon .... l
|
| |
Date: 07 Oct 2006 03:25:14
From: OrhanOzturk
Subject: Re: Scoring goodness of move ordering
|
You cant calculate average branching factor if you are using alpha -
beta pruning.
Simon Krahnke yazdi:
> * OrhanOzturk <[email protected]> (10:14) schrieb:
>
> > Simon Krahnke yazdi:
> >> * OrhanOzturk <[email protected]> (22:22) schrieb:
> >>
> >> > Is it possible to assign a score, for example out of 100, to show how
> >> > good was the program's move ordering after a search ?
> >>
> >> Why not just use the effective branching factor?
> >>
> >> mfg, simon .... l
> >
> > What do you mean with that ? Please make it detailed ...
>
> The effective branching factor is the averge number of visited child
> nodes for each node.
>
> http://en.wikipedia.org/wiki/Branching_factor
>
> mfg, simon .... l
|
| |
Date: 07 Oct 2006 01:14:33
From: OrhanOzturk
Subject: Re: Scoring goodness of move ordering
|
Simon Krahnke yazdi:
> * OrhanOzturk <[email protected]> (22:22) schrieb:
>
> > Is it possible to assign a score, for example out of 100, to show how
> > good was the program's move ordering after a search ?
>
> Why not just use the effective branching factor?
>
> mfg, simon .... l
What do you mean with that ? Please make it detailed ...
|
| |
Date: 07 Oct 2006 08:08:21
From: Simon Krahnke
Subject: Re: Scoring goodness of move ordering
|
* OrhanOzturk <[email protected] > (22:22) schrieb:
> Is it possible to assign a score, for example out of 100, to show how
> good was the program's move ordering after a search ?
Why not just use the effective branching factor?
mfg, simon .... l
|
| | |
Date: 07 Oct 2006 16:20:26
From: Simon Krahnke
Subject: Re: Scoring goodness of move ordering
|
* OrhanOzturk <[email protected] > (13:07) schrieb:
> Do you have a sample code ?
ebf = exp(log(nodes)/depth)
where depth is the depth searched so far and nodes is the node count.
mfg, simon .... l
|
| | |
Date: 07 Oct 2006 12:35:31
From: Simon Krahnke
Subject: Re: Scoring goodness of move ordering
|
* OrhanOzturk <[email protected] > (12:25) schrieb:
> You cant calculate average branching factor if you are using alpha -
> beta pruning.
Of cource you can.
mfg, simon .... l
|
| | |
Date: 07 Oct 2006 11:59:42
From: Simon Krahnke
Subject: Re: Scoring goodness of move ordering
|
* OrhanOzturk <[email protected] > (10:14) schrieb:
> Simon Krahnke yazdi:
>> * OrhanOzturk <[email protected]> (22:22) schrieb:
>>
>> > Is it possible to assign a score, for example out of 100, to show how
>> > good was the program's move ordering after a search ?
>>
>> Why not just use the effective branching factor?
>>
>> mfg, simon .... l
>
> What do you mean with that ? Please make it detailed ...
The effective branching factor is the averge number of visited child
nodes for each node.
http://en.wikipedia.org/wiki/Branching_factor
mfg, simon .... l
|
|
