Not logged inRybka Chess Community Forum
- - By robertj (**) [gb] Date 2007-07-03 14:14 Edited 2007-07-03 14:17
I've seen Rybka 2.3.2a searching up to 60ish plies (in endgame positions), in some positions Rybka searches 3 to 5 plies deeper than (my version of) Crafty (both engines running on the same machine sharing CPU, etc.). Rybka 1.0 has similar behaviour, although Rybka 2.3.2a searches a few plies deeper on average.

May I ask if Rybka has some sort of aggressive forward pruning or the 60ish plies output referes to how deep the search extensions have reached (not the depth of the main brute force search).

May I also ask what Rybka defines as 'nodes searched' is it only the leaf nodes where evaluation is done or it includes all of the traversed nodes during the search (or possibly having very expensive evaluation function, could evaluation function do a shallow search)?

Thanks.
Parent - - By bedouin (**) [gb] Date 2007-07-03 15:12
Could you please include the fen of the position and any screenshots as its unclear what you are asking. It was written in another thread that the nodecount is a GUI thing and misleading.
Parent - - By robertj (**) [gb] Date 2007-07-03 15:21

> Could you please include the fen of the position and any screen shots as its unclear what you are asking.


I can't do that as I play matches and observe the games, I do not make an analysis on a set of given positions.

>It was written in another thread that the node count is a GUI thing and misleading.


I do not see how this can be... :)
Parent - - By robertj (**) [gb] Date 2007-07-04 10:23 Edited 2007-07-04 10:51
In the following position (Crafty is White, Rybka 2.3.2a is Black)...

2k1r3/p2nPp2/q4P1r/2pQ4/1pp5/2N3P1/PP3P1P/3R1K2 b - - 0 22


...Rybka 2.3.2a had outsearched Crafty for 8 plies, Crafty was searching (pondering) 12 plies while at the same time Rybka 2.3.2a was searching (thinking) 20 plies.
Parent - - By rivaldo (***) [de] Date 2007-07-05 04:29
which book did you use?

at least not the best one:

[Event "Blitz:120'"]
[Site "?"]
[Date "2007.07.05"]
[Round "?"]
[White "Neue Partie"]
[Black "Rybka 2.3.2a 32-bit"]
[Result "*"]
[ECO "D44"]
[Annotator ",fish"]
[PlyCount "44"]
[EventDate "2007.??.??"]
[TimeControl "7200"]

{256MB, Power.ctg, LEM} 1. d4 d5 2. c4 c6 3. Nf3 Nf6 4. Nc3 e6 5. Bg5 dxc4 6.
e4 b5 7. e5 h6 8. Bh4 g5 9. Nxg5 hxg5 10. Bxg5 Nbd7 11. exf6 Bb7 12. g3 c5 13.
d5 Qb6 14. Bg2 O-O-O 15. O-O b4 16. Rb1 Qa6 17. dxe6 Bxg2 18. e7 Bxf1 19. Kxf1
Bh6 $6 (19... Bxe7 {draws by force}) 20. Bxh6 Rxh6 21. Qd5 $2 Re8 22. Rd1 Qb7
$15 *
Parent - By rivaldo (***) [de] Date 2007-07-05 04:32
oh, I forgot to mention, that 19.Qd5 is better than 19.Kxf1
Parent - - By robertj (**) [gb] Date 2007-07-06 12:14
Hello,

I do not understand what the game you've posted does represent?

> which book did you use?


For Rubka I use Arena book Rybka_v2_0_0.abk and for Crafty my custom Crafty book.
Parent - - By rivaldo (***) [de] Date 2007-07-08 11:35
the game I postet was the game crafty played on your comp against rybka. I just wanted to point out, that at least craftys book is not up to date.
Parent - By robertj (**) [gb] Date 2007-07-10 12:09

> the game I posted was the game crafty played on your comp against rybka. I just wanted to point out, that at least craftys book is not up to date


Ah, I see.

Basically, I used Hyatt's and Corbit's game databases, joined them into one gigantic database (with over 2 million games in it) and generated Crafty's book with...

White(1): book create gigantic.pgn 60 12
parsing pgn move file (100k moves/dot)
parsed 137472853 moves (2519478 games).
found 0 errors during parsing.
discarded 0 moves (maxply=60).
discarded 74092896 moves (minplayed=12).
discarded 0 moves (win/lose=0.0%).
book contains 342768 unique positions.
deepest book line was 60 plies.
longest cluster of moves was 42.
time used:   25:38 elapsed.
White(1): end


...where 60 indicates how many moves from each game are to be stored in the book.bin database, and 12 says  that unless a move is played in at least 12 games, the move is discarded.

