New killer idea

[brtzsnr]

(pun intended)

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 prediction contexts I tried:
* 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.

[Gerd Isenberg]

Interesting!

[elcabesa]

I'm trying to read your code, the patch is not very clean

let me summarize some point and let's check wheter or not I understood your code:

1) you use the killer infrastructure
2) instead of saving the killers, you save every quiet move in an array indexed by ourpiecesBB and lastMovedPieceBB.
3) using the same index you retrieve the moves.

how big is the minHash array?
it's murmurmix needed or it can be used some other hashing code?

[brtzsnr]

Sorry about the code quality. It's a squash of 20 patches or so. Will get better, hopefully.

I think you got the idea right.

> how big is the minHash array?

2^11 entries. It's about maximum that made any noticeable change.

> it's murmurmix needed or it can be used some other hashing code?

Any hashing would do. I found murmur mixing to be relatively good and fast. What function do you use?

[elcabesa]

Any hashing would do. I found murmur mixing to be relatively good and fast. What function do you use?

I realy don't know, looking at the code it looks like I don't have any better hashing

I'll give it a try in the next week.

have you tried with both killers and your improved code working toghether? first your code and then the killers?

[mar]

interesting, in my previous work I used locality sensitive hashing to detect similarity of small images (icons)
input was n values (any range) [quantized DCT coeffs of 16x16 downsampled grayscale image]
output was k-bit signature (k < n)

first one has to compute k*n random numbers with normal distribution; with other words k n-valued vectors representing a normal vector in Rn (n-dimensional planes at origin),
effectively cutting it into 2k distinct pieces

then one simply does k dotproducts with this table, each time the dot product yields a value >= 0, the corresponding k-th signature bit is 1, otherwise 0
(=whenever it lies in the positive halfspace of the plane)

similarity was then simply computed using (weighted) hamming distance

I wonder how much this minhash has to do with LSH (never heard of it before) Need to look at the link

[brtzsnr]

Yes, for a while I did have killers also, but I ended up dropping them. I have an incomplete test (LLR 2.36) that shows ~4.67 Elo when using one killer.

My objective was to improve the hitrate on ECM / STS which allowed me to iterate faster than actually running matches. Using ply as context (close to killer moves) didn't work very well.

[mar]

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).

Ok I think I understand your idea, but why call it minhash (now that I know what it is ?
You simply hash bitboards to get a context and use it as index into killer table. How is this different from eval cache except that you store two entries?
Am I missing something?

[brtzsnr]

It's not minhash. I started with that, but it got lost on the way. It's just two hashes now.

[mar]

It's not minhash. I started with that, but it got lost on the way. It's just two hashes now.

You're right, I missed this:

There is no minhash anymore, I dropped that part of the code., it's just hashing.

Should read more carefully next time, sorry. Interesting idea though.

EDIT: simplification idea: what about using two smaller tables for stm instead of hashing in stm?
also, why checking for 0 and offset by 1?