The issue with quiet moves is that there no good static ordering of them, i.e. nothing similar to MVV/LVA for captures. If the hash move or the captures don't trigger at cut-off many engines guess the best quiet move from similar positions. The most used idea is killer moves.
I have always wondered whether killer moves are enough and if we can do better. A few days ago I started experimenting with minimum hashing https://en.wikipedia.org/wiki/MinHash , and through a long list of experiments I found that we might be able to do better than killer moves.
Killer moves uses the current ply as context for prediction the best quiet move. I experimented with several ways to predict based on current position and I found two contexts that work well together:
* bitboard for current player pieces
* bitboard of all pieces of the same kind of the last piece moved (e.g. all enemy pawns, if enemy moved a pawn).
On most positions I tested the new idea produces trees that are about 8% smaller. The hitrate given that the move is quiet, non-hash and a cut-off is 3-5% smaller than the hitrate of killers.
I ran quick match at STC and it showed a small improvement. I will run LTC after I test a small variation.
4487 @ 40/15+0.05
1514 - 1343 - 1630
ELO 13.25±8.12
The first draft of the code is here https://bitbucket.org/brtzsnr/zurichess ... s/minhash2 , not ready yet to be cherry picked into the master, but understandable. The diff is only 85 lines of code.
Context computation is done in the code below. murmurMix is a hashing function. There is no minhash anymore, I dropped that part of the code., it's just hashing. I dropped killers altogether which were replaced by this new algorithm.
Code: Select all
+func (pos *Position) MinHash() (int, int) {
+ if pos.curr.minhash[0] != 0 {
+ return pos.curr.minhash[0] - 1, pos.curr.minhash[1] - 1
+ }
+
+ h0 := murmurMix(uint64(pos.ByColor[pos.Us()]), murmurSeed[pos.Us()])
+ pos.curr.minhash[0] = int(h0>>(64-bits)) + 1
+
+ l := pos.LastMove().Target()
+ bb := pos.ByPiece(l.Color(), l.Figure())
+
+ h1 := murmurMix(uint64(bb), murmurSeed[pos.Us()])
+ pos.curr.minhash[1] = int(h1>>(64-bits)) + 1
+
+ return pos.curr.minhash[0] - 1, pos.curr.minhash[1] - 1
+}
* Other player's pieces
* Our/Other player's minors and majors
* Everything without border squares
* Current ply (very similar to Killer moves)
Can somebody test this idea with her/his engine? I can help with a small review if you get stuck.