Preprocessing vs leaf evaluating - any preprocessors left?
Tom King
Hi all,
I've recently changed the evaluation function in my program from being
(more or less) a pure preprocessor to (more or less) a pure leaf
evaluator. The result? Slower search, yes, but more interesting,
possibly stronger chess.
Anyone still doing pure preprocessing? I'd guess not, but would be
interested to hear otherwise.
--
Tom King
Komputer Korner
Nimzo 3.5 was a notorious preprocessor but I haven't done any tests
yet to determine if Nimzo 98 is still mainly preprocessing or not.
--
--
Komputer Korner
The inkompetent komputer
To send email take the 1 out of my address. My email address is
kor...@netcom.ca but take the 1 out before sending the email.
Tom King wrote in message ...
mclane
Tom King <t...@hatbulb.demon.co.uk> wrote:
>Hi all,
>I've recently changed the evaluation function in my program from being
>(more or less) a pure preprocessor to (more or less) a pure leaf
>evaluator.
Congratulations !
>The result? Slower search, yes, but more interesting,
>possibly stronger chess.
!!!
Very good. So next championship more chances ?!
>Anyone still doing pure preprocessing? I'd guess not, but would be
>interested to hear otherwise.
>--
>Tom King
best wishes
mclane
David Rasmussen
Komputer Korner wrote:
>
> Nimzo 3.5 was a notorious preprocessor but I haven't done any tests
> yet to determine if Nimzo 98 is still mainly preprocessing or not.
>
Could someone please explain the difference?
--
David Rasmussen
e-mail: ho...@kampsax.dtu.dk
"Life is what happens to you while you're busy making other plans." John
Lennon
Floyd Code: v1.2a r+d>s TW 1/0/pw tG sqrt(-1)? 0 DSotM 3 2 <6jun98>
Check http://www.memes.com/~tristandcw/fc/floydcode2.html for details
Robert Hyatt
David Rasmussen <ho...@kampsax.dtu.dk> wrote:
: Komputer Korner wrote:
:>
:> Nimzo 3.5 was a notorious preprocessor but I haven't done any tests
:> yet to determine if Nimzo 98 is still mainly preprocessing or not.
:>
: Could someone please explain the difference?
It means doing all your evaluation "busy-work" at the root, and then
using this stuff out at the ends of the branches you search. The
problem is best understood with an example:
suppose you evaluate your opponent's king safety and decide his king
is exposed. At the root, you set up piece/square tables that attract
every piece you have to where his king is *right now*. If you do a
12 ply search, it is possible that at moves 2,4,6,8,10 and 12, your
opponent moves his king to the other side of the board, yet you are
still trying to gather your pieces where his king *was*.
That's the problem with root evaluation... by the time you reach the
tip of a branch, things you decided on at the root might be completely
wrong for the tip position...
If you evaluate at the tips only (Crafty, for example) then you don't
fall into this trap, but you go slower.
: --
: David Rasmussen
: e-mail: ho...@kampsax.dtu.dk
: "Life is what happens to you while you're busy making other plans." John
: Lennon
: Floyd Code: v1.2a r+d>s TW 1/0/pw tG sqrt(-1)? 0 DSotM 3 2 <6jun98>
: Check http://www.memes.com/~tristandcw/fc/floydcode2.html for details
--
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
Steve Maughan
There are (at least) two schools of thought when it comes to evaluating a
chess position. One uses "Piece Value Tables". This method assigns a value
for a piece occupying a given square e.g. a knight on e4 may be worth 3.13
pawns whereas a knight on a1 may be worth 2.89 pawns. The table is usually
created at the beginning of each search and is depended upon the root
position. With this method calculating the incremental evaluation of a
position is simple -
Score = Score - PieceSquareValue(Piece,From) + PieceSquareValue(Piece,To).
Hence this method of evaluation is fast (up to 250 node/sec). Since the
Piece Value Table is calculated at the beginning of the search this is also
known as "Pre-processing".
The disadvantage of pre-processing is that as the search gets deeper the
position becomes less and less like the root. As a result the interactions
between the pieces are not accounted for accurately. This can lead to
inaccuracies in the evaluation.
The second school of thought is the leaf node evaluation where the position
is accurately evaluated at the end of each node. This is slow in comparison
to the pre-processing method but more accurate. Ironically, as hardware
gets faster the weaknesses of pre-processing become more apparent as
searches get deeper i.e. further away from the root node. This has resulted
in a shift to leaf node evaluation - hence the original question.
Nevertheless, Nimzo is an excellent exponent of pre-processing clocking over
200 node per second and 2500+ ELO
Regards
Steve Maughan
David Rasmussen wrote in message <35A11511...@kampsax.dtu.dk>...
>Komputer Korner wrote:
>>
>> Nimzo 3.5 was a notorious preprocessor but I haven't done any tests
>> yet to determine if Nimzo 98 is still mainly preprocessing or not.
>>
>
>Could someone please explain the difference?
>
>
Tom King
preprocessing in there. But it plays very good chess, and I can't
believe it could play that well with just preprocessing. Anyone know?
In article <6np2ec$n4m$1...@tor-nn1.netcom.ca>, Komputer Korner
<kor...@netcom.ca> writes
>Nimzo 3.5 was a notorious preprocessor but I haven't done any tests
>yet to determine if Nimzo 98 is still mainly preprocessing or not.
>
>--
>--
>Komputer Korner
>The inkompetent komputer
>
>To send email take the 1 out of my address. My email address is
>kor...@netcom.ca but take the 1 out before sending the email.
>Tom King wrote in message ...
>>Hi all,
>>
>>I've recently changed the evaluation function in my program from
>being
>>(more or less) a pure preprocessor to (more or less) a pure leaf
>>evaluator. The result? Slower search, yes, but more interesting,
>>possibly stronger chess.
>>
>>Anyone still doing pure preprocessing? I'd guess not, but would be
>>interested to hear otherwise.
>>--
>>Tom King
>
>
--
Tom King
Andrew Fan
> I've recently changed the evaluation function in my program from
> being (more or less) a pure preprocessor to (more or less) a
> pure leaf evaluator. The result? Slower search, yes, but more
> interesting, possibly stronger chess.
> Anyone still doing pure preprocessing? I'd guess not, but would
> be interested to hear otherwise.
Why not use both ?
I had written a chess program (Chinese Chess) some years back that
uses some form of preprocessing in the move ordering codes :
if move in PV list then
MoveScore = PVScore
else
MoveScore = Material difference + positional difference +
Value of pieces attacking - Value of pieces
under attack
end if
This preprocessing occurs at every ply.
At each leave node, I do a more detailed static position
evaluation.
The program was coded it in 680x0 assembly and runs on a
50MHz 68030 powered machine and achieved about 500 nodes/sec.
On average about 30% of the tree nodes was evaluated after
alpha-beta pruning. The program played much better than me
and some other portable chess computers which either shows that
I am a poor player or the program is fairly strong.
Is this the same type of preprocessing you had in mind ?
--
Andrew :)
Robert Hyatt
Andrew Fan <r28...@email.sps.mot.com> wrote:
:> I've recently changed the evaluation function in my program from
:> being (more or less) a pure preprocessor to (more or less) a
:> pure leaf evaluator. The result? Slower search, yes, but more
:> interesting, possibly stronger chess.
:> Anyone still doing pure preprocessing? I'd guess not, but would
:> be interested to hear otherwise.
: Why not use both ?
: I had written a chess program (Chinese Chess) some years back that
: uses some form of preprocessing in the move ordering codes :
: if move in PV list then
: MoveScore = PVScore
: else
: MoveScore = Material difference + positional difference +
: Value of pieces attacking - Value of pieces
: under attack
: end if
There is a much easier and simpler way to do the PV first. Simply take each
PV move and "stuff" them into the normal hash table at the start of an
iteration. Since you'd normally search hash table moves first anyway, this
means you follow the PV to the end, first... without any funny stuff about
special-casing the PV... and it is faster to boot...
: This preprocessing occurs at every ply.
: At each leave node, I do a more detailed static position
: evaluation.
: The program was coded it in 680x0 assembly and runs on a
: 50MHz 68030 powered machine and achieved about 500 nodes/sec.
: On average about 30% of the tree nodes was evaluated after
: alpha-beta pruning. The program played much better than me
: and some other portable chess computers which either shows that
: I am a poor player or the program is fairly strong.
: Is this the same type of preprocessing you had in mind ?
No... the idea is to do scoring at the root. IE find weak pawns and
set things up so pieces try to attack them during the search. Of course,
if one side can liquidate such a pawn, you end up attacking "vapor" here
and there...
: --
: Andrew :)
SMO CFI
>(more or less) a pure preprocessor to (more or less) a pure leaf
>evaluator. The result? Slower search, yes, but more interesting,
>possibly stronger chess.
>
>
Tom,
I have been thinking of adding some pre-processing to my program, the thought
being I could take some of the load off the leaf eval to speed it up, as well
as get a more detailed look at the position. You imply that you are still
doing some root node processing. What, in your view, is important to process
at the root, and not at the leaf?
Will
mclane
>Nimzo 98 is *very* fast. So I'd guess there's a lot of (well tuned)
>preprocessing in there. But it plays very good chess, and I can't
>believe it could play that well with just preprocessing. Anyone know?
I don't think it is still a pure preprocessor.
Of course, Nimzo98 has not much knowledge, but IMO it plays better
than fritz5.
One very good example about positive and negative behaviour of Nimzo98
is IMO the game vs. Chess Tiger from Paderborn.
[Event "7th IPCCC"]
[Site "Paderborn"]
[Date "1998.02.13"]
[Round "4"]
[White "CTiger 11.2"]
[Black "Nimzo98"]
[Result "1/2-1/2"]
1. d4 Nf6 2. c4 e6 3. Nf3 b6 4. e3 Bb7 5. Bd3 Be7 6. Nc3 d5 7. O-O O-O
8. Qe2 Nbd7 9. cxd5 exd5 10. b3 c6 11. a4 Re8 12. Qc2 g6 13. Bb2 Bd6
14. Rfc1 a5 15. Ba3 Bxa3 16. Rxa3 Ne4 17. Ra2 Qe7 18. Qd1 Qb4 19. Ne2
Rac8
20. h3 Ra8 21. Raa1 Rad8 22. Nf4 Re7 23. Qc2 Rc8 24. Ra2 Rce8 25. Kf1
g5
26. Ne2 f5 27. Kg1 h6 28. Nh2 f4 29. f3 Nd6 30. Bg6 Rf8 31. exf4 gxf4
32. Ng4 Kg7 33. Kh2 c5 34. Nf2 c4 35. bxc4 Nxc4 36. Bd3 Ba6 37. Nc3
Ne3
38. Qd2 Bc4 39. Bxc4 dxc4 40. Nfe4 Re6 41. d5 Rg6 42. d6 Kh7 43. Nd5
c3
44. Qd3 Qb3 45. Ndxc3 Ne5 46. Qb1 Qe6 47. Nf2 h5 48. Qe4 Rc8 49. d7
Nxd7
50. Qxe6 Rxe6 51. Ne2 Rxc1 52. Nxc1 Nc5 53. Nfd3 Rf6 54. Ra3 Nd5
55. Nxc5 bxc5 56. Rd3 Rf5 57. Ne2 Kh6 58. h4 c4 59. Rd4 Re5 60. Re4
Rxe4
61. fxe4 Nb4 62. Nxf4 c3 63. Ne2 c2 64. Nc1 Na6 65. Kg3 Nc5 66. Kf3
Nxa4
67. Ke3 Kg6 68. Nd3 Nc5 69. Nf4+ Kg7 70. Kd2 Nxe4+ 71. Kxc2 Ng3 72.
Kb3 Kf6
73. Ka4 Kf5 74. Nd5 Kg4 75. Kxa5 Kxh4 76. Kb4 Ne4 77. Kc4 Kg3 78. Kd4
1/2-1/2
This game showed up's and downs on both sides. I guess in the end you
could say: the draw was completely ok, both sides show the same
tactical and/or positional strength.
Typical for a NON-knowledge program like Nimzo98 is IMO move
19,20,21,23,24 where Nimzo moves the rook without any idea.
These are IMO typical (as a chess player I would call these moves:
NULL-MOVES, especially to tease the programmers a little) null-moves.
Tiger defended the big attack of Nimzo98 and in the end the draw was,
as I said, completely ok.
Chrilly and I lost a few litres sweat during the game, as you can
imagine.
best wishes
mclane
Komputer Korner
knowledge. This will slow it down of course, but the idea of only
evaluating at the root is to avoid the slowdown of tip evaluations.
Whether it has much knowledge or not is independent of it's choice of
how much root processing it does.
--
--
Komputer Korner
The inkompetent komputer
To send email take the 1 out of my address. My email address is
kor...@netcom.ca but take the 1 out before sending the email.
mclane wrote in message <6nugha$cin$1...@steve.prima.ruhr.de>...
>Tom King <t...@hatbulb.demon.co.uk> wrote:
>
>>Nimzo 98 is *very* fast. So I'd guess there's a lot of (well tuned)
>>preprocessing in there. But it plays very good chess, and I can't
>>believe it could play that well with just preprocessing. Anyone
know?
>
>I don't think it is still a pure preprocessor.
>Of course, Nimzo98 has not much knowledge, but IMO it plays better
>than fritz5.
>mclane
>
Andrew Fan
ordering algorithm? A target is identified at the root node by
some function/database and subsequent moves that "points" to the
target will be prefered?
Do you find a new target at each ply or just stick with the same
one, hoping you'll get at it at the terminal node?
--
Andrew.
Robert Hyatt
: It is important to realize that a preprocessor can also have lots of
: knowledge. This will slow it down of course, but the idea of only
: evaluating at the root is to avoid the slowdown of tip evaluations.
: Whether it has much knowledge or not is independent of it's choice of
: how much root processing it does.
depends on your definition of "knowledge"... knowledge applied at the
root is not nearly the same as knowledge applied at the tips. Tip
knowledge is more expensive and more accurate. Root knowledge is cheaper
and less accurate...
bruce moreland
<kor...@netcom.ca> wrote:
>It is important to realize that a preprocessor can also have lots of
>knowledge. This will slow it down of course, but the idea of only
>evaluating at the root is to avoid the slowdown of tip evaluations.
>Whether it has much knowledge or not is independent of it's choice of
>how much root processing it does.
At the one end of the scale is sloppiness, and at the other end is
caution.
Sloppy is faster, but depending upon how far you go with this you
might make mistakes or do things that just don't make sense.
Cautious is real slow, and if you're too cautious you'll decrease
speed without doing anything productive.
bruce
Tom King
<smo...@aol.com> writes
I'm not doing *any* preprocessing now. Previous versions of my program
used piece value squares, but the more I looked at it, the more I felt
disappointed with the approach. Deeper searches revealed more tactics
sometimes, but didn't help positional play very much.
What is it important to process (evaluate) at the root, not the leaf?
you ask. Good question. I'm sure other programmers have lots of
information on this one, but I'd say that if you can buy the slowdown,
you don't need to evaluate *anything* at the root. There are things you
can evaluate ok via piece value squares, though. A simple example is a
bonus for a rook on the 7th rank.
I'm guessing now, but my hunch is that most programs do both leaf- and
pre- processing.
--
Tom King
Tom King
<hy...@crafty.cis.uab.edu> writes
>Andrew Fan <r28...@email.sps.mot.com> wrote:
>:> I've recently changed the evaluation function in my program from
>:> being (more or less) a pure preprocessor to (more or less) a
>:> pure leaf evaluator. The result? Slower search, yes, but more
>:> interesting, possibly stronger chess.
>
>:> be interested to hear otherwise.
>
>: Why not use both ?
>
>: I had written a chess program (Chinese Chess) some years back that
>: uses some form of preprocessing in the move ordering codes :
>
>: if move in PV list then
>: MoveScore = PVScore
>: else
>: MoveScore = Material difference + positional difference +
>: Value of pieces attacking - Value of pieces
>: under attack
>: end if
>
>
>There is a much easier and simpler way to do the PV first. Simply take each
>PV move and "stuff" them into the normal hash table at the start of an
>iteration. Since you'd normally search hash table moves first anyway, this
>means you follow the PV to the end, first... without any funny stuff about
>special-casing the PV... and it is faster to boot...
>
>
Is this "PV stuffing" trick a good deal? I don't use it, because it's
always appeared to me that the PV moves are in the hash table anyhow? Am
I missing a performance boost here? (Having switched to leaf evaluation,
I'm worried about performance - again).
--
Tom King
SMO CFI
>Is this "PV stuffing" trick a good deal? I don't use it, because it's
>always appeared to me that the PV moves are in the hash table anyhow? Am
>I missing a performance boost here? (Having switched to leaf evaluation,
>I'm worried about performance - again).
I don't think there'd be much difference either way. But like you, I've always
just relied on the positions being in the tt table, without any special
stuffing. Maybe I'll have to verify that. Pretty easy to verify.
Will
Robert Hyatt
: Is this "PV stuffing" trick a good deal? I don't use it, because it's
: always appeared to me that the PV moves are in the hash table anyhow? Am
: I missing a performance boost here? (Having switched to leaf evaluation,
: I'm worried about performance - again).
: --
: Tom King
I don't find them in the hash table reliably... because after storing a
PV, you can search a huge tree, and overwrite many of the PV positions,
particularly those closer to the leaf nodes... This way, I reliably
follow the PV at the start of each iteration, and the cute thing is it
costs me *zero*. In a very early version of Cray Blitz we had a special
test to see if we were following the PV, and if so, to make sure the PV
move was searched first, even before capture moves. Now I don't have to
deal with that, because it happens automatically by the code that tries
the hash move first anyway...
Robert Hyatt
: I'm not doing *any* preprocessing now. Previous versions of my program
: used piece value squares, but the more I looked at it, the more I felt
: disappointed with the approach. Deeper searches revealed more tactics
: sometimes, but didn't help positional play very much.
: What is it important to process (evaluate) at the root, not the leaf?
: you ask. Good question. I'm sure other programmers have lots of
: information on this one, but I'd say that if you can buy the slowdown,
: you don't need to evaluate *anything* at the root. There are things you
: can evaluate ok via piece value squares, though. A simple example is a
: bonus for a rook on the 7th rank.
I don't use this, because a rook on the 7th can be meaningless, as when
the king is on the 6th and there are no pawns on the 7th. There are enough
cases that the only thing I use piece/square tables for are for occupying
the center, and not occupying the edge. Everything else is dynamic.
: I'm guessing now, but my hunch is that most programs do both leaf- and
: pre- processing.
: --
: Tom King
--
Robert Hyatt
:>
:>Is this "PV stuffing" trick a good deal? I don't use it, because it's
:>always appeared to me that the PV moves are in the hash table anyhow? Am
:>I missing a performance boost here? (Having switched to leaf evaluation,
:>I'm worried about performance - again).
: I don't think there'd be much difference either way. But like you, I've always
: just relied on the positions being in the tt table, without any special
: stuffing. Maybe I'll have to verify that. Pretty easy to verify.
: Will
It depends. If your 2nd pv move is not there, there will be a big difference
if it is an odd move, because you won't find it quickly and waste lots of extra
nodes doing so.
You could certainly modify your program to check this out... at the start of
each iteration, just run down the PV, making moves and calling LookUp() to
see which moves are found and which are not. I bet you find that many are not
there. Otherwise we'd all be using the hash table to produce a PV, rather
than backing the PV up in the search...
mclane
>Sloppy is faster, but depending upon how far you go with this you
>might make mistakes or do things that just don't make sense.
>Cautious is real slow, and if you're too cautious you'll decrease
>speed without doing anything productive.
>bruce
Moving a rook from
19...Rac8
20...Ra8
21.. Rad8
23...Rc8
24...Rce8
looks very cautious and not sloppy !
Also it does not look much intelligent. It gives away many tempi. And
it outs a preprocessor, or ?
best wishes
mclane
bruce moreland
>Moving a rook from
>
>19...Rac8
>20...Ra8
>21.. Rad8
>23...Rc8
>24...Rce8
>
>looks very cautious and not sloppy !
>Also it does not look much intelligent. It gives away many tempi. And
>it outs a preprocessor, or ?
>best wishes
No. Mine is not a preprocessor and it does this sometimes.
I haven't seen anything yet that doesn't make dumb mistakes.
Sometimes a program doesn't see a productive plan.
bruce