Explaining heuristics with computer science, graph theory.

[zulban]

Hello. I'm working on a smartphone interface and AI (now playable!) which allows the player to make custom board shapes and sizes, and pieces with custom move rules, then play against an AI.

I am finding that in order to generalise a lot of chess AI heuristics and optimisations, I need to express our ideas in more general computer science terms, especially graph theory terms. Here are some examples of CS terms.

https://i.imgur.com/rjYXjfu.png

1) In this board, a bishop is probably worth a lot more than a rook. Maybe this is because the "graph diameter" or perhaps the "average path length" for a bishop is much less than for a rook.

2) In classic chess, the piece square table for queens and rooks end game is sometimes not used. Perhaps this is because "average path length" is so consistently low/the same on any tile.

3) Classic chess is a "disconnected graph" for bishops. Meaning you can have two bishops which can never touch.

4) If a tile is removed and it impacts "graph connectivity", those tiles are probably worth more. For example, the centre tiles in this board are likely worth a lot more:

https://i.imgur.com/Ax8xTvJ.png

Moving beyond classic chess pieces: imagine an overly complicated piece which can slide forward like a bishop, retreat backward like a rook up to 4 squares, capture like a rook sideways, and jump to the left like a knight. Implementing AI on pieces like this makes graph theory even more necessary.

Does anyone have any thoughts or links to resources that discuss chess in these more general terms? Note: np-hard isn't a problem since things can be pre-computed on the smartphone or approximated. I need features, not perfection.

Here are some typical chess tips I am having trouble converting into more general terms:

1) Pawn structure. What is it about pawn moves compared to other pieces that makes this important? What impact would it have if pawns could move backward?
2) Bishop pair.
3) Control the centre. Why? Is it just to maximise your mobility, and minimise opponent mobility?
4) King mating patterns. Given a custom board and custom pieces, where do we want to draw the enemy king? At what point in the game?
5) Using a queen too early. Why is this generally bad in terms of how queens move compared to other pieces?

Thanks in advance for any discussion! This is a cool forum.

[Evert]

1) Pawn structure. What is it about pawn moves compared to other pieces that makes this important? What impact would it have if pawns could move backward?

If pawns could move backward, you lose the concept of backward pawns, which seems like a big deal.
The importance of pawn structure comes not only from the irreversible moves, but also from the divergence between captures and regular moves. It's hard to generalise though, when you consider having to deal with Shatranj pawns, Berolina pawns and Shogi pawns, to name but a few.
Sjaak II has some generalised pawn structure terms, but I'm quite sure those mostly apply to regular chess pawns (and perform poorly in Shogi, where pawn structure is less of a concern).

2) Bishop pair.

I award a 15% (I think) bonus of the base value to a pair of colour-bound pieces (45cp for a Bishop, 17cp for a Ferz). It makes sense to link the size of the bonus to the base value, and then linearly is the obvious thing to do first.
Note that something like an Alfil suffers from a higher order "colour" binding, which may warrant a different bonus to "first order" colour binding. Such pieces are sufficiently worthless that it's not such a big deal though.

3) Control the centre. Why? Is it just to maximise your mobility, and minimise opponent mobility?

Also the ability to switch targets (offensive and defensive) more quickly. Which is sortof implied if you score mobility for the wings and centre with different weights.

4) King mating patterns. Given a custom board and custom pieces, where do we want to draw the enemy king? At what point in the game?

Probably where it has few moves (in a corner, in 99% of cases). The tipping point can be determined by considering the strength of the opposing army. Sjaak II's method for calculating attack weights works ok for calculating "game phase", at least for fairly normal boards.

5) Using a queen too early. Why is this generally bad in terms of how queens move compared to other pieces?

