Easy Moves

[Edmund]

my reasoning was that a low node count indicates a high score difference, as many beta-cutoffs and null-move prunings succeed.

So why don't you count fail-highs instead?
Yet, I think that some sort of additional search is needed to detect easy moves...

Cheers, mr

initially I took total node count because these were the variable at hand without much additional work. But now thanks to your comment I am wondering whether such absolute messures are good at all. For example in an opening position the algorithm might even favour a trade of pieces after which the mobility increases drastically eg opening up a file or diagonal, as the resulting positions will have many more nodes to search. In the contrary in the endgame a queen trade would never get the chance to be reduced as the resulting positions will have a lot less nodes. Maybe something relative like % of first move cutoffs or cutoffs/total nodes should be used instead.

I will run another test tomorrow as I am too busy today.

regards,
Edmund

[Edmund]

Have you tried comparing the two methods to figure out where you have significant differences ? You can log the node counts and easy move info for a couple of games.

Code: Select all

So I then tried a scaled reduction of searchtime:
50 - 100: 2/3
100 - 200: 1/2
200+: 1/4 

If root move qsearch scoring signals an easy move, do you start searching by allocating 1/4 of time you would normally do ? And then at the end of that time check if the ratio is > 200 ,or is between 100 and 200 etc... to decide if to use more time ?
Easy move should also be _really_ easy. The next group of moves closer to them are singular moves. Then comes the normal moves. Does the ratio you mention (0 - 30) include the singular moves as well. If that is not the case may be you should increase the time factors to exclude the singular moves (say delta 50) from the easy moves ?
cheers
Daniel

The way I implemented it was to base the decision of whether the next ply should be searched on the remaining movetime corrected by the reduction factor which is determined by the previous plies highest nodecount / second highest nodecount. This has the effect that once the ply has started and it takes considerably longer (maybe because another move fails high) it doesn't consider the reduced time and stop.

The 0-30 ratio I observed was from average middlegame positions with more than one reasonable move; > 500 was in positions where only one move would avoid the loss of a queen (ie. so no checks etc are possible that might intervene)

Concerning your definitions "really easy", easy, singular move. I don't think it is easy to draw a clear line. Ideally one should stop a search once the marginal gain of continuing the search is equal to the marginal loss of reducing the search time for all the other moves that have to be played with the remaining time. So the more likely it seems that a certain move will end best the sooner the search should be stopped.
If now the opponent remaines a Queen up, if the side to move doesn't recapture the probability the recapture being better than the rest should soon be high enough to have the time better spent searching more uncertain outcomes. Same for recapturing/defending Rooks, Bishops and Knights, defending passed pawns, etc. all might be singular moves, but the time to determine that they are better than the rest may vary.

[Daniel Shawul]

The way I implemented it was to base the decision of whether the next ply should be searched on the remaining movetime corrected by the reduction factor which is determined by the previous plies highest nodecount / second highest nodecount. This has the effect that once the ply has started and it takes considerably longer (maybe because another move fails high) it doesn't consider the reduced time and stop.

The 0-30 ratio I observed was from average middlegame positions with more than one reasonable move; > 500 was in positions where only one move would avoid the loss of a queen (ie. so no checks etc are possible that might intervene)

I understand your method now. But maybe you shouldn't do checks for easy moves starting from ply 1. Decisions at shallow iterations (say search_depth <= 7) could be very risky. I always spend some time,t /4 or smaller (depth criteria could also be used), on any easy move, including the seemingly easiest case of queen recaptures.. You could be sacing a queen to mate in 8 !

Concerning your definitions "really easy", easy, singular move. I don't think it is easy to draw a clear line. Ideally one should stop a search once the marginal gain of continuing the search is equal to the marginal loss of reducing the search time for all the other moves that have to be played with the remaining time. So the more likely it seems that a certain move will end best the sooner the search should be stopped.

I agree that if the move looks certain to be played , then time could be saved. But IMO trying to save time from a move with delta <= 100 score above the second best (in your case the corresponding nodes ration), has more risk than its advantage in saving time.. YMMV

[Daniel Shawul]

While I was trying to see what things look like in scorpio, I found something astounding My first to second ratio is between 100 -200 !
Well not so shocking once I figure the details I introduced reduction on root moves (reduce everything except the first move) in the last version, without researchs or whatsoever. This resulted in that behaviour. Since first move is being searched always one ply deeper than the rest the node count ratios are well astronomical.. This may be a concern for your method if you have pv favouring techniques, like extend pvs,don't reduce pv lines etc..

I also found a bug (not really a mistake but something i could use to improve). When a root move fails low and a better move is found, the new best move is searched first and the now old best move is searched _LAST_ in my case (But it should have been searched second). The reason was that on the next iteration hash table gives a quick cutoff because it was already searched one ply deeper in the previous iteration (only 1 node required). Sample run to make my rumblings clearer..

Code: Select all