So, the book heavily depends on the quality of the games. Hyatt usually uses 60 10, so my parameters are a bit conservative compared to Hyatt's (12 as opposed to 10).

I also fine-tuned books.bin...

After creating book.bin, you need to create books.bin. This is a small version of book.bin, which is  intended to give you  more  control over the moves/openings Crafty will play. This is usually built from the file start.pgn on the ftp machine, but you can  modify this file to suit your taste
easily. To build books.bin, you use the following command:

books create start.pgn 60
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-07-03 18:45
Rybka tends to have very imbalanced search trees. Interior nodes are of course counted - the more interior a node, the more important it is.

Vas
Parent - - By robertj (**) [gb] Date 2007-07-04 08:55 Edited 2007-07-04 09:04
Hello Vasik,

Thanks for your reply.

> Rybka tends to have very imbalanced search trees.


I see.

> Interior nodes are of course counted - the more interior a node, the more important it is.


If I understand you correctly, you are saying that the closer you are to the specified full-width search depth (i.e. the less the remaining depth) the more aggressively you forward-prune. I guess your forward-pruning decision might also depend on the position in question regardless of how deep it has been reached. Please do not comment on this if it requires revealing one of Rybka's secrets.

I modified Crafty a bit: I've introduced, as described by Ernst A Heinz in his book ‘‘Scalable Search in Computer Chess’’, EL of so called AEL pruning (A of AEL pruning was already in Crafty); I've added in search what I call Rybka's evaluation extension, basically when quiescence search function is to be called instead of the search itself I first do a shallow full-width search for a couple of plies, the number of additional plies to search decreases with the full-search depth (in each iterative deepening step) and becomes zero after some limit, currently I extend for 3 plies on depth 0 linearly decreasing it for all depths up to depth 12, after which it becomes zero, this could have similar effect to making a bit more sophisticated evaluation function; I've introduced what I call a beta margin cutoff, basically I forward-prune a node if current score plus some beta margin is greater or equal to beta, the pruning is done only if absolute current score is above some threshold, currently I use 2 centipawns for beta margin and 40 centipawns for the threshold.

I am tuning Crafty's evaluation parameters using Rybka, firstly I used Rybka 1.0, now I use Rybka 2.3.2a, maybe Rybka 2.3.2a is too strong for Crafty; I use so called genetic algorithm, for which I believe you've heard of, so I won't get into details here; the current results of some best performing Crafty individuals up to date are as follows (I test the individuals in 20 game tournaments with 30 0 time control using opening books, I'm interested in tuning Crafty for slower time controls, the results of the last or a current test can be found at: http://www.jurjevic.org.uk/chess/crafty/Test.html):

-------------------------------------
individual   score vs    score vs
             Rybka 1.0   Rybka 2.3.2a
-------------------------------------
g01i04       25.0%       12.5%
g00i11       32.0%        2.5%
g02i07       25.0%        2.5%
-------------------------------------
Parent - - By bedouin (**) [gb] Date 2007-07-04 11:13
Hmm interesting. You can give Dr Hyatt a shout at Computer Chess Club as he in fact answered some questions on the yet to be released 21.6 version. I can't remember offhead the changes and tests he was talking about.
Parent - - By robertj (**) [gb] Date 2007-07-04 13:32

> You can give Dr Hyatt a shout at Computer Chess Club as he in fact answered some questions on the yet to be released 21.6 version.


I'm in contact with Professor Hyatt, but it looks like he decided to close the sources, as I understand until 2007 WCCC (which is by the way finished and Crafty did not participate). Nevertheless, I've tried some of Crafty 21.x versions, but their performance was not impressive. 

The main reason why my version of Crafty is performing so much worse against Rybka 2.3.2a than Rybka 1.0 is most likely due to the fact that Rybka 2.3.2a searches considerably deeper (mostly in complex middlegame positions) than Rybka 1.0 and no evaluation tuning can account for that (if Rybka is searching 18 plies and Crafty 12 plies, Rybka may see some tactics Crafty does not), another reason is perhaps much better evaluation function of Rybka.
Parent - - By Gaмßito (****) [cr] Date 2007-07-04 22:11
Hi,

Yes, for Crafty is almost impossible to compete against that Rybka strength in depth and against the better Rybka evaluation function. Rybka advantage over Crafty is simply huge. Those beatings are normal :-)

By the way, thanks for your games, and by the games against GM Georgiev.

Regards,
Gambito.
Parent - By robertj (**) [gb] Date 2007-07-06 10:26

> By the way, thanks for your games, and by the games against GM Georgiev.


