Pawn Pattern Matching

[Gerd Isenberg]

Assume we have an array of black:white pawn sets, like mentioned in the chess wiki:
http://en.wikipedia.org/wiki/Pawn_structure

I am thinking about an algorithm to look which pattern matches most closely the current pawn structure. For instance to use pawn-structure as an index for piece-square tables or weight-vectors for attack-set dot-products or to determine strategical targets. One may use xor to look, which bit(s) differ, if any. My question is - if no equal match occurd - which is the closest - if we like to consider center structure and less importantly possible wing issues.

Does anybody has experience and hints for this pattern matching stuff?

Thanks,
Gerd

[CThinker]

My recollection is that older versions of crafty has code to detect stonewall formations. Recent versions don't have it anymore. Perhaps it was not effective?

[Dann Corbit]

My recollection is that older versions of crafty has code to detect stonewall formations. Recent versions don't have it anymore. Perhaps it was not effective?

Crafty (up to version 20) had wall formation detection, as designed by Jeremiah Pennery. Look at how fast Crafty sees the wall here:

[d]2b5/1r6/2kBp1p1/p2pP1P1/2pP4/1pP3K1/1R3P2/8 b - - bm Rb4; id "WAC.230";

Code: Select all

C:\programme\winboard\crafty>craftydd
EPD Kit revision date: 1996.04.21
found computer opening book file [./bookc.bin].
hash table memory =  192M bytes.
pawn hash table memory =    6M bytes.
EGTB cache memory =   32M bytes.
draw score set to    0.00 pawns.
choose from book moves randomly (using weights.)
choose from 5 best moves.
book learning enabled
result learning enabled
position learning enabled
resign after 5 consecutive moves with score < -9.
5 piece tablebase files found
13980kb of RAM used for TB indices and decompression tables

Crafty v20.0

