Author: Christophe Theron
Date: 07:23:22 03/01/04
Go up one level in this thread
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:
* 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)
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 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.
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? :)
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.