You are welcome. There might be a rematch, depends if I manage to improve Crafty and find co-sponsors.

Maybe Vasik would be interested in organizing a GM vs Rybka live match on FICS, he has a fast machine, I understand, and the only expense would be the GM's fee (the better the GM the more he or she asks for the match).
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-07-05 12:20
Hi,

it sounds interesting, although I don't really follow it.

Are you trying to tune Crafty's evaluation function so that it plays like Rybka? Or so that it beats Rybka?

It certainly makes sense to add all sorts of selectivity to Crafty. These are definitely steps in the right direction. If you do this right, you could probably tack on 200 Elo just with some straightforward selectivity.

Another thing I might suggest is to take Toga and see if you can improve that. Toga is quite state-of-the-art and if you can improve it, I will be very impressed.

Vas
Parent - - By robertj (**) [gb] Date 2007-07-06 09:44 Edited 2007-07-06 09:47
Hello Vasik,

Thank you for your reply.

> Are you trying to tune Crafty's evaluation function so that it plays like Rybka? Or so that it beats Rybka?


I'm using a so called genetic algorithm (which is an optimization method) in an attempt to find an optimum set of evaluation parameters. In order to find out if one set of parameters is better than another I play a 20 games (30 0 time control) match against Rybka 2.3.2a (Crafty's score in that match is a measure of evaluation parameters 'goodness').

> It certainly makes sense to add all sorts of selectivity to Crafty. These are definitely steps in the right direction. If you do this right, you could probably tack on 200 Elo just with some straightforward selectivity.


I've implemented EL of AEL pruning.

Also, I've implemented what I call, a beta margin cutoff (I forward-prune if current score plus some beta margin is greater or equal to beta)...

#if defined(FUTILITY)
if (beta_margin && abs(shared->root_value - value) >= beta_threshold && abs(value) < abs(MATE - 300))
{
  if (value + beta_margin >= beta) {
    bprune = 1;
  }
}
#endif


...which might not make sense at all (does it?).

Nevertheless, I believe that Rybka has some more sophisticated method of forward-pruning (even Rybka 2.3.2a in comparison to Rybka 1.0) which cuts the search tree significantly, maybe to an extent which is equivalent to the null-move (or A of AEL) pruning.

> Another thing I might suggest is to take Toga and see if you can improve that. Toga is quite state-of-the-art and if you can improve it, I will be very impressed.


I've been long involved in modification of Crafty and know the code.

My main assumption was that Crafty is good enough and all that it lacks is a good evaluation function (I also assumed that Crafty's evaluation function has enough elements and that all it needs is tuning of the parameters). Of course, this assumption of mine could be well wrong.

Crafty can write/ read its evaluation parameters to/ from, so called, Crafty personality file, so it was not difficult to add the code for genetic algorithm, the zero generation of Crafty individuals was created by replication (say)...

personality load g00i00.cpf
personality replicate 900 500
personality save g00i01.cpf


...where...

usage:  personality replicate <change> [probability]

...and all other generations by breeding (say)...

personality load g00i01.cpf
personality load g00i02.cpf
personality breed 800 800 900 500
personality save g01i01.cpf


...where...

usage:  personality breed <inheritance_probability> <crossover_probability> [mutation_change] [mutation_probability]

Maybe Toga already has an optimum set of evaluation parameters, I do not know. I remember that author of Fruit said that there is no secret in his program, just a well balanced evaluation function.

Of course, you certainly know what is the secret of Rybka's success.

Fine tuning of Rybka's parameters (or Hydra's) may not be so easy, as there isn't an oracle (apart from previous version of the program) which is required for the assessment of the change. I recall that programmers of Hydra said that they use a combination of GM and a strong chess program (not Hydra) to test Hydra.

Tuning Crafty's parameters is much easier, you play against Rybka. :)
Attachment: g03i02.cpf (8k)
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-07-07 14:57
Aha.

I don't know if your genetic algorithm will adapt itself positively. 20-game matches are quite small. On the other hand, if 51% of your changes are positive, it might be enough.

Your pruning looks a bit weird, though. Don't you mean that value - margin > beta?

Re. Toga vs Crafty, I'm sure that Toga has a better search than Crafty.

Vas
Parent - - By robertj (**) [gb] Date 2007-07-09 11:59
Hello Vasik,

Thank you for your reply.

> I don't know if your genetic algorithm will adapt itself positively.


So far I haven't seen any significant improvement.

> 20-game matches are quite small.


I had to make a compromise between the number of games and the time control (I wanted at least 30 0 games).

> On the other hand, if 51% of your changes are positive, it might be enough.


