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
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...