Weaker play with TT

[maksimKorzh]

Yup. I'm aware of BigInts and typed arrays - was thinking to consider them but rejected due to the same reasons you did.

cj

Just to clarify, I do use typed arrays, I don't use big ints.
So as tomitank - I know, I saw that in both sources)

Now some weird stuff with hash size happens - if I use size of tt entry = 20 bytes as suggested than changing Mb doesn't match - I add only say 4 Mb while actually used memory grows in 20 Mb...

How to get the size of object in javascript?? Is it impossible??

my tt entry is:

Code: Select all

{
  hashKey: js type Number,
  score: js type Number,
  depth: js Type Number,
  flag: js type Number,
  bestMove: js type Number
}

When I use 80 = 16 * 5 then people say it's horribly wrong but that's the only way to get at least rough estimate values correlating with actual change
of the actual RAM used. I know that using Number type is expensive and better to use typed array, but the problem is that I can't get the size of a variable in JS. This is so weird.

[hgm]

If I were to do this, I would use a typed array of 32-bit integers, only allow the index i to be a multiple of 4 (by masking away the lowest two bits together with unwanted upper bits), and then use element i for the signature, i+1 for the score, i+2 for the move, and i+3 for the depth and flags. And pack/unpack them 'by hand'. (E.g. to test the flags you don't care whether there also is a depth in other bits of the word, and to get the depth you mask away the flag bits.The move you can store as toSqr + 256*fromSqr, and on probing do fromSqr = move >> 8; toSqr = move & 256;.)

That would probably be a lot faster than messing with JavaScript objects containing a variety of types as fields. And also more memory efficient.

[maksimKorzh]

UPDATE ON QUESTION:

I've revealed that hash keys are wrong when null move pruning occurs.
But the strange thing is that when I was allowing to do null move several times in the row
this wasn't so, I mean hash keys were correct, so now with making null move only if
previous move wasn't null move I;m starting getting these incorrect hash values.

Here's the code for null move pruning:

Code: Select all

// previous move wasn't null move
if (nullMove) {
        // null move pruning
        if ( searchPly && depth > 2 && staticEval >= beta) {
          let correct = generateHashKey();
          if (hashKey != correct) {
            // gives wrong hash keys here!
            console.log('wrong:', hashKey, '  correct:', correct, ' ep:', enpassant);
          }
          
          makeNullMove();
          score = -negamax(-beta, -beta + 1, depth - 1 - 2, NO_NULL);
          takeNullMove();

          if (timing.stopped == 1) return 0;
          if (score >= beta) return beta;
        }
        ...
}

Here's the code for make/take null move:

Code: Select all

  // make null move
  function makeNullMove() {
    // backup current board state
    moveStack.push({
      move: 0,
      capturedPiece: 0,
      side: side,
      enpassant: enpassant,
      castle: castle,
      fifty: fifty,
      hash: hashKey,
    });
    
    if (enpassant != noEnpassant) hashKey ^= pieceKeys[enpassant];
    enpassant = noEnpassant;
    
    fifty = 0;
    side ^= 1;
    hashKey ^= sideKey;
  }
  
  // take null move
  function takeNullMove() {
    // restore board state
    side = moveStack[moveStack.length - 1].side;
    enpassant = moveStack[moveStack.length - 1].enpassant;
    castle = moveStack[moveStack.length - 1].castle;
    fifty = moveStack[moveStack.length - 1].fifty;
    hashKey = moveStack[moveStack.length - 1].hashKey;
    moveStack.pop();
  }

Please note that I do take care about hashing side and enpassant square if it's not equal to no square
but for some reason hash keys are getting malformed after null move pruning.
If I comment out null move pruning code hash keys are correct again.

How can I debug my hash keys within null move pruning?
I just can't realize which parameter wasn't XORed with hash keys,
can I somehow manually reproduce wrong hashes without running search to figure out what's going wrong?

[op12no2]

That would probably be a lot faster than messing with JavaScript objects containing a variety of types as fields. And also more memory efficient.

Agree, (that's what Lozza does). Maksim, if you use typed arrays you know exactly what is happening and they are very fast. Using objects in this context 'feels' slow

[hgm]

Code: Select all

    hashKey = moveStack[moveStack.length - 1].hashKey;

Wouldn't this have to be .hash, rather than .hashKey?

BTW, using side ^= 1; also in TakeMove() seems faster than saving and restoring the old value. Same for hashKey ^= sideKey.

If you use only a 32-bit key, from which you derive both the index and teh signature, I am afraid this is not enough. A TT would be pretty useless if it doesn't have at least a million entries, and more likely you use something like 2^24. That would mean your signature is effectively only 8 bits, and every hash probe has a 1-in-256 chance to return the score of a completely unrelated position without the engine detecting it. This could very well be the reason for the Elo regression.

In micro-Max I keep two 32-bit hash keys. One is used to derive the index from (by simple masking), the other to store in the entry as signature. That way all stored key bits are significant (i.e. not implied by the index). So I only have a 1-in-4-billion chance to get a wrong score (of an unrelated position) on a hash probe.

Some keys, such as sideKey, you can have act only on one of the two hash keys, to simplify key update. Some engines use 1 for the sideKey anyway, to guarantee that a cache hit on the hash probe after null move (which would then map to the adjacent entry).

[op12no2]

can I somehow manually reproduce wrong hashes without running search to figure out what's going wrong?

I'm not sure I totally follow your code, but, if your hash reflects the current player when you get to nmp, I think you need to tweak ep and the player turn, since you are going to search with the other player, then put them both back after nmp. My code:-

Code: Select all

  
  board.loHash ^= board.loEP[board.ep];
  board.hiHash ^= board.hiEP[board.ep];

  board.ep = 0; // what else?

  board.loHash ^= board.loEP[board.ep];
  board.hiHash ^= board.hiEP[board.ep];

  board.loHash ^= board.loTurn;
  board.hiHash ^= board.hiTurn;

  score = -this.alphabeta(node.childNode, depth-R-1, nextTurn, -beta, -beta+1, NULL_N, INCHECK_UNKNOWN);

  node.uncache(); // restore the board hash

[maksimKorzh]

can I somehow manually reproduce wrong hashes without running search to figure out what's going wrong?

I'm not sure I totally follow your code, but, if your hash reflects the current player when you get to nmp, I think you need to tweak ep and the player turn, since you are going to search with the other player, then put them both back after nmp. My code:-

Code: Select all

  
  board.loHash ^= board.loEP[board.ep];
  board.hiHash ^= board.hiEP[board.ep];

  board.ep = 0; // what else?

  board.loHash ^= board.loEP[board.ep];
  board.hiHash ^= board.hiEP[board.ep];

  board.loHash ^= board.loTurn;
  board.hiHash ^= board.hiTurn;

  score = -this.alphabeta(node.childNode, depth-R-1, nextTurn, -beta, -beta+1, NULL_N, INCHECK_UNKNOWN);

  node.uncache(); // restore the hash

At very least I just found a way to make hash keys being correct:
instead of pushing null moves to stack I just preserve/restore side, fifty, ep and hash and then restore them back
after nill move recursive call:

Code: Select all

if (nullMove) {
        // null move pruning
        if ( searchPly && depth > 2 && staticEval >= beta) {
          // preserve board state variables
          let oldSide = side;
          let oldEnpassant = enpassant;
          let oldCastle = castle;
          let oldFifty = fifty;
          let oldHash = hashKey;
          
          if (enpassant != noEnpassant) hashKey ^= pieceKeys[enpassant];
          enpassant = noEnpassant;
          fifty = 0;
          side ^= 1;
          hashKey ^= sideKey;

          score = -negamax(-beta, -beta + 1, depth - 1 - 2, NO_NULL);
          
          // restore board state
          side = oldSide;
          enpassant = oldEnpassant;
          castle = oldCastle;
          fifty = oldFifty;
          hashKey = oldHash;
          
          if (timing.stopped == 1) return 0;
          if (score >= beta) return beta;
        }
        ...
}

At very least it doesn't give any wrong hash keys anymore, so I'm now running a match TT vs noTT again to see if the
situation is going to change now.

[hgm]

It is a bad idea to update the key incrementally for e.p. rights and side to move anyway. Incremental update only makes sense for pesistent features. Most pieces stay on the same square for a long time, because you can only move one at the time. So there it makes sense. Side to move will change every turn, and e.p. rights evaporate after one turn. If you include those in the incremental key, you have to first apply them, and then again undo them for the next move, effectively duplicating the work.

So I use incremental update only for the board key. The total key is than calculated in every node by XORing the sideKey and applicable e.p. key with that incremental key. Then I don't have to undo it on TakeMove().

[maksimKorzh]

I've found a trivial bug in my takeNullMove()...
just returned wrong key from move stack hence hashKey was undefined after null move pruning... weird
Now with a fix it has started playing MUCH better.
Thanks for your support.
I still have lot's of questions but at very least current implementation seems at least
not doing something horribly wrong (I hope)

To HGM:
I got your concept generally but I will go insane if try to implement it now...
Maybe in future, I need first to name the variables correctly)

[Dann Corbit]

Your approach is a good approach.
First make it correct, and only after it works correctly, you can make it faster.
In order to make it faster, you should always profile first.
After the profile you will have discovered the slow spots.
The best way to speed it up is to choose a better algorithm.

But early in development correctness is absolutely crucial.
If you try to make an incorrect program fast you will just get wrong answers quicker