White(1): epdpfga e:\wac230.epd wac230.out
PFGA: EPD record: 1   ID: WAC.230
              time surplus   0.00  time limit 275179:21 (275179:21)
              depth   time  score   variation (1)
               11     0.75  -1.74   1. ... Rh7 2. Rb1 Kb5 3. Ba3 Rf7 4.
                                    Rb2 Rf5 5. Kg4 Ka4 6. Bc5 Kb5 <HT>
               11->   0.78  -1.74   1. ... Rh7 2. Rb1 Kb5 3. Ba3 Rf7 4.
                                    Rb2 Rf5 5. Kg4 Ka4 6. Bc5 Kb5 <HT>
               12     0.90     +1   1. ... Rh7
               12     1.11   0.00   1. ... Rh7 2. Rb1 Kb5 3. Ba3 Rf7 4.
                                    Ra1 Ka4 5. Bb2+ Kb5 6. Ba3
               12     1.92  -1.70   1. ... Rb4 2. cxb4 a4 3. Rb1 c3 4.
                                    Rc1 b2 5. Rxc3+ Kd7 6. Rc7+ Kd8 7.
                                    Ra7 b1=Q 8. Rxa4
               12->   2.01  -1.70   1. ... Rb4 2. cxb4 a4 3. Rb1 c3 4.
                                    Rc1 b2 5. Rxc3+ Kd7 6. Rc7+ Kd8 7.
                                    Ra7 b1=Q 8. Rxa4
               13     3.03     -1   1. ... Rb4!!
               13     3.78  -2.23   1. ... Rb4 2. cxb4 a4 3. b5+ Kxb5 4.
                                    Rb1 c3 5. Rc1 Kc4 6. Ra1 Bd7 7. Bc5
                                    Kd3 8. Rd1+ Kc2
               13->   4.23  -2.23   1. ... Rb4 2. cxb4 a4 3. b5+ Kxb5 4.
                                    Rb1 c3 5. Rc1 Kc4 6. Ra1 Bd7 7. Bc5
                                    Kd3 8. Rd1+ Kc2
               14     5.00     +1   1. ... Rb4
               14     6.53  -1.67   1. ... Rb4 2. cxb4 a4 3. Rb1 Kb5 4.
                                    Ra1 c3 5. Rc1 c2 6. f4 a3 7. f5 b2
                                    8. Rxc2 b1=Q 9. Rxc8 Qxf5
               14->   8.43  -1.67   1. ... Rb4 2. cxb4 a4 3. Rb1 Kb5 4.
                                    Ra1 c3 5. Rc1 c2 6. f4 a3 7. f5 b2
                                    8. Rxc2 b1=Q 9. Rxc8 Qxf5
               15    11.00     -1   1. ... Rb4!!
               15    14.06  -2.32   1. ... Rb4 2. cxb4 a4 3. b5+ Kxb5 4.
                                    Rc2 bxc2 5. Ba3 c3 6. Kf4 Kc4 7. Ke3
                                    c1=Q+ 8. Bxc1 Kb3 9. Kf4 a3
               15->  16.61  -2.32   1. ... Rb4 2. cxb4 a4 3. b5+ Kxb5 4.
                                    Rc2 bxc2 5. Ba3 c3 6. Kf4 Kc4 7. Ke3
                                    c1=Q+ 8. Bxc1 Kb3 9. Kf4 a3
               16    21.43  -2.27   1. ... Rb4 2. cxb4 a4 3. b5+ Kxb5 4.
                                    Rc2 bxc2 5. Ba3 c3 6. Kf4 Kc4 7. Ke3
                                    c1=Q+ 8. Bxc1 Kb3 9. Kf4 a3 10. Be3
               16->  28.70  -2.27   1. ... Rb4 2. cxb4 a4 3. b5+ Kxb5 4.
                                    Rc2 bxc2 5. Ba3 c3 6. Kf4 Kc4 7. Ke3
                                    c1=Q+ 8. Bxc1 Kb3 9. Kf4 a3 10. Be3
               17    41.18  -2.34   1. ... Rb4 2. cxb4 a4 3. b5+ Kxb5 4.
                                    Rc2 bxc2 5. Ba3 c3 6. Kf4 Kc4 7. Ke3
                                    c1=Q+ 8. Bxc1 Kb3 9. Kf4 a3 10. Be3
                                    Bd7
               17->  51.95  -2.34   1. ... Rb4 2. cxb4 a4 3. b5+ Kxb5 4.
                                    Rc2 bxc2 5. Ba3 c3 6. Kf4 Kc4 7. Ke3
                                    c1=Q+ 8. Bxc1 Kb3 9. Kf4 a3 10. Be3
                                    Bd7
               18     2:36  -2.47   1. ... Rb4 2. Rb1 Ra4 3. Rc1 Ra2 4.
                                    Kf3 Bd7 5. Ke3 a4 6. Bb4 Bc8 7. Bd6
                                    <HT>
quit           18     2:36   2/16*  1. ... Rf7
Black(0): quit

A very simple way to see if you have a strong pawn formation is to attack your own pawns with the pawns of the same color. If you have nice long pawn chains, then each pawn will attack(actually defend) one or more of his siblings most of the time. It is an extremely cheap operation if you use bitboards (two shifts and an and operation per side).

[Harald Johnsen]

One may use xor to look, which bit(s) differ, if any. My question is - if no equal match occurd - which is the closest - if we like to consider center structure and less importantly possible wing issues.

Does anybody has experience and hints for this pattern matching stuff?

Thanks,
Gerd

I've not tried yet because of the lack of time.
1) only use exact match of pattern ie : (pattern & pawn_structure) == pattern, pawns outside of the pattern are then handled like 'don't care'
2) sort your patterns by lenght and compares the longests first, you can now compare very specialized patterns first and more generics later
3) store the patterns in a map or any binary tree so that there is no sequential search (still a few probes needed of course)

HJ.

[Gerd Isenberg]

I've not tried yet because of the lack of time.
1) only use exact match of pattern ie : (pattern & pawn_structure) == pattern, pawns outside of the pattern are then handled like 'don't care'
2) sort your patterns by lenght and compares the longests first, you can now compare very specialized patterns first and more generics later
3) store the patterns in a map or any binary tree so that there is no sequential search (still a few probes needed of course)

HJ.

