Difference between revisions of "Pawn Islands (Bitboards)"

From Chessprogramming wiki
Jump to: navigation, search
Line 88: Line 88:
 
=External Links=
 
=External Links=
 
* [https://en.wikipedia.org/wiki/Glossary_of_chess#P Glossary of chess from Wikipedia - P]
 
* [https://en.wikipedia.org/wiki/Glossary_of_chess#P Glossary of chess from Wikipedia - P]
 +
* [[:Category:Steps Ahead|Steps Ahead]] - [https://en.wikipedia.org/wiki/Steps_Ahead_(album) Islands], 1983, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 +
: lineup:. [https://en.wikipedia.org/wiki/Mike_Mainieri Mike Mainieri], [[:Category:Michael Brecker|Michael Brecker]], [https://en.wikipedia.org/wiki/Eddie_G%C3%B3mez Eddie Gómez],  [[:Category:Peter Erskine|Peter Erskine]], [https://en.wikipedia.org/wiki/Eliane_Elias Elaine Elias]
 +
: {{#evu:https://www.youtube.com/watch?v=ixOvuqRX9nE|alignment=left|valignment=top}}
  
 
=References=  
 
=References=  
 
<references />
 
<references />
 
 
'''[[Pawn Pattern and Properties|Up one Level]]'''
 
'''[[Pawn Pattern and Properties|Up one Level]]'''
 
[[Category:Samuel Bak]]
 
[[Category:Samuel Bak]]
 +
[[Category:Steps Ahead]]
 +
[[Category:Michael Brecker]]
 +
[[Category:Peter Erskine]]

Revision as of 23:06, 11 January 2019

Home * Board Representation * Bitboards * Pawn Pattern and Properties * Pawn Islands

Samuel Bak - Drowned [1]

Pawn Islands of either side are groups of pawns (at least one), separated by files without own pawns. Those files are therefore either halfopen or open. All other things being equal, the side with fewer pawn islands has an advantage, because the individual pawns are easier to defend against enemy attacks. Each island has a west- or east border file. Rook-files may be the most outer borders.

Sample Filesets

Black has three islands here, white two:

 . . . . . . . .
 b . . . . . . b
 . b . b b . b .
 . . . . . . . .
 . . . . . . . .
 . w . . . w . .
 w . w . . . w w
 . . . . . . . .

Those are the black and white filesets, one byte each.

 b b . b b . b b

 w w w . . w w w

Island Borders

Based on filesets, we can simply determine the west- or east border-files of each island. By shifting left or right one, xor with the original fileset to get all the 0-1 or 1-0 transitions - to finally intersect it with the original fileset to restrict the transitions inside this set of occupied files. The result are the files with half-isolanis.

Since conjunction is distributive over xor, one may alternately swap both operands. In fact it is the relative complement of the shifted files in files and takes three operations each.

East

 b b . b b . b b
 . b . . b . . b

 w w w . . w w w
 . . w . . . . w
BYTE islandsEastFiles(BYTE f) {return f & (f ^ (f >> 1));}
BYTE islandsEastFiles(BYTE f) {return f ^ (f & (f >> 1));}
BYTE islandsEastFiles(BYTE f) {return f &     ~(f >> 1) ;}
1 . . . 1 1 . .  files
. . . 1 1 . . .  files >> 1 (board left or west)
1 . . 1 . 1 . .  xor       -> all the west 0-1 or 1-0 file-transitions
1 . . . . 1 . .  and files -> east files of each island

West

 b b . b b . b b
 b . . b . . b .

 w w w . . w w w
 w . . . . w . .
BYTE islandsWestFiles(BYTE f) {return f & (f ^ (f << 1));} // ... (f+f)
BYTE islandsWestFiles(BYTE f) {return f ^ (f & (f << 1));}
BYTE islandsWestFiles(BYTE f) {return f &     ~(f << 1) ;}
1 . . . 1 1 . .  files
. 1 . . . 1 1 .  files << 1  (board right or east)
1 1 . . 1 . 1 .  xor       -> all the east 0-1 or 1-0 file-transitions
1 . . . 1 . . .  and files -> west files of each island

Number of Islands

Since each island has exactly one west- and one east border-file, the population count of either border-set might be used to determine the numbers of islands, see dispersion. Of course all byte-wise calculations may be implemented by small, preinitialized lookup tables, indexed by fileset (0..255), containing the number of islands, bitboards of isolated files and whatever else. The maximum number of islands is four.

Isolated Files

The intersection of east- and west border-files are already files with isolated pawns.

1 . . . . 1 . .  east files of each island
1 . . . 1 . . .  west files of each island
1 . . . . . . .  and -> isolated files
. . . . 1 1 . .  xor -> resets isolated files

To isolate wider (2..8) islands is not that hard either.

External Links

lineup:. Mike Mainieri, Michael Brecker, Eddie Gómez, Peter Erskine, Elaine Elias

References

Up one Level