|
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
|
|