Currently my move ordering is:
PV move.
LVA/MVA.
With no pruning techniques except of course for Alpha/Beta...my engine can complete depth 8 in around 15s.
I am wondering what improvement I can expect if I added TT Hash move.
PV Move
TT Hash
LVA/MVA
Here is my engine (JAVA Applet)
www.mytopcoder.com/gmol
Thanks in advance!
How effective is move ordering from TT?
Moderators: hgm, Rebel, chrisw
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: How effective is move ordering from TT?
what do you mean by "PV move" ?voyagerOne wrote:Currently my move ordering is:
PV move.
LVA/MVA.
With no pruning techniques except of course for Alpha/Beta...my engine can complete depth 8 in around 15s.
I am wondering what improvement I can expect if I added TT Hash move.
PV Move
TT Hash
LVA/MVA
Here is my engine (JAVA Applet)
www.mytopcoder.com/gmol
Thanks in advance!
-
- Posts: 154
- Joined: Tue May 17, 2011 8:12 pm
Re: How effective is move ordering from TT?
Principal variation from last iteration of ID.
-
- Posts: 4367
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: How effective is move ordering from TT?
If you are doing hashing right, your TT move is the best move from the last time the node was visited. That is, the move that caused cutoff, or that scored best. Re-using this move is very effective because often it will cause cutoff again. If no move caused cutoff I store the move that was sorted first from the move generator but re-using this is less effective.
--Jon
--Jon
-
- Posts: 27811
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: How effective is move ordering from TT?
Using the TT move should be enormously effective compared to only using the PV move. As a depth-8 search has only 7 PV nodes where there is a PV move from the depth-7 search. While a hash move should be available in every cut node of the first seven levels.
So where following the PV helps you to get good settings of alpha and beta from the start, the TT moves help you to always search a move that scores above that beta as first move, when there is one available. With the static move ordering there would be many nodes where you would find the cut move w.r.t. the correct beta only as 2nd, 3rd or even 25th move.
In principle the TT should already contain the PV, so there would be no need to separately play a PV move and a TT move.
So where following the PV helps you to get good settings of alpha and beta from the start, the TT moves help you to always search a move that scores above that beta as first move, when there is one available. With the static move ordering there would be many nodes where you would find the cut move w.r.t. the correct beta only as 2nd, 3rd or even 25th move.
In principle the TT should already contain the PV, so there would be no need to separately play a PV move and a TT move.
-
- Posts: 154
- Joined: Tue May 17, 2011 8:12 pm
Re: How effective is move ordering from TT?
To HG: Thanks for the feedback.
Are you able to ballpark some numbers for me?
What depth do you think one can reach with just move ordering in a reasonable amount of time (30s) in mid game?
Thanks in advance!
Are you able to ballpark some numbers for me?
What depth do you think one can reach with just move ordering in a reasonable amount of time (30s) in mid game?
Thanks in advance!
-
- Posts: 27811
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: How effective is move ordering from TT?
This is very hard to quantify, because it depends on the details of your move ordering. Best approach would be to let your engine keep statistics: at each ply level count the number of nodes, the number of beta cutoffs, and the number of moves searched before the beta cutoff. Then you can calculate the branching ratio in your cut nodes at each level. For a good search this should be well below 1.5 (perhaps even 1.1). So if you find 3, it means your effective branching ratio could be increased by a factor sqrt(2) to sqrt(2.7), or 1.4 - 1.65.
But not all that improvement comes from using TT. Killer, and some ordering of non-captures will also contribute an improvement.
But not all that improvement comes from using TT. Killer, and some ordering of non-captures will also contribute an improvement.
-
- Posts: 686
- Joined: Thu Mar 03, 2011 4:57 pm
- Location: Germany
Re: How effective is move ordering from TT?
If you want to know whether it is worth the effort implementing a TT, I can tell you it is.
Mr. Schaeffer states (and most of the 99% come probably from the TT)
http://www.faui01.de/brettspiele/schaef ... ements.pdf
Mr. Schaeffer states (and most of the 99% come probably from the TT)
http://www.faui01.de/brettspiele/schaef ... ements.pdf
Results indicate that the history heuristic and transposition
tables significantly out-perform other alpha-beta enhancements in application generated game trees. For
trees up to depth 8, when taken together, they account for over 99% of the possible reductions in tree size,
with the other enhancements yielding insignificant gains.
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: How effective is move ordering from TT?
As explained by Jon Dart, the "PV move" is useless if you use TT. Here's the move ordering that I use in DiscoCheck:voyagerOne wrote:Currently my move ordering is:
PV move.
LVA/MVA.
With no pruning techniques except of course for Alpha/Beta...my engine can complete depth 8 in around 15s.
I am wondering what improvement I can expect if I added TT Hash move.
PV Move
TT Hash
LVA/MVA
Here is my engine (JAVA Applet)
www.mytopcoder.com/gmol
Thanks in advance!
1/ Search (all legal moves)
* TT move
* captures and promotions with SEE >=0, sorted by MVV/LVA
* captures and promotions with SEE < 0, sorted by SEE
* killer move: this is the last quiet move that gave a cutoff at the same ply. I use only one killer per ply now (many programs use 2)
* non killer quiet moves by History score
2/ QSearch depth = 0 (quiet checks + captures + queen promotions)
* same as 1/,m except that quiet moves are only checks in this case
3/ QSearch depth < 0 (captures + queen promotions)
* captures by MVV/LVA. Note that using SEE for bad captures and MVV/LVA for good captures is slightly better (in reducing the node count), but this avoid a lot of unnecessary SEE computations thanks to early beta cutoffs. Overall the gain (speed) compensates the pain (slightly more nodes)
Note that despite what some may say, the killer move heuristic isn't very useful, it only gives a small improvement over a proper implementation of History ordering. History and Killer are a bit redundant in a way, so if you have to choose one or the other it should be History (much more general and scalable). I previously used the mate killer and 2 (non mate) killer-slots, and concluded with extensive testing that the mate killer was useless (if not harmful) and so was the second killer (2nd killer was actually harmful better to trust the history than the 2nd killer). I haven't tried the "killer from 2 plies ago" heuristic though.
-
- Posts: 5258
- Joined: Mon Feb 27, 2006 4:31 pm
- Location: Atlanta, Georgia
Re: How effective is move ordering from TT?
In principle or in fact? I've always poked the PV into the hash table at the end of each iteration but I never knew if that was really necessary.hgm wrote:In principle the TT should already contain the PV, so there would be no need to separately play a PV move and a TT move.
Best
Dan H.