[2] 12 12 118 1489739  Ng1-f3 Ng8-f6 d2-d4 e7-e6 e2-e4 Nf6xe4 Bf1-d3 d7-d5 Qd1-e2 Nb8-c6 Bd3xe4 d5xe4 Qe2xe4
[2] 12 14 131 1695462  Nb1-c3 Nb8-c6 d2-d4 d7-d5 Qd1-d3 Ng8-f6 Bc1-f4 Bc8-g4 Ng1-f3 e7-e6
[2] 12 14 142 1865701  Nb1-c3 Nb8-c6 d2-d4 d7-d5 Qd1-d3 Ng8-f6 Bc1-f4 Bc8-g4 Ng1-f3 e7-e6
0.Ng1-f3 : 231381
1.Nb1-c3 : 205723
2.e2-e4 : 26354
3.e2-e3 : 23682
4.b2-b3 : 14359
5.a2-a4 : 8271
6.g2-g3 : 7563
7.h2-h4 : 7164
8.d2-d4 : 16693
9.a2-a3 : 5223
10.d2-d3 : 5391
11.Nb1-a3 : 6708
12.Ng1-h3 : 5007
13.c2-c4 : 10820
14.h2-h3 : 7578
15.f2-f4 : 13622
16.b2-b4 : 3779
17.g2-g4 : 3644
18.f2-f3 : 2940
19.c2-c3 : 1441
[0] 13 19 223 3224298  Nb1-c3 Nb8-c6 d2-d4 e7-e6 e2-e4 Bf8-b4 Ng1-f3 Ng8-f6 Bf1-d3 d7-d5 e4-e5 Bb4xc3 b2xc3 Nf6-e4 Bd3xe4 d5xe4
[0] 13 19 243 3564162  Nb1-c3 Nb8-c6 d2-d4 e7-e6 e2-e4 Bf8-b4 Ng1-f3 Ng8-f6 Bf1-d3 d7-d5 e4-e5 Bb4xc3 b2xc3 Nf6-e4 Bd3xe4 d5xe4
0.Nb1-c3 : 1358597
1.Ng1-f3 : 1
2.e2-e4 : 34399
3.e2-e3 : 31053
4.d2-d4 : 81700
5.b2-b3 : 16313
6.f2-f4 : 7265
7.c2-c4 : 21520
8.a2-a4 : 26278
9.h2-h3 : 10226
10.g2-g3 : 23462
11.h2-h4 : 14431
12.Nb1-a3 : 11171
13.d2-d3 : 11853
14.a2-a3 : 13640
15.Ng1-h3 : 12311
16.b2-b4 : 7466
17.g2-g4 : 6245
18.f2-f3 : 7286
19.c2-c3 : 3244

Ngl-f3 was best at depth 12 and new best move Nb1-c3 comes up. See now Ng1-f3 has only one nodecout which makes it to be searched last once sorting is done. I am hoping fixing this should give me a couple of elos . thanks

[Richard Allbert]

One idea that just popped into my head....

Say you do a search in a normal game, and the PV is for example:

1. Ne4 Nxe4 2. Bxe4 Rf6 3. etc etc

where the Bxe4 is an obvious recapture for you. If you stored your PV for the search that found Ne4, your opponent made Nxe4, then I imagine it would be safe to say that if after a very quick search, and Bxe4 is easily the best move compared with the others, it's safe to play, seeing as it was in your PV last time.

I hope that makes sense! I haven't tried it myself, but I'll try it out this week



Richard

[jdart]

Well, I might put the easy move back in someday. But if the following move is forced or nearly so you are likely going to have a ponder hit on it, so your search time is reduced anyway.

[hgm]

You mean the _opponent_ is going to have a ponder-hit if you think long on a forced move...

[hgm]

One idea that just popped into my head....

Say you do a search in a normal game, and the PV is for example:

1. Ne4 Nxe4 2. Bxe4 Rf6 3. etc etc

where the Bxe4 is an obvious recapture for you. If you stored your PV for the search that found Ne4, your opponent made Nxe4, then I imagine it would be safe to say that if after a very quick search, and Bxe4 is easily the best move compared with the others, it's safe to play, seeing as it was in your PV last time.

I hope that makes sense! I haven't tried it myself, but I'll try it out this week



Richard

If it was in your PV, it has been search to a depth 2 less than you would normally search, at this complexity. That corresponds to a reduction in search time of about 10. So if you were planning to reduce thinking time by that factor for an easy-move you could play it without search. (As long as you don't do two esy-moves in a row!)

The catch is of course: how would you know it is an easy-move without search?

[Richard Allbert]

Agreed, but I don't mean in all cases.

You could define that if the previous search this a specified depth (say 11), you know the candidate easy move was searched to depth 9.

If this move is a. A recapture, with no other recapture available and b. is still > 200 cp better than the other moves, then it would be safe to say it and ok easy move.

Or not?

I was thinking of lots of obvious easy recaptures in the opening and early middlegame when pieces are exchanged.


See you in two weeks!


Richard