I could freeze some or all of the changes for chosen parameters. For example, I can suppress mutation (that is what I've done for nominal piece values), inheritance or taking an average (if the parameters will be inherited from one of the parents or averaged depends on inheritance_probability, similarly if vector parameter will be crossovered or not depends on crossover_probability) or any combination of thereof. At the moment I tend to use high percentages for both inheritance_probability and crossover_probability (I found that averaging is not good).

> Your pruning looks a bit weird, though. Don't you mean that value - margin > beta?


No, I meant value + margin >= beta (or alpha + margin >= beta), i.e. if value + margin >= beta for some positive margin I decide to prune the node (if value >= beta there will be a beta cutoff), i.e. I effectively increase the number of beta cutoffs (actually I do not beta-cutoff here but rather mark the node for forward-pruning, I use the same algorithm as if EL of AEL pruning had decided to forward-prune the node, once the node is marked for forward-pruning the search won't continue searching the remaining moves in the node, but I do not store the score in the hash table). Actually, I've changed the algorithm a bit, and now it reads...

#if defined(FUTILITY)
if (depth <= depth_3) {
  if (beta_factor && abs(value) <= abs(MATE - 300))
  {
     if (value + abs(shared->root_value - value) / beta_factor >= beta) {
       bprune = 1;
     }
  }
}
#endif


...where depth_3 is AEL pruning razor depth. Nevertheless, I see Rybka 2.3.2a searching on average deeper than Crafty 20.12.rj8 (with both AEL pruning and the mentioned beta-cutof forward pruning implemented, how much deeper it depends on the position).

> Re. Toga vs Crafty, I'm sure that Toga has a better search than Crafty.


Do you know what would be the main advantage of Toga's search over Crafty's search? Thanks. Does Rybka 2.3.2a have some improvements over Toga's search? Thanks.
Parent - - By Vempele (Silver) [rs] Date 2007-07-09 17:49

>if (depth <= depth_3) {
>  if (beta_factor && abs(value) <= abs(MATE - 300))
>  {
>     if (value + abs(shared->root_value - value) / beta_factor >= beta) {
>       bprune = 1;
>     }
>  }
>}


What's shared->root_value?
What happens if value < alpha?
And, most of all, what's the whole point of this? It still doesn't seem to make much sense.

> Do you know what would be the main advantage of Toga's search over Crafty's search?


I haven't looked over Crafty, but I'd guess the main differences are Toga's extremely aggressive futility pruning at depths 1-3 (the margins are 100, 200 and 300 cp) and history pruning (yes, actual pruning on top of LMR). AFAIK Toga's always doing a research after a (non-first move) fail high in a PV node even if score >= beta is non-standard too. And Toga's Qsearch move ordering is based on MVV/LVA (there was a discussion on whether this is better than pure SEE ordering at Talkchess a while back), losing captures are of course pruned.

Anyway, Thomas says most of Toga's 100 point improvement over Fruit comes from search.

Incidentally, I got a 20 to 25 point improvement on Toga 1.2.1 just by tinkering with the history thresholds. There's also a rather serious nullmove bug and a few other things that could be improved upon (for example, checks and recaptures are extended too much, the lazy eval currently seems useless, possibly harmful). I'm confident it won't be too hard to at least surpass Rybka 1.0 beta 32-bit (this would make Toga the strongest free engine that runs on Linux :))
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-07-10 13:26
Is "value" the current evaluation score, or the result of the search? This 'margin' looks a bit weird but maybe I just don't understand it.

Re. Toga vs Crafty, there are a ton of things. I won't be able to name them all from the top of my head. Better extensions, better reductions (LMR), better pruning (at the tips), better quiescence search (for starters checks are included), etc. Plus, there are all sorts of 'search mechanics' issues - little points littered everywhere which improve the search.

Vas
Parent - - By robertj (**) [gb] Date 2007-07-12 09:52 Edited 2007-07-12 10:44

> Is "value" the current evaluation score, or the result of the search? This 'margin' looks a bit weird but maybe I just don't understand it.


The idea is to make a cutoff when val >= beta as shown in the algorithms below (code lines I've added or changed end with // rj) ...

int AlphaBeta(int depth, int alpha, int beta)

{
    int prune = 0; // rj

    if (depth == 0)

        return Evaluate();

    GenerateLegalMoves();

    while (MovesLeft() && !prune) { // rj

        MakeNextMove();

        val = -AlphaBeta(depth - 1, -beta, -alpha);

        UnmakeMove();

        if (val >= beta)

            return beta;
           
        if (val + beta_margin >= beta)  // rj
       
            prune = 1; // rj

        if (val > alpha)

            alpha = val;

    }

    return alpha;
   
}


...or in...

int AlphaBeta(int depth, int alpha, int beta)

{

    BOOL fFoundPv = FALSE;
    int prune = 0; // rj

    if (depth == 0)

        return Evaluate();

    GenerateLegalMoves();

    while (MovesLeft() && !prune) { // rj

        MakeNextMove();

        if (fFoundPv) {
            val = -AlphaBeta(depth - 1, -alpha - 1, -alpha);

            if ((val > alpha) && (val < beta)) // Check for failure.

                val = -AlphaBeta(depth - 1, -beta, -alpha);

        } else

            val = -AlphaBeta(depth - 1, -beta, -alpha);

        UnmakeMove();

        if (val >= beta)

            return beta;
           
        if (val + beta_margin >= beta)  // rj
       
            prune = 1; // rj         

        if (val > alpha) {

            alpha = val;

            fFoundPv = TRUE;

        }

    }

    return alpha;
   
}


I switched the code back to...

#if defined(FUTILITY)
    if (found_pv) {
        if (beta_margin && abs(value) > abs(DrawScore(wtm)) && abs(value) <= abs(MATE - 300))
        {
            if (value + beta_margin >= beta) {
                if (rand() % 1000 <= 499) {
                    bprune = 1;
                }
            }
        }
    }
#endif


...where beta_margin is a fixed value.

Once Dr Beal suggested that Eval + RandomEval could be better than Eval alone if RandomEval is small enough (RandomEval is simply a random variation added to the deterministic Eval).

If you put a small beta_margin, say 1 to 2 centipawns, you are effectively doing a cutoff based on evaluation uncertainty, you assume your eval may be wrong for a few centipawns and your assumption is that the error is such that you can prune the node.

You, of course, do not change value if there is a beta margin cutoff, i.e. you do not do...

#if defined(FUTILITY)
    if (found_pv) {
        if (beta_margin && abs(value) > abs(DrawScore(wtm)) && abs(value) <= abs(MATE - 300))
        {
            if (value + beta_margin >= beta) {
                if (rand() % 1000 <= 499) {
                    bprune = 1;
                    value += beta_margin; // I do not like this
                }
            }
        }
    }
#endif


...although one could experiment with that too (I personally do not like the idea).

> Re. Toga vs Crafty, there are a ton of things. I won't be able to name them all from the top of my head. Better extensions, better reductions (LMR), better pruning (at the tips), better quiescence search (for starters checks are included), etc. Plus, there are all sorts of 'search mechanics' issues - little points littered everywhere which improve the search.


I see, thanks for the info, I might have a look at the Toga sources.

The results of ongoing tests can be found at...

current test result with games...

http://www.jurjevic.org.uk/chess/crafty/Test.html

test summary up to date...

http://www.jurjevic.org.uk/chess/crafty/Results.txt
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-07-14 06:14
Aha, I see.

It's good that you're making experiments in this area, this is generally how Crafty could be improved. However, I am 100% sure that this heuristic won't work. In fact, the way you have done it, you'll fail low when value + margin >= beta.

Vas
Parent - - By robertj (**) [gb] Date 2007-07-16 12:13 Edited 2007-07-16 12:36
Hello Vasik,

Thanks for your reply.

I found at http://www.brucemo.com/compchess/programming/glossary.htm that...

Fail Low, Fail High

An alpha-beta search is guided by two bounds, which are called alpha and beta.  Alpha is always less than beta.  Each successor position is searched.  If a successor's value is greater than or equal to beta, the search will stop and return beta at that point.  This is called a "fail high".  If all of the successors are searched, and none of them returns a score in excess of alpha, the search will return alpha.  This is called a fail low.

A fail-high indicates that the search found something that was "too good".  What this means is that the opponent has some way, already found by the search, of avoiding this position, so you have to assume that they'll do this.  If they can avoid this position, there is no longer any need to search successors, since this position won't happen.

A fail-low indicates that this position was not good enough for us.  We will not reach this position, because we have some other means of reaching a position that is better.  We will not make the move that allowed the opponent to put us in this position.

You can also talk about failing high and failing low from the root position, if you use an aspiration window.


In the code below I commented when fail-low and fail-high would occur...

int AlphaBeta(int depth, int alpha, int beta)

{

    BOOL fFoundPv = FALSE;
    int prune = 0; // rj

    if (depth == 0)

        return Evaluate();

    GenerateLegalMoves();

    while (MovesLeft() && !prune) { // rj

        MakeNextMove();

        if (fFoundPv) {
            val = -AlphaBeta(depth - 1, -alpha - 1, -alpha);

            if ((val > alpha) && (val < beta)) // Check for failure.

                val = -AlphaBeta(depth - 1, -beta, -alpha);

        } else

            val = -AlphaBeta(depth - 1, -beta, -alpha);

        UnmakeMove();

        if (val >= beta)

            return beta; // fail-high
           
        if (val + beta_margin >= beta)  // rj
       
            prune = 1; // rj // sort of fail-high    

        if (val > alpha) {

            alpha = val;

            fFoundPv = TRUE;

        }

    }

    return alpha; // fail-low if fFoundPv == FALSE
   
}


> However, I am 100% sure that this heuristic won't work. In fact, the way you have done it, you'll fail low when value + margin >= beta.


If alpha < beta, theoretically it is possible that val > alpha for some move prior to the move where val + beta_margin >= beta, where beta_margin is say between 1 and 4. Nevertheless, I do not know in how many cases this would happen in practice, but my experiments show that beta_margin cutoff has some effect on search (at least in Crafty).

I found at http://www.ics.uci.edu/~eppstein/180a/990202b.html that...


...it is often helpful to call alpha-beta with an artificially narrow window centered around the previous search value. If the result is a score within that window, you've saved time and found the correct search value. But if the search fails, you must widen the window and search again:


    // aspiration search
    int alpha = previous - WINDOW;
    int beta = previous + WINDOW;
    while (true) {
        score = alphabeta(depth, alpha, beta)
        if (score <= alpha) alpha = -WIN;
        else if (score >= beta) beta = WIN;
        else break;
    }


May I ask what is a value of WINDOW in the above code in Rybka? Thanks.

By the way, I've also noticed that it appears that Rybka 2.3.2a has no built in knowledge about some basic endings...

(please see the attached image)

...however, Crafty eventually managed to lose (I do not understand how) this position (no tablebases were used for either of the engines). :(

I guess this knowledge is expected to be obtained from the tablebases.
Attachment: rybka.gif (146k)
Parent - By Vempele (Silver) [fi] Date 2007-07-16 15:20

>If alpha < beta, theoretically it is possible that val > alpha for some move prior to the move where val + beta_margin >= beta, where beta_margin is say between 1 and 4.


Since you're using PVS, the vast majority (More than 99%) of your nodes will have (alpha == beta - 1) so I'd say it happens fairly often.
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-07-18 07:19
Hi,

the line:

prune = 1; // rj // sort of fail-high    

will cause a fail-low. At that point, you have a value < beta (otherwise you would have already failed high), and by setting prune == 1 you won't search any more moves. So, you will return a value < beta.

Re. aspiration window, this hardly matters. I use some sort of a big window for Rybka - I don't remember the exact value, maybe 200. It's easy to figure it out by giving Rybka a position with a massive root fail-high.

Vas
Parent - - By robertj (**) [gb] Date 2007-07-18 09:23
Hello Vasik,

Thank you for your reply.

> the line:
>
> prune = 1; // rj // sort of fail-high    
>
> will cause a fail-low. At that point, you have a value < beta (otherwise you would have already failed high), and by setting prune == 1 you won't search any more moves. So, you will return a value < beta.


Isn't fail-low when you return value <= alpha (alpha being alpha passed to alpha-beta search function)? If so we need not to fail-low, as the program may have entered the body of the following if-statement...

        if (val > alpha) {

            alpha = val;

            fFoundPv = TRUE;

        }
        
...for the current or some previous move.
       
What I might try to do is to forward prune only if we cannot fail-low, i.e.  

int AlphaBeta(int depth, int alpha, int beta)

{

    BOOL fFoundPv = FALSE;
    int prune = 0; // rj

    if (depth == 0)

        return Evaluate();

    GenerateLegalMoves();

    while (MovesLeft() && !prune) { // rj

        MakeNextMove();

        if (fFoundPv) {
            val = -AlphaBeta(depth - 1, -alpha - 1, -alpha);

            if ((val > alpha) && (val < beta)) // Check for failure.

                val = -AlphaBeta(depth - 1, -beta, -alpha);

        } else

            val = -AlphaBeta(depth - 1, -beta, -alpha);

        UnmakeMove();

        if (val >= beta)

            return beta; // fail-high
           
        if (fFoundPv == TRUE) { // rj // prevent fail-low    
           
                if (val + beta_margin >= beta)   // rj
          
                        prune = 1; // rj // sort of fail-high    
        }

        if (val > alpha) {

            alpha = val;

            fFoundPv = TRUE;

        }

    }

    return alpha; // fail-low if fFoundPv == FALSE
   
}


I also noticed that in Crafty...


        if (fFoundPv) {
            val = -AlphaBeta(depth - 1, -alpha - 1, -alpha);

            if ((val > alpha) && (val < beta)) // Check for failure.

                val = -AlphaBeta(depth - 1, -beta, -alpha);

        } else

            val = -AlphaBeta(depth - 1, -beta, -alpha);


reads...


        if (!fFirstMove) { // Crafty's condition
            val = -AlphaBeta(depth - 1, -alpha - 1, -alpha);

            if ((val > alpha) && (val < beta)) // Check for failure.

                val = -AlphaBeta(depth - 1, -beta, -alpha);

        } else

            val = -AlphaBeta(depth - 1, -beta, -alpha);


Is that NegaScout and is it ok?

> Re. aspiration window, this hardly matters. I use some sort of a big window for Rybka - I don't remember the exact value, maybe 200. It's easy to figure it out by giving Rybka a position with a massive root fail high.


Right, thanks for the info, I'll try a bigger aspiration window in Crafty.
Parent - By Vasik Rajlich (Silver) [hu] Date 2007-07-20 09:08
Ok, this stuff is hard, very very hard. Especially if you haven't spent several thousand hours just thinking about search mechanics. But - your latest condition also won't work. It won't prevent fail lows. Besides, do you want to stop searching when you have found one move within your window? Why not look for a better one?

Vas
Parent - - By robertj (**) [gb] Date 2007-07-19 15:41
I was surprised to learn that Crafty (at least my version) passes to its evaluation function positions in which side to move is in check or even had checkmated his/ her/ its opponent. Vasik, may I ask if Rybka does the same thing? Thanks.
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-07-20 09:09
Rybka evaluates everything. Evaluating only tips is in my view crazy.

Vas
Parent - - By robertj (**) [gb] Date 2007-07-20 12:18
Hello Vasik,

Thank you for your reply.

> Rybka evaluates everything. Evaluating only tips is in my view crazy.


This looks as a very interesting and an original idea, thanks for sharing it with us.

Nevertheless, although I guess you may benefit from evaluation in non-leaf (i.e. interior) nodes for forward pruning heuristics I'm not sure how much would it cost you, i.e. how much would your search be slower because of that, also, isn't that you want to evaluate so called quiescent positions, that is why one has quiescent search.

My understanding is that the whole point of search is to find something, and that is, I thought, the path in the game tree which leads you to a leaf position which is estimated to be the best for you.

I really never understood why the same evaluation function works better if applied to positions which arise deeper in the search tree, but I would guess it is because deeper positions may have evolved more (more things has happened and it is more likely for evaluation function to see something, be it only tactics).

Anyway, I'll implement a call to Evaluate function in Search function (as it has been done in Quiescence function, i.e. do a cutoff based on "stand-pat" score) and see what happens.
Parent - - By Uri Blass (*****) [il] Date 2007-07-20 13:10
Evaluating interior nodes is an old known idea.
Rebel also evaluates every node.
Glaurung does the same and and movei does the same.
I think that Ed was the first who told people about it.
I started to do it independently of Rebel and later I learned that other programs do it.

I always considered it as stupid not to evaluate every node because this information is needed for search decisions.
You can have some rule like if evaluation is bigger than beta+margin(depth and other factors) return beta.

You say:

" really never understood why the same evaluation function works better if applied to positions which arise deeper in the search tree"

I simply did not understand what is the meaning of that sentence.
What do you mean by saying that the same evaluation function works better and better relative to what?

Uri
Parent - By Vasik Rajlich (Silver) [hu] Date 2007-07-22 07:34
You definitely don't want to stand pat in mid-search.

Anyway, if your branch factor is 2, then there will be roughly as many interior nodes as leaf nodes and you'll do only twice as many evals.

Re. evaluation function working better later in the tree - this is a basic axiom of chess analysis. When strong chess players analyze, they hardly say anything - they just move pieces around.

Vas
Parent - By robertj (**) [gb] Date 2007-07-12 10:28

> What's shared->root_value?


Should be a current root score.

> What happens if value < alpha?


If (lscore - lazy_eval_cutoff >= beta) or (lscore + lazy_eval_cutoff <= alpha, where lazy_eval_cutoff = 350 centipawns, Crafty does not evaluate Knights, Bishops, Rooks, Queens nor Kings, is this called lazy evaluation?

If material + *_margin <= alpha I do various aspects of EL of AEL forward-pruning.

> And, most of all, what's the whole point of this? It still doesn't seem to make much sense.


Probably not, nevertheless I've changed the code back to...

#if defined(FUTILITY)
    if (found_pv) {
        if (beta_margin && abs(value) > abs(DrawScore(wtm)) && abs(value) <= abs(MATE - 300))
        {
            if (value + beta_margin >= beta) {
                if (rand() % 1000 <= 499) {
                    bprune = 1;
                }
            }
        }
    }
#endif


...as it looks like...

if (value + abs(shared->root_value - value) / beta_factor >= beta)

...makes no sense.

> I haven't looked over Crafty, but I'd guess the main differences are Toga's extremely aggressive futility pruning at depths 1-3


That is I guess EL of AEL pruning (as advised by Heinz), which I've implemented in Crafty, though I did not try so aggressive thresholds (what I've tried is to rise the depths where the pruning is done, considerably).

> and history pruning (yes, actual pruning on top of LMR).


Do not know what history pruning is and if Hyatt has implemented it in Crafty.

> AFAIK Toga's always doing a research after a (non-first move) fail high in a PV node even if score >= beta is non-standard too.


I'm not following you here (on non-first move Crafty re-searches if value > alpha && value < beta), shouldn't extra research slow down the search?

>  And Toga's Qsearch move ordering is based on MVV/LVA (there was a discussion on whether this is better than pure SEE ordering at Talkchess a while back), losing captures are of course pruned.


I guess Crafty is here okay.

> Anyway, Thomas says most of Toga's 100 point improvement over Fruit comes from search.


I have looked at Fruit 2.1 sources and could not find anything extraordinary in its search. Nevertheless, this helped me to find out that Hyatt has added some pruning into Crafty's search which may not be sound (now I'm testing Crafty with this bit omitted). Is it Toga considerably different from Fruit 2.1?

> Incidentally, I got a 20 to 25 point improvement on Toga 1.2.1 just by tinkering with the history thresholds. There's also a rather serious nullmove bug and a few other things that could be improved upon (for example, checks and recaptures are extended too much, the lazy eval currently seems useless, possibly harmful). I'm confident it won't be too hard to at least surpass Rybka 1.0 beta 32-bit (this would make Toga the strongest free engine that runs on Linux)


I see.
Parent - - By Dragon Mist (****) [hr] Date 2007-07-20 10:06
"...I'm using a so called genetic algorithm (which is an optimization method) in an attempt to find an optimum set of evaluation parameters. In order to find out if one set of parameters is better than another I play a 20 games (30 0 time control) match against Rybka 2.3.2a (Crafty's score in that match is a measure of evaluation parameters..."

With how many parameters are you calculating? It seems to me that it will take decades to properly conduct n-dimensional analysis if only a handfull of parameters are variable?

Dragon Mist
Parent - By robertj (**) [gb] Date 2007-07-20 10:55
Hello,

I'm glad to see here someone from Croatia... :)

> With how many parameters are you calculating?


Quite a few, the set of evaluation parameters for the current set is herewith attached (g03i09.cpf file).

> It seems to me that it will take decades to properly conduct n-dimensional analysis if only a handful of parameters are variable?


Possibly, it depends on how fast the algorithm converges, of curse, here is all done manually, I pick up which individuals to breed, it also depends on breeding implementation and its control parameters, I can also make replicants from one individual by mutation... I at least decided to give it a try... current test results with games...

http://www.jurjevic.org.uk/chess/crafty/Test.html

... and test summary up to date...

http://www.jurjevic.org.uk/chess/crafty/Results.txt

My main assumption was that Crafty is good enough and all that it lacks is a good evaluation function (I also assumed that Crafty's evaluation function has enough elements and that all it needs is tuning of the parameters, I've added a couple of elements to Crafty's evaluation function). Of course, this assumption of mine could be well wrong.

Crafty can write/ read its evaluation parameters in/ from, so called, Crafty personality file, so it was not difficult to add the code for genetic algorithm, the zero generation of Crafty individuals was created by replication (say)...

personality load g00i00.cpf
personality replicate 900 500
personality save g00i01.cpf

...where...

usage:  personality replicate <mutation_change> [mutation_probability]

...all other generations by breeding (say)...

personality load g00i01.cpf
personality load g00i02.cpf
personality breed 800 800 900 500
personality save g01i01.cpf

...where...

usage:  personality breed <inheritance_probability> <crossover_probability> [mutation_change] [mutation_probability]

I could freeze some or all of the changes for chosen parameters. For example, I can suppress mutation (that is what I've done for nominal piece values), inheritance or taking an average (if the parameters will be inherited from one of the parents or averaged depends on inheritance_probability, similarly if vector parameter will be crossovered or not depends on crossover_probability) or any combination of thereof. At the moment I tend to use high percentages for both inheritance_probability and crossover_probability (I found that averaging is not good).
Attachment: g03i09.cpf (8k)

Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill