How effective is move ordering from TT?

[voyagerOne]

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!

[lucasart]

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!

what do you mean by "PV move" ?

[voyagerOne]

Principal variation from last iteration of ID.

[jdart]

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

[hgm]

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.

[voyagerOne]

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!

[hgm]

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.

[tpetzke]

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

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.

[lucasart]

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!

As explained by Jon Dart, the "PV move" is useless if you use TT. Here's the move ordering that I use in DiscoCheck:

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.

[Dan Honeycutt]

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.

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.

Best
Dan H.