Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Exact value of second best move in AlphaBeta with aspiration Window

Author: Robert Hyatt

Date: 17:57:44 08/04/02

Go up one level in this thread


On August 03, 2002 at 20:55:40, Mike Byrne wrote:

>On August 02, 2002 at 17:08:03, Robert Hyatt wrote:
>
>>On August 01, 2002 at 19:40:17, Martin Bauer wrote:
>>
>>>On August 01, 2002 at 08:12:13, Ulrich Tuerke wrote:
>>>
>>>>In order to get exact values, you in principle have to switch off alpa-beta at
>>>>ply 1. But that's too expensive in terms of search tree sizes.
>>>
>>>Ok, thank you and all other people, who replyed to my question. I see it is not
>>>so easy, I have to spend some extra work and be careful, that it does not waste
>>>too much time.
>>>
>>>I dont want to trust the values at depth 1, because that is not a good look
>>>ahead.
>>>
>>>>I do a pure minmax search at iteration #1. So, I get exact values at this level.
>>>>These values - combined with other criteria - are some measure whether the best
>>>>move is "an easy one".
>>>
>>>What about this Situation: I can recapture the queen in 1, but there also is a 7
>>>move combination that wins two rooks. So a 1 ply search would say "easy move"
>>>because it only sees the recapture of the queen. But in truth there is a
>>>slightly better move that wins 2 rooks, what gives a little bit better value in
>>>my program and I think in most others, too.
>>>
>>>if I half the search time in a 1min bullet game, I may be blind for the better 7
>>>move combination, because of the reduced time. That is the reason, why I want to
>>>ask for the difference of the two best moves with values resulting from depth 7.
>>>Can ply 1 + some extra things replace ply 7. Or do I worry about things that
>>>doesn't matter in practice? On what depends searching more or less in top
>>>Engines?
>>>
>>>Bye
>>>
>>>Martin
>>\
>>Here is what I do in Crafty:
>>
>>1.  I order all the root moves.  To do this, I make each root move and do a
>>captures-only q-search after each move to get a rough idea of the material
>>situation on the board.
>>
>>2.  If one move is better than all the rest (by at least 2.0 pawns) then I
>>set the "easy move" flag.
>>
>>3.  I then start the normal search.
>>
>>4.  If, during the search, this move "fails low" at any point, "easy move" is
>>cleared.  If, during the search, another move becomes best, "easy move" is
>>also cleared.
>>
>>5.  When I have used 1/3 of the target time, and easy move is still set, I
>>stop the search early.
>>
>>I do have some additional restrictions...  IE this must be a recapture, ie
>>To(move) must be identical to To(opponent's last move) which would make it
>>a recapture.  You don't want to say easy move too quickly.  There is a
>>famous position from Cray Blitz vs Belle in 1981, where white could play
>>Qxb6 (the knight appeared to be hanging, but taking it led to great
>>difficulty).  Cray Blitz thought it was "easy" and didn't search long enough
>>to see it was poisoned...
>
>noise=1
>Crafty v17.15 SE (2 cpus)
>
>White(1): noise 1
>noise level set to 1.
>White(1): [D] 5r1k/6p1/1n2Q2p/4p3/8/7P/PP4PK/R1B1q3 w - - 28 bm Bxh6
>
>White(1):
>White(1): go
>              clearing hash tables
>              time surplus   0.00  time limit 10:00 (10:00)
>         nss  depth   time  score   variation (1)
>starting thread 1
>                1     0.00   5.21   1. Qxb6 Rf2
>                1->   0.03   5.21   1. Qxb6 Rf2
>                2     0.03     --   1. Qxb6
>                2     0.03     ++   1. Qxb6!!
>                2     0.03   5.67   1. Qxb6 Rc8 2. Qe3
>                2->   0.03   5.67   1. Qxb6 Rc8 2. Qe3
>                3     0.03     --   1. Qxb6
>                3     0.03   5.59   1. Qxb6 Qf2 2. Be3 Qf5
>                3->   0.03   5.59   1. Qxb6 Qf2 2. Be3 Qf5
>                4     0.03     ++   1. Qxb6!!
>                4     0.05   6.00   1. Qxb6 Qf2 2. Qe3 Qxe3 3. Bxe3
>                4->   0.05   6.00   1. Qxb6 Qf2 2. Qe3 Qxe3 3. Bxe3
>                5     0.06     --   1. Qxb6
>                5     0.06   5.72   1. Qxb6 Rc8 2. Qe3 Qxe3 3. Bxe3 Rc2
>                                    <HT>
>                5->   0.08   5.72   1. Qxb6 Rc8 2. Qe3 Qxe3 3. Bxe3 Rc2
>                                    <HT>
>                6     0.09     ++   1. Qxb6!!
>                6->   0.11   6.11   1. Qxb6 Rc8 2. Qe3 Qxe3 3. Bxe3 Rc2
>                                    4. Bc1 <HT>
>                7     0.11     --   1. Qxb6
>                7     0.30  -1.30   1. Qxb6 Rf1 2. Qd8+ Kh7 3. Qd3+ e4
>                                    4. Qxf1 Qxf1 5. b3 e3 6. Bb2 e2 7.
>                                    Bc3
>                7     0.33     ++   1. Bxh6!!
>                7     0.41  -0.60   1. Bxh6 Qxa1 2. Qg6 Rg8 3. Be3 Rc8
>                                    4. Bxb6 Qxb2
>         (4)    7->   0.80  -0.60   1. Bxh6 Qxa1 2. Qg6 Rg8 3. Be3 Rc8
>                                    4. Bxb6 Qxb2
>         (3)    8     0.87  -0.49   1. Bxh6 Qxa1 2. Qg6 Rg8 3. Qxb6 Qxa2
>                                    4. b4 Rc8 5. Bg5
>         (4)    8->   1.36  -0.49   1. Bxh6 Qxa1 2. Qg6 Rg8 3. Qxb6 Qxa2
>                                    4. b4 Rc8 5. Bg5
>                9     1.48     ++   1. Bxh6!!
>         (3)    9     1.64   0.00   1. Bxh6 Qxa1 2. Qg6 gxh6 3. Qxh6+ Kg8
>                                    4. Qg6+ Kh8 5. Qh6+
>         (4)    9->   2.58   0.00   1. Bxh6 Qxa1 2. Qg6 gxh6 3. Qxh6+ Kg8
>                                    4. Qg6+ Kh8 5. Qh6+
>         (3)   10     2.98   0.00   1. Bxh6 Qxa1 2. Qg6 gxh6 3. Qxh6+ Kg8
>                                    4. Qg6+ Kh8 5. Qh6+
>         (2)   10->   4.05   0.00   1. Bxh6 Qxa1 2. Qg6 gxh6 3. Qxh6+ Kg8
>                                    4. Qg6+ Kh8 5. Qh6+
>               11     4.75   0.00   1. Bxh6 Qxa1 2. Qg6 gxh6 3. Qxh6+ Kg8
>                                    4. Qg6+ Kh8 5. Qh6+
>         (2)   11->   6.75   0.00   1. Bxh6 Qxa1 2. Qg6 gxh6 3. Qxh6+ Kg8
>                                    4. Qg6+ Kh8 5. Qh6+
>               12    11.41   0.07   1. Bxh6 Qxa1 2. Qe7 Rg8 3. Be3 Rc8
>                                    4. Bxb6 Qxb2 5. Bc7 Qb7 6. Qh4+ Kg8
>                                    7. Bxe5 Rc2 8. Qd8+ Kf7
>         (2)   12->  16.33   0.07   1. Bxh6 Qxa1 2. Qe7 Rg8 3. Be3 Rc8
>                                    4. Bxb6 Qxb2 5. Bc7 Qb7 6. Qh4+ Kg8
>                                    7. Bxe5 Rc2 8. Qd8+ Kf7
>               13    21.27   0.10   1. Bxh6 Qxa1 2. Qe7 Rg8 3. Be3 Rc8
>                                    4. Bxb6 Qxb2 5. Bc7 Qxa2 6. Bxe5 Qg8
>                                    7. Qh4+ Qh7 8. Qxh7+ Kxh7 9. Kg3
>               13->  27.98   0.10   1. Bxh6 Qxa1 2. Qe7 Rg8 3. Be3 Rc8
>                                    4. Bxb6 Qxb2 5. Bc7 Qxa2 6. Bxe5 Qg8
>                                    7. Qh4+ Qh7 8. Qxh7+ Kxh7 9. Kg3
>White(1): ?
>              time=36.95  cpu=241%  mat=1  n=47660K  fh=92%  nps=1289K
>              ext-> checks=4002140 recaps=128977 pawns=1500
>              ext->  1rep=244593 thrt:34710  pawn sac=0
>              predicted=0  nodes=47660917  evals=0
>              endgame tablebase-> probes done=0  successful=0
>              SMP->  split=960  stop=211  data=10/64  cpu=1:29  elap=36.95
>
>White(1): Bxh6
>              time used:  36.95
>======================================================================
>Black(1): undo
>Qxb6 forced
>White(1): Qxb6
>              time used:  19.07
>              clearing hash tables
>              time surplus   0.00  time limit 10:00 (10:00)
>         nss  depth   time  score   variation (1)
>                1     0.00  -5.37   1. ... Rf2 2. Qg6
>                1     0.00     ++   1. ... Rc8!!
>                1->   0.02  -4.98   1. ... Rc8
>                2     0.02     --   1. ... Rc8
>                2     0.02  -5.60   1. ... Rc8 2. Qe3 Qf1
>                2     0.02     ++   1. ... Rf2!!
>                2     0.02  -5.06   1. ... Rf2 2. Qg6 Qe2
>                2->   0.02  -5.06   1. ... Rf2 2. Qg6 Qe2
>                3     0.02     --   1. ... Rf2
>                3     0.02  -5.49   1. ... Rf2 2. a4 Kh7 3. b4
>                3->   0.03  -5.49   1. ... Rf2 2. a4 Kh7 3. b4
>                4     0.03     --   1. ... Rf2
>                4     0.03  -5.81   1. ... Rf2 2. Be3 Qxa1 3. Qb8+ Kh7
>                                    4. Bxf2
>                4     0.03  -5.72   1. ... Rc8 2. Qe3 Qxe3 3. Bxe3 Rc2
>         (2)    4->   0.06  -5.72   1. ... Rc8 2. Qe3 Qxe3 3. Bxe3 Rc2
>                5     0.06     --   1. ... Rc8
>                5     0.06  -6.04   1. ... Rc8 2. Qe3 Qxe3 3. Bxe3 Kh7
>                                    4. Kg3
>                5     0.10     ++   1. ... Rf1!!
>                5     0.11   0.41   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. b4 e3 6. a4
>                5->   0.11   0.41   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. b4 e3 6. a4
>                6     0.13   0.41   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. b4 e3 6. a4
>                6->   0.14   0.41   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. b4 e3 6. a4
>                7     0.14     ++   1. ... Rf1!!
>                7->   0.16   0.80   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. b4 e3 6. a4
>                8     0.17     ++   1. ... Rf1!!
>         (2)    8->   0.21   1.19   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. b4 e3 6. a4
>                9     0.21     --   1. ... Rf1
>                9     1.08     ++   1. ... Rf1!!
>                9     1.81   3.52   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. a4 e3 6. b4 e2 7. Bb2
>                                    Qxa1 8. Bxa1 e1=Q
>                9->   1.83   3.52   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. a4 e3 6. b4 e2 7. Bb2
>                                    Qxa1 8. Bxa1 e1=Q
>               10     2.02   3.57   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. b4 e3 6. Bb2 e2 7. b5
>                                    Qxa1 8. Bxa1 e1=Q
>               10->   2.06   3.57   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. b4 e3 6. Bb2 e2 7. b5
>                                    Qxa1 8. Bxa1 e1=Q
>               11     2.44   3.29   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. b4 e3 6. Bb2 e2 7. b5
>                                    Qf4+ 8. Kh1 Qd2 9. Bxg7 Kxg7
>               11->   2.56   3.29   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. b4 e3 6. Bb2 e2 7. b5
>                                    Qf4+ 8. Kh1 Qd2 9. Bxg7 Kxg7
>               12     2.85     ++   1. ... Rf1!!
>               12    17.24   4.04   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. b4 e3 6. Bb2 e2 7. a3
>                                    Qf4+ 8. Kh1 Qd2 9. Bd4 Qxd4 10. Re1
>               12->  17.50   4.04   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. b4 e3 6. Bb2 e2 7. a3
>                                    Qf4+ 8. Kh1 Qd2 9. Bd4 Qxd4 10. Re1
>               13    19.74   3.98   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. a3 e3 6. Bxe3 Qxa1 7.
>                                    Bd4 Qc1 8. Bc3 Qf4+ 9. Kh1 Kg6 10.
>                                    b4
>               13->  20.19   3.98   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. a3 e3 6. Bxe3 Qxa1 7.
>                                    Bd4 Qc1 8. Bc3 Qf4+ 9. Kh1 Kg6 10.
>                                    b4
>               14    24.89   3.78   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. a3 e3 6. Bxe3 Qxa1 7.
>                                    Bd4 Qc1 8. Be5 Qe3 9. Bg3 Kg6 10. a4
>               14->  25.53   3.78   1. ... Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
>                                    Qxf1 Qxf1 5. a3 e3 6. Bxe3 Qxa1 7.
>                                    Bd4 Qc1 8. Be5 Qe3 9. Bg3 Kg6 10. a4
>Black(0): ?
>              time=34.41  cpu=199%  mat=-4  n=46304K  fh=96%  nps=1345K
>              ext-> checks=4706810 recaps=135233 pawns=14978
>              ext->  1rep=369980 thrt:54945  pawn sac=0
>              predicted=0  nodes=46304432  evals=0
>              endgame tablebase-> probes done=0  successful=0
>              SMP->  split=1304  stop=129  data=10/64  cpu=1:08  elap=34.41
>
>Black(1): Rf1


That is the position.  In 1981 just before the tournament, we lost access to
our normal Cray.  The university of minnesota gave me access to theirs, but
it was not "interactive".  I had to submit a batch job, let it search,
get the batch output back to the front-end machine, edit it to see the move,
and so forth.

We were able to compute 10-15 seconds per move, basically, as we lost all
kinds of time editing the stuff.  No pondering.  No way to tell when our
batch job had finished except by going thru a complex process.  Total mess.


"easy move" caused Qxb6 to be played because that resulted in a target time
of about 5 seconds, at roughly 1000 nodes per second.  I fixed it seriously
before the next round...



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.