A queen alone cannot carry an attack, and is a vulnerable target for minor pieces. Note this has nothing to do with how it moves!
Some sort of progressive scoring for attacks (it's worth more to attack a single target with many pieces than to attack a lot of targets with a queen) should help, but it's a notoriously difficult problem. It's why strong programs still rely on opening books (Stockfish and Komodo might do better at this now).

[hgm]

1) Pawn structure. What is it about pawn moves compared to other pieces that makes this important? What impact would it have if pawns could move backward?
2) Bishop pair.
3) Control the centre. Why? Is it just to maximise your mobility, and minimise opponent mobility?
4) King mating patterns. Given a custom board and custom pieces, where do we want to draw the enemy king? At what point in the game?
5) Using a queen too early. Why is this generally bad in terms of how queens move compared to other pieces?

1) That Pawns are rather immobile. So they tend to be (or become) rather persistent features. Having a Knight in a poor spot is also bad, but can be undone in one or two moves. With a poor Pawn structure you can be stuck for the rest of the game.
2) It seems to be bad if you are not able to direct the same amount of force against every square on the board. Probably because the opponent would then wage battle mainly on the squares where you are weak. It would be interesting to determine how two independent forms of color binding interact. E.g. pieces that can only be on odd/even squares or odd/even ranks. (In Betza notation: vRsDD and sRvDD.)
3) From the center you can either directly attack two widely separated spots of the opponent (Bishops), or be a few moves away from attacking both spots without having to commit to one of them. When you can switch your attack faster than the opponent can switch his defense, you can create a local majority.
4) For mating a bare King, you better generate end-game tables.
5) Early development of the Queen is bad because the Queen is very valuable. That is only indirectly related to how it moves. The opponent will be able to chase it while devloping his own minors. This would also hold for Rooks, but it is in general impossible to bring these out quickly anyway, as the initial position traps them behind Pawns. But in general you don't want to expose valuable pieces, but hide them behind less valuable pieces.

[zulban]

irreversible moves

Interesting point... maybe I should also try a directed graph. For pawns this would show tiles that are not part of any cycles. You can leave the tile but not return. This would also apply to a rook-like piece which cannot move left, etc. Not totally sure yet how this interacts with other graph features... but we're getting there :o

I guess pieces are worth less if they are farther down an irreversible directed graph. In classic chess this is offset by pawns simultaneously increasing in value because of promotions.

[zulban]

4) For mating a bare King, you better generate end-game tables.

If you mean this:

https://chessprogramming.wikispaces.com ... Tablebases

I cannot do this. This is part of what makes my problem interesting. A player can create their own set of pieces on a custom board and immediately play it. Several seconds of pre-computation before starting a new game for the first time is acceptable from a user experience perspective, but not much more than that.

My goal is not to destroy other AIs dedicated to classic chess, but to generally beat amateur players in interesting boards they just designed. Next I'm going to try improving my evaluation function by leading the king(s) towards tiles that limit their movement. This should raise the probability that a search could lead towards a mate. This may involve using directed graphs if the king moves more like a pawn. I think this will weigh more near end game with material imbalances.

5) Early development of the Queen is bad because the Queen is very valuable. That is only indirectly related to how it moves. The opponent will be able to chase it while developing his own minors. This would also hold for Rooks, but it is in general impossible to bring these out quickly anyway, as the initial position traps them behind Pawns. But in general you don't want to expose valuable pieces, but hide them behind less valuable pieces.

I have always thought that chess is an extraordinarily well designed game. The idea of "development" for example is hard to balance right in new chess variant designs. In classic chess, early use of the queen is bad because minor pieces can develop with tempo... but in other configurations I can imagine the queen badgering the opponent into "developing" in a bad way. Maybe.

Definitely not sure where to go on that last point. For now "early queen development" is not a feature that I can fit into my system.

[zulban]

To add to what I just wrote, "looking for an alternative to end-game tables" is a good way to phrase my problem. Specifically lighter on computation so a smartphone can do at least something in a few seconds.

[hgm]

I cannot do this. This is part of what makes my problem interesting. A player can create their own set of pieces on a custom board and immediately play it. Several seconds of pre-computation before starting a new game for the first time is acceptable from a user experience perspective, but not much more than that.