Good points. I think rather than to compare bitboards or their relative complements, to match the a preinitialized bitboard-database with the less important "don't care" bits - it probably makes sense to look for distinct pattern, like rams, chains and wedges with top and base-pawns, lever-breaks, backward, isolated, candidates and even passers if we enter the later middle- or even the endgame. One may also differentiate and weight by areas, like center-files, extented center files and wings.

• 1 The Caro formation
  2 The Slav formation
  3 The Sicilian - Scheveningen
  4 The Sicilian - Dragon
  5 The Sicilian - Maróczy bind
  6 The Sicilian - Boleslavsky hole
  7 The d5 chain
  8 The e5 chain
  9 The King's Indian - Rauzer formation
  10 The King's Indian - Boleslavsky Wall
  11 The Queen's Gambit - Isolani
  12 The Queen's Gambit - Hanging Pawns
  13 The Queen's Gambit - Orthodox Exchange
  14 The Panov formation
  15 The Stonewall formation
  16 The Closed Sicilian formation

Due to pawn hashing, to determine those 16 (or more) opening-related pawn structure enumerations for the (early) middlegame-state is not performance critical and only takes few bits inside the pawn-hash entry. To make eval and search aware of the strategical goal or theme for both sides - also considering king locations, castle- and king-safety issues.

Gerd

[Gerd Isenberg]

A very simple way to see if you have a strong pawn formation is to attack your own pawns with the pawns of the same color. If you have nice long pawn chains, then each pawn will attack(actually defend) one or more of his siblings most of the time. It is an extremely cheap operation if you use bitboards (two shifts and an and operation per side).

Dann, are you aware of the computer chess wiki?
http://chessprogramming.wikispaces.com/
http://chessprogramming.wikispaces.com/ ... Properties
http://chessprogramming.wikispaces.com/ ... h+Approach

http://chessprogramming.wikispaces.com/space/pagelist
http://chessprogramming.wikispaces.com/tag/list

If not, you (and all others of course) are welcome to become a member there, to eventually contribute up and then. All critique and suggestions on technical aspects and/or fixing grammatical errors and miss-formulations is highly appreciated.

Gerd

[bob]

My recollection is that older versions of crafty has code to detect stonewall formations. Recent versions don't have it anymore. Perhaps it was not effective?

It was an asymmetric evaluation term and all of that was eliminated within the last 2 years.

Also it did not do what Gerd is looking for. It was an almost exact match, where at least 3 of the 4 pawns had to match. He is looking more general than that I believe, with some measure between 0 and 100 of how well the match fits...

[CThinker]

It was an asymmetric evaluation term and all of that was eliminated within the last 2 years.

Also it did not do what Gerd is looking for. It was an almost exact match, where at least 3 of the 4 pawns had to match. He is looking more general than that I believe, with some measure between 0 and 100 of how well the match fits...

Dann posted an example of how your old code could be effective at certain positions. Maybe it is worth bringing it back?

[bob]

It was an asymmetric evaluation term and all of that was eliminated within the last 2 years.

Also it did not do what Gerd is looking for. It was an almost exact match, where at least 3 of the 4 pawns had to match. He is looking more general than that I believe, with some measure between 0 and 100 of how well the match fits...

Dann posted an example of how your old code could be effective at certain positions. Maybe it is worth bringing it back?

One day, if I can figure out how to do that without any sort of asymmetrical behavior, I will do that. But we removed _all_ asymmetry in the eval when we started the rewrite last year or the year before, and we don't want to regress to that solution for certain types of problems...

[Tony]

It was an asymmetric evaluation term and all of that was eliminated within the last 2 years.

Also it did not do what Gerd is looking for. It was an almost exact match, where at least 3 of the 4 pawns had to match. He is looking more general than that I believe, with some measure between 0 and 100 of how well the match fits...

Dann posted an example of how your old code could be effective at certain positions. Maybe it is worth bringing it back?

One day, if I can figure out how to do that without any sort of asymmetrical behavior, I will do that. But we removed _all_ asymmetry in the eval when we started the rewrite last year or the year before, and we don't want to regress to that solution for certain types of problems...

Why would this be asymmetrical ? Shouldn't you just pull the score closer to zero if the "loosing" side has the choice to wall ?

Tony