Author: Vincent Diepeveen
Date: 08:37:30 03/01/04
Go up one level in this thread
On March 01, 2004 at 10:23:22, Christophe Theron wrote:
>On February 29, 2004 at 01:51:35, Joshua Haglund wrote:
>
>>Hi,
>>
>>I have an idea I am not sure will work. Tell me what you think.
>>
>>example:
>>
>>search to ply 10 with static evals.
>> any search method, alpha/beta, NegaScout, MiniMax, Quiesce, etc.
>>
>>
>>Then start searching for ply 10 with all your other evaluations.
>>
>>What i'm saying is:
>>
>>Search deeper with right away with "dummy" moves so are depth is good. Then,
>>start searching for better moves.
>>
>>void SearchForBetter()
>>{
>>Do_more_with_evaluation();
>>compare_alpha_beta();
>>}
>>
>>DummySearch(alpha, beta, depth)
>>{
>>...
>>if(depth >= 10)
>>SearchForBetter();
>>...
>>return alpha;
>>}
>>
>>Another Idea of this or maybe both can be tried at the same time is:
>>
>> for (i = first_move[ply]; i < first_move[ply + 1]; ++i) {
>> sort_moves(i);
>> if (!makemove(generate_data[i]m.b))
>> continue;
>> ++f; // number of moves to look at
>> // the less to look at the faster. 3 moves.
>>(plies should come fast before 5 to even worry about)
>> if (ply == 5 && f == 3) {
>> if (ply == 6)
>> f = 3;
>> if (ply == 7)
>> f = 3;
>> if (ply == 8)
>> f = 3;
>> if (ply == 9)
>> f = 3;
>> if (ply == 10)
>> f = 255; // look at all moves from ply 10 and onward.
>> ++depth;
>> takeback();
>> break;
>> }
>> x = -search(-beta, -alpha, depth - 1);
>>
>>
>>and if we are very optimistic:
>>
>>
>> for (i = first_move[ply]; i < first_move[ply + 1]; ++i) {
>> sort_moves(i);
>> if (!makemove(generate_data[i]m.b))
>> continue;
>> ++f; // number of moves to look at
>> // the less to look at the faster. 3 moves.
>>(plies should come fast before 5 to even worry about)
>> if (ply == 5 && f == 3) {
>> if (ply == 6)
>> f = 3;
>> if (ply == 7)
>> f = 3;
>> if (ply == 8)
>> f = 3;
>> if (ply == 9)
>> f = 3;
>> if (ply == 10)
>> f = 3;
>> if (ply == 11)
>> f = 3;
>> if (ply == 12)
>> f = 3;
>> if (ply == 13)
>> f = 3;
>> if (ply == 14)
>> f = 3;
>> if (ply == 15)
>> f = 255; // look at all moves from ply 15 and onward.
>> ++depth;
>> takeback();
>> break;
>> }
>> x = -search(-beta, -alpha, depth - 1);
>>
>>I hope you see my idea.
>>
>>Joshua Haglund
>
>
>
>I don't think your idea will work as is, and as a matter of facts I'm sure it
>will not because I have tried something similar in the past.
>
>However this family of pruning algorithms looks a lot like what a human player
>does, and I think it is a good thing to continue your researchs in this area.
>
>An idea I have played with, and which worked somehow in the 16 bits version of
>Chess Tiger is to:
16 bits is dead slow, this must be like 10 years ago?
All modern processors there 16 bits code is the slowest possible code.
from Pentiumpro and onwards, 8 bits unsigned is fastest followed by 32 bits
unsigned. Idem opteron.
In order to program neatly i of course use 'int' everywhere, to avoid type
mixing problems
if( a == b ) // a unsigned, b signed
Result is undefined. to avoid this i use 'int' in diep everywhere. it is a lot
slower but it is avoiding forever the above type mixing problem.
>* sort all the move at a given ply by plausibility (you can spend a lot of
>computational resources on this and use a good SEE for example)
>* decide to take the N best ones and even to cut this sublist when the score
>falls behind a given margin below the score of the best one (maybe a pawn, maybe
>2)
>* add to the list all the moves that threaten something, even if they are stupid
>* add to the list all the captures (maybe)
You just mention a tactical move ordering here. Right, that's what i more or
less did in a huge experiment. I had worked for 6 months at it. It searched
around 2-3 ply deeper than normal diep version.
Jan Louwman played in total 1000 games. Level 40 in 2 (at slower computers like
old P3's even slower levels, like 6 hours for 40 moves). About 500 games with
normal diep version, about 500 games with diep version using this type of
forward pruning. Evaluation identical.
Normal diep version scored 20-25% better, despite getting outsearched 2-3 ply by
this type of search.
>And at every ply you search only this sublist, unless you get a fail low (very
>bad score), in which case you continue to search the remaining moves.
>
>I would call this "true forward pruning", and I think it is possible to create a
>very slow and very strong program with this idea. It is also possible to add
>chess knowledge in the part that select the moves to add to the N best ones,
and
I call that tactical forward pruning.
>I like the "humanity" of this approach. For example you could tell your program
>to start looking at every aggressive move, even if it looks stupid, when a King
>attack is possible.
I call that positional forward pruning. I do not lay claims that this doesn't
work the last few plies; the amount of code needed to write here will be quite
though though as it is basically an evaluation function predicting what moves
are interesting to try. Perhaps 200KB knowledge needed here?
>The 16 bits version of Chess Tiger (the last one in the family was Chess Tiger
>10) was based on something similar, and was working rather well.
>
>Chess Tiger 10 was doing forward pruning even at the root of a 20 plies search.
>That means that it *NEVER* searched some moves.
>
>Anybody feeling macho enough to try it again? :)
Positional forward pruning sure. tactical forward pruning, never again :)
And sure i start pruning in root too in such a case, just reduce the depth 1 or
2 ply then though. Not throw it away :)
Throwing away completely moves only last 2 ply.
The real difficulty is how many moves to try at least and in how far to try
tactical moves. Many tactical moves should not be searched IMHO. Giving a queen
away by capturing at a7 or putting it at a6 is a nonsense moves (but of course
could lead to mate).
> Christophe
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.