Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Trick Marsland

71 views
Skip to first unread message

Robert Hyatt

unread,
Feb 15, 1996, 3:00:00 AM2/15/96
to
In article <ravenek-1502...@polonium.chem.vu.nl>,
Walter Ravenek <rav...@chem.vu.nl> wrote:
>Not so long ago there was a suggestion by Marsland to attempt
>to get more out of the transposition table by also inspecting
>successor nodes if a certain node was not found.
>
>I tried this in my program Arthur and essentially reproduced
>Bob Hyatt's results. I got slightly fewer nodes, but this was
>offset by the additional work that needed to be done. Actually,
>this even took some effort because the regular domove/undomove
>is much too slow for this purpose, so I had to write routines
>to just calculate the effect of moves on the hash key.
>
>After more extensive tests I found that the above holds in
>middlegame positions. In endgame positions I see a gain of
>something in the order of 5-15 percent (both in nodes and
>time). I suspect this is caused by a higher hit rate in the
>transposition table.
>
>The overall effect is that in the analysis of a specific game
>(for one player only, to simulate playing a game) at 7 ply I
>get a reduction from 555 to 525 seconds.


Perhaps the most annoying thing about this whole idea is that
in most programs, you can toss in a 100-point "bonus" at just a
few random positions, and make the search much faster for some
positions, and slower for others. If you aren't careful about
the positions you test, then, you can make the wrong conclusion.

I ran a bunch of tests on this, and plan on coming back and trying
the idea again before long, just to make sure that after "redoing"
things I don't find some flaw in the original experiment. It happens
more times than I like to admit. :) In any case, my, your, and
Bruce's results were similar. To me, it just means that we are
(must be) doing something different than Phoenix was. Maybe R=2
recursive null move, maybe killers *and* history move, who knows.

This should go into an "idea box" that gets opened every so often
for testing again.

My next plan for Crafty is to use what I would call the "Ken
Thompson" PVS algorithm that we also used in Cray Blitz for a
while. The idea is this: after searching the first root move,
PVS searches the remaining root moves with beta=alpha+1, so that
all moves either fail low or high. If one fails high, most current
programs re-search the move with a relaxed upper bound to get a
true score immediately. Ken simply put this move aside, and continued
searching with beta=alpha+1. If he finished the root move list, the
move that "failed high" is the best move, and he made it. The only
difficulty is that a second move might also fail high, which makes it
impossible to distinguish between the two moves. He would then re-search
the first with relaxed beta, and get a new alpha as a result. He then
re-searched the second with beta=newalpha+1, and if it failed high, he
put this aside as above, if it failed low, toss it.

What this does is to avoid the *expensive* re-search of a fail-high
move if it can be avoided. I did this for several years in Cray Blitz,
but ultimately removed it because quite frequently you complete a
search without having a PV. This does two things: (1) it affects
move ordering for the next search and (2) provides no "best reply" for
pondering while waiting on the opponent.

Crafty has solutions for both of these issues already "built-in." For
the missing PV for the next iteration, crafty will use internal
iterative deepening which is probably about as slow as doing the re-search
of the original move so it's a wash at worst, and maybe faster at best.
However, this does get us through the ply-1 move list faster. For the
no ponder move, crafty has several "tricks up its sleeve". It looks in
the hash table to find a move to ponder, or, that failing, it begins a
"puzzling" search which is simply a relatively short search, from the
position with opponent-to-move, to find a good move for the opponent.
Since both of these issues have a possible solution already done, I'm
going to "re-visit" this idea again soon. Hence the "idea box" approach.

Bob
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170

Graham Laight

unread,
Feb 16, 1996, 3:00:00 AM2/16/96
to
Bob - from my scrapbook - Blitz 6.5 V Belle, North American Computer
Championship, Washington, December 78. Do you remember this game? I was 15 when
this game was played!

White's move 7 was poor (CB sees a piece for two pawns as equal to losing a
pawn!!!), but black's move 10 was devastating!

1. e4 e5
2. Nf3 Nc6
3. Nc3 Nf6
4. Bb5 Nd4
5. Bc4 Bc5
6. Nxe5 Qe7
7. Bxf7+ ? Kf8
8. Ng6+ h7xe6
9. Bc4 Nxe4
10. 0-0 rxh2!!
11. Kxh2 Qh4+
12. Kg1 Ng3!
13. Qh5 g6xh5
14. f2xg3 Nf3++
--
Graham Laight
Graham...@largotim.co.uk


Robert Hyatt

unread,
Feb 16, 1996, 3:00:00 AM2/16/96
to
In article <824489...@mis.largotim.co.uk>, Graham Laight <grahaml> wrote:
--->Bob - from my scrapbook - Blitz 6.5 V Belle, North American Computer
--->Championship, Washington, December 78. Do you remember this game? I was 15 when
--->this game was played!
--->
--->White's move 7 was poor (CB sees a piece for two pawns as equal to losing a
--->pawn!!!), but black's move 10 was devastating!
--->
--->1. e4 e5
--->2. Nf3 Nc6
--->3. Nc3 Nf6
--->4. Bb5 Nd4
--->5. Bc4 Bc5
--->6. Nxe5 Qe7
--->7. Bxf7+ ? Kf8
--->8. Ng6+ h7xe6
--->9. Bc4 Nxe4
--->10. 0-0 rxh2!!
--->11. Kxh2 Qh4+
--->12. Kg1 Ng3!
--->13. Qh5 g6xh5
--->14. f2xg3 Nf3++
--->--
--->Graham Laight
--->Graham...@largotim.co.uk
--->


Yes. I was there, too. :) The rook sac was so good, the next year,
Ken Thompson showed up at the tournament with a T-shirt with the game
score and position printed (professionally of course) on it. With the
caption "and Belle played: ... Rxh2!!"

Btw, this was not Cray Blitz back then, we were running on a Univac 1100/42
at Univac Federal Systems Division in Washington, DC.

However, we returned the favor in 1983. :) (how about posting a *win*
next time... :) )

Those were the days...

0 new messages