Hi all,
my chess engine RBrChess is one of the weaker engines around. I,m now stuck a little on how to improve further.
It does have:
- a quite extensive evaluation function with piece-square tables, king safety and more ..
- iterative deepening
- quite extensive move ordering
- pondering support
But it doesn't have:
- transposition tables
- null move pruning
- bitboards (now use 12x12 matrix of integers)
- ....
Question:
Has anyone a clue of how much ELO you can gain with these 3 (or other) improvements ?
I would guess 100-200 ELO with hash tables, 50-100 ELO with null move pruning.
Thanks, Roger
How to improve further ?
Moderators: hgm, Rebel, chrisw
-
- Posts: 154
- Joined: Thu May 31, 2007 9:05 pm
- Location: Madrid, Spain
Re: How to improve further ?
Hi Roger,
I think that transposition table and null move are a must, and they can easily give you 200-250 ELO, at least they did to me.
I think that transposition table and null move are a must, and they can easily give you 200-250 ELO, at least they did to me.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: How to improve further ?
The first two are essential features. transposition tables are not that hard to add, and null-move search is really easy. Probably in a full game, null-move search will help the most, although transposition tables are the very reason for doing an iterative-deepening search in the first place, so you might gain a significant amount of speed due to the improved move ordering the trans/ref table will provide.Rogerb wrote:Hi all,
my chess engine RBrChess is one of the weaker engines around. I,m now stuck a little on how to improve further.
It does have:
- a quite extensive evaluation function with piece-square tables, king safety and more ..
- iterative deepening
- quite extensive move ordering
- pondering support
But it doesn't have:
- transposition tables
- null move pruning
- bitboards (now use 12x12 matrix of integers)
- ....
Question:
Has anyone a clue of how much ELO you can gain with these 3 (or other) improvements ?
I would guess 100-200 ELO with hash tables, 50-100 ELO with null move pruning.
Thanks, Roger
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: How to improve further ?
How do you even *do* IID without a hash table?bob wrote:The first two are essential features. transposition tables are not that hard to add, and null-move search is really easy. Probably in a full game, null-move search will help the most, although transposition tables are the very reason for doing an iterative-deepening search in the first place, so you might gain a significant amount of speed due to the improved move ordering the trans/ref table will provide.Rogerb wrote:Hi all,
my chess engine RBrChess is one of the weaker engines around. I,m now stuck a little on how to improve further.
It does have:
- a quite extensive evaluation function with piece-square tables, king safety and more ..
- iterative deepening
- quite extensive move ordering
- pondering support
But it doesn't have:
- transposition tables
- null move pruning
- bitboards (now use 12x12 matrix of integers)
- ....
Question:
Has anyone a clue of how much ELO you can gain with these 3 (or other) improvements ?
I would guess 100-200 ELO with hash tables, 50-100 ELO with null move pruning.
Thanks, Roger
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: How to improve further ?
Not "IID". just "ID". The idea of doing a 1 ply search, and using that to order a 2 ply search, etc... IID is the same idea applied internally to the tree when you don't have a hash move to search first on a PV-type node.Dann Corbit wrote:How do you even *do* IID without a hash table?bob wrote:The first two are essential features. transposition tables are not that hard to add, and null-move search is really easy. Probably in a full game, null-move search will help the most, although transposition tables are the very reason for doing an iterative-deepening search in the first place, so you might gain a significant amount of speed due to the improved move ordering the trans/ref table will provide.Rogerb wrote:Hi all,
my chess engine RBrChess is one of the weaker engines around. I,m now stuck a little on how to improve further.
It does have:
- a quite extensive evaluation function with piece-square tables, king safety and more ..
- iterative deepening
- quite extensive move ordering
- pondering support
But it doesn't have:
- transposition tables
- null move pruning
- bitboards (now use 12x12 matrix of integers)
- ....
Question:
Has anyone a clue of how much ELO you can gain with these 3 (or other) improvements ?
I would guess 100-200 ELO with hash tables, 50-100 ELO with null move pruning.
Thanks, Roger
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: How to improve further ?
As others already stated, adding transposition tables and null move pruning should have a noticeable benefit. Switching to bitboards might in your case lead to an ELO decrease in the beginning sinceRogerb wrote:Hi all,
my chess engine RBrChess is one of the weaker engines around. I,m now stuck a little on how to improve further.
It does have:
- a quite extensive evaluation function with piece-square tables, king safety and more ..
- iterative deepening
- quite extensive move ordering
- pondering support
But it doesn't have:
- transposition tables
- null move pruning
- bitboards (now use 12x12 matrix of integers)
- ....
Question:
Has anyone a clue of how much ELO you can gain with these 3 (or other) improvements ?
I would guess 100-200 ELO with hash tables, 50-100 ELO with null move pruning.
Thanks, Roger
a) you will most probably have to rewrite a considerable amount of code, which often introduces new bugs, and
b) there is a high learning curve for bitboards.
Even without that, with the current level of your engine I doubt that a perfect bitboard implementation would result in any substantial ELO improvement.
But I think there is another important point to consider. According to the results of your engine that I could find with a quick search (e.g. OpenWar, WBEC New Engines Qualify), the engine currently is around 1600 ELO or even below this, and for me this is a strong indication that there may be some major problems already in the *present* code. I think that a properly written engine, even without TT and nullmove, should not have less than 1600 ELO.
There are many potential problems to search for before adding new complexity like TT or nullmove, for instance:
- time control problems
- bugs in draw detection
- bad evaluation in certain cases
- insufficient endgame knowledge
- eval bugs causing asymmetric evaluation (different values when switching white and black color of all pieces and side to move)
- inefficient quiescence search
- inefficient search in general due to bad move ordering
- or even bugs causing silent corruption of some piece of memory without crashing the program
Watch out carefully for these, if you did not do it yet. Do even more tests. Have you checked your move generator with perft?
Sven
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: How to improve further ?
In searches without hashtable IID is even more important.Dann Corbit wrote:How do you even *do* IID without a hash table?bob wrote:The first two are essential features. transposition tables are not that hard to add, and null-move search is really easy. Probably in a full game, null-move search will help the most, although transposition tables are the very reason for doing an iterative-deepening search in the first place, so you might gain a significant amount of speed due to the improved move ordering the trans/ref table will provide.Rogerb wrote:Hi all,
my chess engine RBrChess is one of the weaker engines around. I,m now stuck a little on how to improve further.
It does have:
- a quite extensive evaluation function with piece-square tables, king safety and more ..
- iterative deepening
- quite extensive move ordering
- pondering support
But it doesn't have:
- transposition tables
- null move pruning
- bitboards (now use 12x12 matrix of integers)
- ....
Question:
Has anyone a clue of how much ELO you can gain with these 3 (or other) improvements ?
I would guess 100-200 ELO with hash tables, 50-100 ELO with null move pruning.
Thanks, Roger
I found in 90s a trick there which would've been great for dedicated computers with just 4KB ram and a tad more ROM, to improve move ordering major league.
Hashtable kills all that though.
In 90s of course a lot of all this didn't get observed as most engines, not crafty - it was one of the exceptions back then, they had a branching factor of 10.0
The initial fritz 5.16 from 1997 had a b.f. of 10.0 or so above 10 ply.
Schach 3.0 also if you was lucky 10.0 and so on. All that to see tactics better.
At such huge branching factors CPU power initially seems much more important then than improve the b.f. a little.
It was around 1999 that everyone started to get concerned about b.f.
Note i had posted that already a few years before.
IID is another such typical trick that everyone knew, but also for diep first 10 plies IID is just not even break even, as we already have that hashtable and as Bob correctly notices ID.
As we get nowadays of course far above 10 ply, which Diep didn't get before 1999, such techniques are more relevant now.
So as soon as you refer to searching without hashtable you should also mention that most likely in such case you don't have very fast cores to your avail
Vincent
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: How to improve further ?
Elo improvements depend so much upon current strengths and what is its achillesheel further when it gets a few ply more.Rogerb wrote:Hi all,
my chess engine RBrChess is one of the weaker engines around. I,m now stuck a little on how to improve further.
It does have:
- a quite extensive evaluation function with piece-square tables, king safety and more ..
- iterative deepening
- quite extensive move ordering
- pondering support
But it doesn't have:
- transposition tables
- null move pruning
- bitboards (now use 12x12 matrix of integers)
- ....
Question:
Has anyone a clue of how much ELO you can gain with these 3 (or other) improvements ?
I would guess 100-200 ELO with hash tables, 50-100 ELO with null move pruning.
Thanks, Roger
I ship you email about some strange stuff more there in Dutch
and attachment when i tried to play against it.
Vincent
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: How to improve further ?
Don't be concerned with the amount of Elo points added; whatever rating improvement that will come, will come.
Having a move/score transposition table is an immense improvement. Even if the score portion of an entry is ignored (no pruning), the move ordering by itself produces far more efficient searches. And in the endgame, a transposition table with pruning can easily triple the obtainable search depth.
A null move pruning search is very good improvement, although the overall benefit can be reduced by other techniques like LMR and related depth reductions.
With fast and reasonably priced 64 bit processors, there's no excuse not to have a bitboard program. The only point of contention is how extensively bitboards should be used.
Having a move/score transposition table is an immense improvement. Even if the score portion of an entry is ignored (no pruning), the move ordering by itself produces far more efficient searches. And in the endgame, a transposition table with pruning can easily triple the obtainable search depth.
A null move pruning search is very good improvement, although the overall benefit can be reduced by other techniques like LMR and related depth reductions.
With fast and reasonably priced 64 bit processors, there's no excuse not to have a bitboard program. The only point of contention is how extensively bitboards should be used.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: How to improve further ?
I always thought that the fact that it is an enormous amount of high complex work, and in intself brings you approximately nothing, is a pretty good excuse...sje wrote:With fast and reasonably priced 64 bit processors, there's no excuse not to have a bitboard program. The only point of contention is how extensively bitboards should be used.