SEE Map

[matthewlai]

We usually think of SEE as something we compute for moves, but it's also possible to think of it as a property of squares.

We can simply assume the square is empty (if there's a piece, remove it first), then do SEE on that empty square from both sides (first "capture" forced).

For example, in this position -
[d]7k/8/8/2p5/8/8/3RN3/7K w - - 0 1

If we use Q=9,R=5,B=3,N=3,P=1...

The square d4 would have a white SEE score of -2 (Nxd4, cxd4, Rxd4). It would have a black SEE score of -1 (cxd4, Nxd4).

If we do this for every square (128 SEE calls in total), we get 2 maps of SEE values.

What do these values mean? They are the biggest pieces the opponent can put in that square without expecting to lose material.

Using the example above, if black puts a hypothetical piece of value 2 on d4, it would neither lose or gain material. If black puts a knight (value 3) on d4, she is probably going to lose equivalent of 1 pawn.

Similarly, if white puts a pawn at d4, she is expected to break even. If she puts a hypothetical piece of value 2 or knight/bishop, she is expected to lose material.

These maps are essentially maps of square control. For both sides, closer to 0 means more control on the square, and more negative means less control. Note that the values can never be positive (the opponent's response is not forced, so this capturing of empty square cannot possibly win material if the square was indeed empty).

It's not immediately clear to me how these maps can be used, and fortunately for me I don't have to think about it too much, since my engine is based on machine learning, and I'll just have it figure out what to do with these values by itself. That said, I think it's clear that there's a lot of information in these maps.

One possible way to use this is for filtering out moves to count for mobility. In Stockfish for example (at least last time I checked), mobility excludes squares attacked by pieces of lower value. It is obviously more correct to also not count squares attacked by pieces of higher value, if we cannot capture those pieces back.

Computing these maps are very expensive, so it may not be worthwhile for fast engines. However, if you are trying to make a slow engine with very good eval, I think this is worth a try.

Has anyone tried something like this?

[sje]

This idea was covered in the paper Plans, Goals, and Search Strategies for the Selection of a Move in Chess by Church and Church which appeared in the 1978 edition of Chess Skill in Man and Machine.

The described program, which essentially performs a single ply search, has many 8x8 maps generated by different semantics including those for Safety and Power.

[matthewlai]

This idea was covered in the paper Plans, Goals, and Search Strategies for the Selection of a Move in Chess by Church and Church which appeared in the 1978 edition of Chess Skill in Man and Machine.

The described program, which essentially performs a single ply search, has many 8x8 maps generated by different semantics including those for Safety and Power.

That's good to know. At least that means I'm not completely crazy . Do you know if there have been more modern attempts?

[matthewlai]

I added it to my engine, and my STS score went from 6500/15000 to 6800/15000 in a few hours of learning and it's still going up. So this knowledge obviously helps quite a lot.

I have no idea how it's being used though .

[mvk]

Has anyone tried something like this?

My board control does approximately that. One thing to contemplate is the origin of the piece you hypothetically put on that square. Pieces can't fall out of the blue sky, and the safety of a non-existing piece has little meaning. Existing pieces come from your list of defenders, and, unless it is a pawn, once it is on the square there is one less defender for your SEE. Pieces can't defend themselves after all. And that then suddenly sounds a lot like computing the SEE during move generation, except you do it for both sides.

[matthewlai]

Has anyone tried something like this?

My board control does approximately that. One thing to contemplate is the origin of the piece you hypothetically put on that square. Pieces can't fall out of the blue sky, and the safety of a non-existing piece has little meaning. Existing pieces come from your list of defenders, and, unless it is a pawn, once it is on the square there is one less defender for your SEE. Pieces can't defend themselves after all. And that then suddenly sounds a lot like computing the SEE during move generation, except you do it for both sides.

Indeed. Pieces can't fall out of the sky.

What I am aiming for is more global and long term knowledge.

For example, my program can figure out that if the opponent has good control of many dark squares, our dark bishop is worth less, even if he happens to be on a square right now with good mobility.

Or things like if the opponent has good control of many squares around our king, our king is in trouble.

Or maybe things like extended mobility - where can the knight go in 2 moves.

Or things like if the opponent has good control across the board in a line, the position is more likely to be draw. This one, in particular, can't be done during move generation. There may not be a piece that can actually move to that square in this move, but the pattern of control would still signal drawishness.

Also, the idea is that the value of the hypothetical piece is a maximum. If we can't put a knight somewhere without losing material, we also can't put a rook there, or a queen there. In a way that makes this a little more general.

How is your board control implemented, if you don't mind sharing?

[stegemma]

I added it to my engine, and my STS score went from 6500/15000 to 6800/15000 in a few hours of learning and it's still going up. So this knowledge obviously helps quite a lot.

I have no idea how it's being used though .

I think that this is because you are not adding knowledge but you are adding an algorithm pre-solved. Suppose to add a full stockfish search and then give to your neural network its output...

[matthewlai]

I added it to my engine, and my STS score went from 6500/15000 to 6800/15000 in a few hours of learning and it's still going up. So this knowledge obviously helps quite a lot.

I have no idea how it's being used though .

I think that this is because you are not adding knowledge but you are adding an algorithm pre-solved. Suppose to add a full stockfish search and then give to your neural network its output...

Indeed. There's a fine line between feature representation and feature extraction.

When humans look at positions, we first derive very low level features from raw inputs, then gradually build them up into high level conceptual ideas. This applies not only to chess, but to many other problems as well.

When we do machine learning, we always have to decide where to draw the line - where to hand control over to the learned system.

Modern machine learning models are still nowhere near as good as humans, so in most cases, it's simply not practical to just hand it the raw input (in this case that could be 64 integers, plus a few bits for side to move, etc).

Where to draw the line is hard to decide. On one hand, if we draw the line too low, the model won't be smart enough to figure out useful patterns. On the other hand, if we draw the line too high, we are forcing the model into human constraints and stopping it from exploring other ideas.

For example, there is no reason why the mobility of sliding pieces in each direction needs to be encoded at all. The model can theoretically figure out the rules of chess from the positions, and learn to compute mobility. However, it would use up a lot of the model's modelling capacity, because I know it's very hard for a neural network to compute that kind of knowledge given my board representation. I also know that the knowledge will very probably be useful. So I provide them to the model as parts of the input.

I believe (and this is most certainly debatable) SEE maps are in the same category. They are quite low level, fairly mechanical to compute, hard to learn (given my feature representation), and most probably useful.

There is still almost unlimited flexibility in how the model can make use of control maps (I can think of many off the top of my head), and it's clearly smart enough to make use of it. I'd say I have accomplished the goal of drawing the line at the right level in this case.

[mvk]

How is your board control implemented, if you don't mind sharing?

In pseudo code, something along these lines:

Code: Select all

int whiteAttacks[64], blackAttacks[64] # 15 bits per square, updated in makeMove (see Ref1)
int guard&#91;1<<15&#93; # reduces 15 bits into a single strength/guard value. Very high when there are pawns, lower when only pieces, etc
int squareType&#91;64&#93;&#91;2&#93;&#91;2&#93; # distuingish center, extended center, on which side the kings are, etc
int table&#91;&#93;&#91;&#93;&#91;&#93;

def evaluateStage3&#40;)&#58;
  whiteKingSide = whiteKingSquare in &#91;e1..h8&#93; # 1 bit
  blackKingSide = blackKingSquare in &#91;e1..h8&#93; # 1 bit
  score = 0
  for square in range&#40;64&#41;&#58;
    whiteGuard = guard&#91;whiteAttacks&#91;square&#93;&#93;
    blackGuard = guard&#91;blackAttacks&#91;square&#93;&#93;
    type = squareType&#91;square&#93;&#91;whiteKingSide&#93;&#91;blackKingSide&#93;
    score += table&#91;type&#93;&#91;whiteGuard&#93;&#91;blackGuard&#93;
  return score

The attack bits know about knights, pawns, kings, and slider directions (15 bits per side per square). I currently have code to factor in a 16th bit per square, maintained in separate variables, which signals the presence of a bishop on the same diagonal, but that information is not used (yet), and that is a bit of a kludge anyway. The table[][][] implements a simplified form of SEE, but based on a kind of "guard heuristic" instead of a more precise swap-off. The idea is that you can get away with that because errors don't matter too much when you combine all squares into one number anyway. The guard heuristic is described in [Ref2], but for move ordering in Chinese chess there, not for specifically for evaluation.

Ref1: See also side 16 here.

Ref2: Ke, Y.-F. and Parng, T.-M. (June 1993). The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning. ICCA Journal, Vol. 16, No. 2, p76-85.

[matthewlai]

How is your board control implemented, if you don't mind sharing?

In pseudo code, something along these lines:

Code: Select all

int whiteAttacks[64], blackAttacks[64] # 15 bits per square, updated in makeMove (see Ref1)
int guard&#91;1<<15&#93; # reduces 15 bits into a single strength/guard value. Very high when there are pawns, lower when only pieces, etc
int squareType&#91;64&#93;&#91;2&#93;&#91;2&#93; # distuingish center, extended center, on which side the kings are, etc
int table&#91;&#93;&#91;&#93;&#91;&#93;

def evaluateStage3&#40;)&#58;
  whiteKingSide = whiteKingSquare in &#91;e1..h8&#93; # 1 bit
  blackKingSide = blackKingSquare in &#91;e1..h8&#93; # 1 bit
  score = 0
  for square in range&#40;64&#41;&#58;
    whiteGuard = guard&#91;whiteAttacks&#91;square&#93;&#93;
    blackGuard = guard&#91;blackAttacks&#91;square&#93;&#93;
    type = squareType&#91;square&#93;&#91;whiteKingSide&#93;&#91;blackKingSide&#93;
    score += table&#91;type&#93;&#91;whiteGuard&#93;&#91;blackGuard&#93;
  return score

The attack bits know about knights, pawns, kings, and slider directions (15 bits per side per square). I currently have code to factor in a 16th bit per square, maintained in separate variables, which signals the presence of a bishop on the same diagonal, but that information is not used (yet), and that is a bit of a kludge anyway. The table[][][] implements a simplified form of SEE, but based on a kind of "guard heuristic" instead of a more precise swap-off. The idea is that you can get away with that because errors don't matter too much when you combine all squares into one number anyway. The guard heuristic is described in [Ref2], but for move ordering in Chinese chess there, not for specifically for evaluation.

Ref1: See also side 16 here.

Ref2: Ke, Y.-F. and Parng, T.-M. (June 1993). The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning. ICCA Journal, Vol. 16, No. 2, p76-85.

Ah! That's almost exactly what I planned to do initially. Then I decided that I may as well just do full SEE since my engine spends 99% of its time in neural net evaluation anyways (it's at about 40000 nps right now).