SEE Map

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
matthewlai
Posts: 736
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

SEE Map

Post by matthewlai » Mon Jul 20, 2015 4:53 pm

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?
Author of Giraffe, an engine based on deep reinforcement learning. https://bitbucket.org/waterreaction/giraffe/overview

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: SEE Map

Post by sje » Mon Jul 20, 2015 6:24 pm

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
Posts: 736
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Re: SEE Map

Post by matthewlai » Mon Jul 20, 2015 6:41 pm

sje wrote: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 :D. Do you know if there have been more modern attempts?
Author of Giraffe, an engine based on deep reinforcement learning. https://bitbucket.org/waterreaction/giraffe/overview

matthewlai
Posts: 736
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Re: SEE Map

Post by matthewlai » Mon Jul 20, 2015 10:12 pm

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 :D.
Author of Giraffe, an engine based on deep reinforcement learning. https://bitbucket.org/waterreaction/giraffe/overview

mvk
Posts: 589
Joined: Tue Jun 04, 2013 8:15 pm

Re: SEE Map

Post by mvk » Tue Jul 21, 2015 7:59 pm

matthewlai wrote: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.
[Account deleted]

matthewlai
Posts: 736
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Re: SEE Map

Post by matthewlai » Tue Jul 21, 2015 8:18 pm

mvk wrote:
matthewlai wrote: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?
Author of Giraffe, an engine based on deep reinforcement learning. https://bitbucket.org/waterreaction/giraffe/overview

User avatar
stegemma
Posts: 851
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: SEE Map

Post by stegemma » Tue Jul 21, 2015 9:56 pm

matthewlai wrote: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 :D.
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...
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

matthewlai
Posts: 736
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Re: SEE Map

Post by matthewlai » Tue Jul 21, 2015 10:08 pm

stegemma wrote:
matthewlai wrote: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 :D.
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.
Author of Giraffe, an engine based on deep reinforcement learning. https://bitbucket.org/waterreaction/giraffe/overview

mvk
Posts: 589
Joined: Tue Jun 04, 2013 8:15 pm

Re: SEE Map

Post by mvk » Tue Jul 21, 2015 11:22 pm

matthewlai wrote: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.
[Account deleted]

matthewlai
Posts: 736
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Re: SEE Map

Post by matthewlai » Wed Jul 22, 2015 1:32 am

mvk wrote:
matthewlai wrote:How is your board control implemented, if you don't mind sharing?
In pseudo code, something along these lines:

Code: Select all

int whiteAttacks&#91;64&#93;, blackAttacks&#91;64&#93; # 15 bits per square, updated in makeMove &#40;see Ref1&#41;
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).
Author of Giraffe, an engine based on deep reinforcement learning. https://bitbucket.org/waterreaction/giraffe/overview

Post Reply