It takes less than 100 msec to compute an EGT for a 4-men end-game like KBNK on an 8x8 board, on a PC.

[zulban]

Sure, but when you multiply that up to apply to my problem, it would take much longer than a few seconds.

1) This must run on a smartphone, not a PC.
2) Because my board rules and piece rules are very general, even if I perfectly optimise my code, it's going to be a lot slower than dedicated classic chess code.
3) My game handles up to 16x16, though the editor recommends you disable more tiles if you make a board that big.
4) KBNK is just one of many, many relevant EGTs.

I'd love to do EGTs but I'm pretty darn sure it's totally infeasible given these restrictions. Compromises like "in end game, get the king to places where it has less moves" feel like they'll be effective (which I've just implemented). I could easily use more ideas like that.

Something that is technically possible (but not a priority to implement right now) could be computing an EGT specific to the current game being played, while the human is pondering their turn. I think there's a lot of work elsewhere I'd do before that is worth it tho.

[hgm]

Sure, but when you multiply that up to apply to my problem, it would take much longer than a few seconds.

Why? When the AI is playing a game, it knows long before the end on which combination of pieces its mating potential depends.

1) This must run on a smartphone, not a PC.

A smartphone will be slower than a PV, no doubt. I have no experience with that. But even if it is 100 times slower, 100 msec becomes 10 sec, which still seems an affordable thinking time, considering that from that point on it can play instantly.

The point is that you don't have to include very general heuristics for where to drive a bare King. Once you bared the King, and you have no pieces to promote, you simply generate the EGT for Kings + your best piece (3 men), and if that is a draw, Kings + your 2 best pieces, to figure out in which spots of the board checkmates can be forced, and then either play from that EGT (if you have no other pieces) or create a PST for the bare King that penalize him (heavily) for being closer to those spots.

Orthodox Chess engines that do not know you can only force checkmate in KBNK in the corner of the Bishop shade in general will not be able to win this end-game. If you end up with a Phoenix (WA) and a Mortar (AG) on a square board, (and orthodox Kings), it would be hard to predict from heuristics that you can only checkmate in the corners of the color opposite to that of the Mortar. With asymmetric pieces you can even be limited to some corners on a square board in a 3-men end-game.

2) Because my board rules and piece rules are very general, even if I perfectly optimise my code, it's going to be a lot slower than dedicated classic chess code.
3) My game handles up to 16x16, though the editor recommends you disable more tiles if you make a board that big.
4) KBNK is just one of many, many relevant EGTs.

Even on 16x16 boards a symmetry-less 3-men end-game only has 16M positions, the same as a 4-men on 8x8, and should thus require similar times for EGT generation (i.e. sub-second). So it doesn't seem undoable to generate all 3-men end-game for all of the participating pieces during the game. So that at least when you reach a late-end-game position you know which pieces have mating potential, and which haven't.

I'd love to do EGTs but I'm pretty darn sure it's totally infeasible given these restrictions. Compromises like "in end game, get the king to places where it has less moves" feel like they'll be effective (which I've just implemented). I could easily use more ideas like that.

Would fail miserably for KBNK.

Something that is technically possible (but not a priority to implement right now) could be computing an EGT specific to the current game being played, while the human is pondering their turn.

Yes, of course. That is what I mean.

[Evert]

Interesting point... maybe I should also try a directed graph. For pawns this would show tiles that are not part of any cycles. You can leave the tile but not return. This would also apply to a rook-like piece which cannot move left, etc. Not totally sure yet how this interacts with other graph features... but we're getting there

Like a Lance?
In SjaakII I determine whether pieces can return to where they came from by any sequence of moves. I think I also keep track of the parity of pieces (whether they can make tempo moves).

I guess pieces are worth less if they are farther down an irreversible directed graph. In classic chess this is offset by pawns simultaneously increasing in value because of promotions.

I don't know how strong this effect is. I suspect it only applies close to where it loses the extra move. In Xiangqi, pawns lose a move on the last rank, but they don't drop in value on reaching the penultimate rank.