-
Notifications
You must be signed in to change notification settings - Fork 1
/
generate_horde_insufficient_material_tests.py
1392 lines (1180 loc) · 53.1 KB
/
generate_horde_insufficient_material_tests.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
from chess import Board, Move, Piece, SquareSet
from chess import BB_BACKRANKS, BB_DARK_SQUARES, BB_LIGHT_SQUARES
from chess import ( A1, A2, A3, A4, A5, A6, A7, A8,
B1, B2, B3, B4, B5, B6, B7, B8,
C1, C2, C3, C4, C5, C6, C7, C8,
D1, D2, D3, D4, D5, D6, D7, D8,
E1, E2, E3, E4, E5, E6, E7, E8,
F1, F2, F3, F4, F5, F6, F7, F8,
G1, G2, G3, G4, G5, G6, G7, G8,
H1, H2, H3, H4, H5, H6, H7, H8 )
from chess import popcount, square, square_name, square_file, square_rank
from copy import deepcopy
from os.path import abspath
from time import time
class WrappedBoard(Board):
def __init__(self, fen="8/8/8/8/8/8/8/8 b - - 0 1", name="", is_insufficient=True):
super().__init__(fen)
self.comment = name
self.is_insufficient = is_insufficient
@staticmethod
def mirror_square(square):
from chess import square as sq
return sq(7-square_file(square), square_rank(square))
@staticmethod
def is_backrank(square):
return (square in range(0,8)) or (square in range(56,64))
def get_empty_square(self):
"""Gets an empty square not in the backranks."""
return SquareSet(72057594037927680).difference(self.occupied).pop()
def mirror_vertical(self):
mirrored = WrappedBoard('8/8/8/8/8/8/8/8 b - - 0 1', self.comment, self.is_insufficient)
for i in range(8):
for j in range(8):
sq = square(i,j)
piece = self.piece_at(sq)
if piece:
mirrored.set_piece_at(self.mirror_square(sq), piece)
mirrored.compute_white_composition()
mirrored.compute_black_composition()
return mirrored
def compute_white_composition(self):
"""
Returns the material composition of the white side.
Only up to two same colour bishops are taken into account.
"""
white = self.occupied_co[1]
dark = popcount(white&self.bishops&BB_DARK_SQUARES)
dark = 2 if dark>=2 else dark
light = popcount(white&self.bishops&BB_LIGHT_SQUARES)
light = 2 if light>=2 else light
self.white_composition = (
popcount(white&self.pawns),
dark+light,
popcount(white&self.knights),
popcount(white&self.rooks),
popcount(white&self.queens),
dark,
light
)
return self.white_composition
def compute_black_composition(self):
black = self.occupied_co[0]
self.black_composition = (
popcount(black&self.pawns),
popcount(black&self.bishops),
popcount(black&self.knights),
popcount(black&self.rooks),
popcount(black&self.queens),
popcount(black&self.bishops&BB_DARK_SQUARES),
popcount(black&self.bishops&BB_LIGHT_SQUARES)
)
return self.black_composition
def __le__(self, other):
"""Is the material on 'self' a subset of the material on 'other'?"""
for i in range(7):
if self.white_composition[i] > other.white_composition[i]:
return False
for i in range(7):
if self.black_composition[i] > other.black_composition[i]:
return False
return True
def __ge__(self, other):
"""Is the material on 'self' a superset of the material on 'other'?"""
return other <= self
def deepcopy(self):
return WrappedBoard(self.fen(), self.comment, self.is_insufficient)
def print(self):
print( "\n".join([self.comment,self.__str__(),self.fen(),str(self.is_insufficient)])+"\n" )
def has_insufficient_material(self, color):
import chess
# The side with the king can always win by capturing the horde.
if color == chess.BLACK:
return False
white = self.occupied_co[chess.WHITE]
queens = chess.popcount( white & self.queens )
pawns = chess.popcount( white & self.pawns )
rooks = chess.popcount( white & self.rooks )
bishops = chess.popcount( white & self.bishops )
knights = chess.popcount( white & self.knights )
horde_darkb = chess.popcount(chess.BB_DARK_SQUARES & white & self.bishops)
horde_lightb = chess.popcount(chess.BB_LIGHT_SQUARES & white & self.bishops)
horde_bishop_co = lambda : chess.WHITE if horde_lightb >= 1 else chess.BLACK
horde_num = (
pawns + knights + rooks + queens +
(horde_darkb if horde_darkb <= 2 else 2) +
(horde_lightb if horde_lightb <= 2 else 2)
)
# Two same color bishops suffice to cover all the light and dark squares around the enemy king.
pieces = self.occupied_co[chess.BLACK]
pieces_pawns = chess.popcount( pieces & self.pawns )
pieces_bishops = chess.popcount( pieces & self.bishops )
pieces_knights = chess.popcount( pieces & self.knights )
pieces_rooks = chess.popcount( pieces & self.rooks )
pieces_queens = chess.popcount( pieces & self.queens )
pieces_darkb = lambda : chess.popcount(chess.BB_DARK_SQUARES & pieces & self.bishops)
pieces_lightb = lambda : chess.popcount(chess.BB_LIGHT_SQUARES & pieces & self.bishops)
pieces_num = chess.popcount(pieces)
pieces_oppositeb_of = lambda square_color: pieces_darkb() if square_color == chess.WHITE else pieces_lightb()
pieces_sameb_as = lambda square_color: pieces_lightb() if square_color == chess.WHITE else pieces_darkb()
pieces_of_type_not = lambda piece: pieces_num - piece
has_bishop_pair = lambda side: (horde_lightb >= 1 and horde_darkb >= 1) if side == chess.WHITE else (pieces_lightb() >= 1 and pieces_darkb() >= 1)
if horde_num == 0:
return True
if horde_num >= 4:
# Four or more white pieces can always deliver mate.
return False
if (pawns >= 1 or queens >= 1) and horde_num >= 2:
# Pawns/queens are never insufficient material when paired with any other
# piece (a pawn promotes to a queen and delivers mate).
return False
if rooks >= 1 and horde_num >= 2:
# A rook is insufficient material only when it is paired with a bishop
# against a lone king. The horde can mate in any other case.
# A rook on A1 and a bishop on C3 mate a king on B1 when there is a
# friendly pawn/opposite-color-bishop/rook/queen on C2.
# A rook on B8 and a bishop C3 mate a king on A1 when there is a friendly
# knight on A2.
if not (horde_num == 2 and rooks == 1 and bishops == 1 and pieces_of_type_not(pieces_sameb_as(horde_bishop_co())) == 1):
return False
if horde_num == 1:
if pieces_num == 1:
# A lone piece cannot mate a lone king.
return True
elif queens == 1:
# The horde has a lone queen.
# A lone queen mates a king on A1 bounded by:
# -- a pawn/rook on A2
# -- two same color bishops on A2, B1
# We ignore every other mating case, since it can be reduced to
# the two previous cases (e.g. a black pawn on A2 and a black
# bishop on B1).
return not (
pieces_pawns >= 1 or
pieces_rooks >= 1 or
pieces_lightb() >= 2 or
pieces_darkb() >= 2
)
elif pawns == 1:
# Promote the pawn to a queen or a knight and check whether white
# can mate.
pawn_square = chess.SquareSet(self.pawns & white).pop()
promote_to_queen = WrappedBoard(self.fen())
promote_to_queen.set_piece_at( pawn_square, chess.Piece(chess.QUEEN,chess.WHITE) )
promote_to_knight = WrappedBoard(self.fen())
promote_to_knight.set_piece_at( pawn_square, chess.Piece(chess.KNIGHT,chess.WHITE) )
return promote_to_queen.has_insufficient_material(chess.WHITE) and promote_to_knight.has_insufficient_material(chess.WHITE)
elif rooks == 1:
# A lone rook mates a king on A8 bounded by a pawn/rook on A7 and a
# pawn/knight on B7. We ignore every other case, since it can be
# reduced to the two previous cases.
# (e.g. three pawns on A7, B7, C7)
return not (
pieces_pawns >= 2 or
(pieces_rooks >= 1 and pieces_pawns >= 1) or
(pieces_rooks >= 1 and pieces_knights >= 1) or
(pieces_pawns >= 1 and pieces_knights >= 1)
)
elif bishops == 1:
# The horde has a lone bishop.
return not (
# The king can be mated on A1 if there is a pawn/opposite-color-bishop
# on A2 and an opposite-color-bishop on B1.
# If black has two or more pawns, white gets the benefit of the doubt;
# there is an outside chance that white promotes its pawns to
# opposite-color-bishops and selfmates theirself.
# Every other case that the king is mated by the bishop requires that
# black has two pawns or two opposite-color-bishop or a pawn and an
# opposite-color-bishop.
# For example a king on A3 can be mated if there is
# a pawn/opposite-color-bishop on A4, a pawn/opposite-color-bishop on
# B3, a pawn/bishop/rook/queen on A2 and any other piece on B2.
pieces_oppositeb_of(horde_bishop_co()) >= 2 or
(pieces_oppositeb_of(horde_bishop_co()) >= 1 and pieces_pawns >= 1) or
pieces_pawns >= 2
)
elif knights == 1:
# The horde has a lone knight.
return not (
# The king on A1 can be smother mated by a knight on C2 if there is
# a pawn/knight/bishop on B2, a knight/rook on B1 and any other piece
# on A2.
# Moreover, when black has four or more pieces and two of them are
# pawns, black can promote their pawns and selfmate theirself.
pieces_num >= 4 and (
pieces_knights>=2 or pieces_pawns>=2 or
(pieces_rooks>=1 and pieces_knights>=1) or
(pieces_rooks>=1 and pieces_bishops>=1) or
(pieces_knights>=1 and pieces_bishops>=1) or
(pieces_rooks>=1 and pieces_pawns>=1) or
(pieces_knights>=1 and pieces_pawns>=1) or
(pieces_bishops>=1 and pieces_pawns>=1) or
(has_bishop_pair(chess.BLACK) and pieces_pawns>=1)
) and ( pieces_of_type_not(pieces_darkb())>=3 if pieces_darkb()>=2 else True )
and ( pieces_of_type_not(pieces_lightb())>=3 if pieces_lightb()>=2 else True )
)
# By this point, we only need to deal with white's minor pieces.
elif horde_num == 2:
if pieces_num == 1:
# Two minor pieces cannot mate a lone king.
return True
elif knights == 2:
# A king on A1 is mated by two knights, if it is obstructed by a
# pawn/bishop/knight on B2. On the other hand, if black only has
# major pieces it is a draw.
return not (pieces_pawns + pieces_bishops + pieces_knights >= 1)
elif has_bishop_pair(chess.WHITE):
return not (
# A king on A1 obstructed by a pawn/bishop on A2 is mated
# by the bishop pair.
pieces_pawns >= 1 or pieces_bishops >= 1 or
# A pawn/bishop/knight on B4, a pawn/bishop/rook/queen on
# A4 and the king on A3 enable Boden's mate by the bishop
# pair. In every other case white cannot win.
( pieces_knights >= 1 and pieces_rooks + pieces_queens >= 1 )
)
elif bishops >= 1 and knights >= 1:
# The horde has a bishop and a knight.
return not (
# A king on A1 obstructed by a pawn/opposite-color-bishop on
# A2 is mated by a knight on D2 and a bishop on C3.
pieces_pawns >= 1 or pieces_oppositeb_of(horde_bishop_co()) >= 1 or
# A king on A1 bounded by two friendly pieces on A2 and B1 is
# mated when the knight moves from D4 to C2 so that both the
# knight and the bishop deliver check.
pieces_of_type_not( pieces_sameb_as(horde_bishop_co()) ) >=3
)
else:
# The horde has two or more bishops on the same color.
# White can only win if black has enough material to obstruct
# the squares of the opposite color around the king.
return not (
# A king on A1 obstructed by a pawn/opposite-bishop/knight
# on A2 and a opposite-bishop/knight on B1 is mated by two
# bishops on B2 and C3. This position is theoretically
# achievable even when black has two pawns or when they
# have a pawn and an opposite color bishop.
( pieces_pawns >= 1 and pieces_oppositeb_of(horde_bishop_co()) >= 1 ) or
( pieces_pawns >= 1 and pieces_knights >= 1 ) or
( pieces_oppositeb_of(horde_bishop_co()) >= 1 and pieces_knights >= 1 ) or
( pieces_oppositeb_of(horde_bishop_co()) >= 2 ) or
pieces_knights >= 2 or
pieces_pawns >= 2
# In every other case, white can only draw.
)
elif horde_num == 3:
# A king in the corner is mated by two knights and a bishop or three
# knights or the bishop pair and a knight/bishop.
if (knights == 2 and bishops == 1) or knights == 3 or has_bishop_pair(chess.WHITE):
return False
else:
# White has two same color bishops and a knight.
# A king on A1 is mated by a bishop on B2, a bishop on C1 and a
# knight on C3, as long as there is another black piece to waste
# a tempo.
return pieces_num == 1
return True
class MaterialCompositions:
def __init__(self):
"""A dictionary to keep the material compositions."""
self.material = dict()
self.boards = dict()
@staticmethod
def __is_tuple1_subset_tuple2(tuple1, tuple2):
if tuple1[0] > tuple2[0]:
return False
for j in range(2,7):
if tuple1[j] > tuple2[j]:
return False
return True
@staticmethod
def __mirror(tuple):
return tuple[0],tuple[1],tuple[2],tuple[3],tuple[4],tuple[6],tuple[5]
def add(self, board):
"""
Adds a board in the collection.
If the board has bishops then its vertical mirroring is also added.
"""
white_comp = board.white_composition
self.material.setdefault(white_comp,set())
black_comp = board.black_composition
for cand_black_comp in self.material[white_comp]:
if self.__is_tuple1_subset_tuple2(cand_black_comp,black_comp):
return None
else:
self.material[white_comp].add(black_comp)
self.boards.setdefault( white_comp, dict() )[black_comp] = board
if board.bishops:
self.material.setdefault( self.__mirror(white_comp), set() ).add( self.__mirror(black_comp) )
self.boards.setdefault( self.__mirror(white_comp), dict() )[self.__mirror(black_comp)] = board.mirror_vertical()
def __len__(self):
return sum( [ 1 for i in self.material for j in self.material[i]] )
def __getitem__(self, i):
return self.material[i]
def exists_subset_of(self, board):
"""
Returns True if the material composition of 'board' has a subset
material composition in 'self' or if there are enough black pawns
that can be promoted to reach such a state.
"""
try:
if board.sufficient_subset:
return True
except AttributeError:
pass
for white_comp in self.material:
if self.__is_tuple1_subset_tuple2(white_comp, board.white_composition):
if board.black_composition in self.material[white_comp]:
board.sufficient_subset = (white_comp,board.black_composition)
return True
for black_comp in self.material[white_comp]:
if black_comp[0] > board.black_composition[0]:
continue
residual_pawns = board.black_composition[0] - black_comp[0]
for j in range(2,7):
if black_comp[j] > board.black_composition[j]:
residual_pawns += board.black_composition[j] - black_comp[j]
if residual_pawns < 0:
break
else:
board.sufficient_subset = (white_comp,black_comp)
self.boards.setdefault(board.white_composition,dict())[board.black_composition] = self.boards[white_comp][black_comp]
return True
board.sufficient_subset = None
return False
class GenerateTestsFromPatterns:
def __init__(self):
"""Use add_pattern to add patterns."""
self.tests = dict()
self.minimal_sufficient_material = MaterialCompositions()
self.FENs = set()
self.BB_BORDER = SquareSet(18411139144890810879)
self.BB_BACKRANKS = SquareSet(BB_BACKRANKS)
self.BB_DARK_SQUARES = SquareSet(BB_DARK_SQUARES)
self.BB_LIGHT_SQUARES = SquareSet(BB_LIGHT_SQUARES)
def __add(self, board):
if board.fen() in self.FENs:
return None
board.compute_white_composition()
board.compute_black_composition()
board.has_sufficient_subset = lambda : self.minimal_sufficient_material.exists_subset_of(board)
if board.is_insufficient and board.has_sufficient_subset():
board.is_insufficient = False
if board.is_insufficient == False:
self.minimal_sufficient_material.add( board )
self.tests.setdefault(board.comment,[]).append( board )
self.FENs.add( board.fen() )
if board.bishops:
self.__add( board.mirror_vertical() )
def has_sufficient_subset(self, board):
return self.minimal_sufficient_material.exists_subset_of(board)
def add_pattern(self, name, black_pattern, black_king_square=A1, white=[], is_insufficient=False, generate_insufficient=True, dont_spam=False):
"""
Creates tests for a given black pattern.
For the pattern (A2,"bp"),(B3,"bq") we get four cases:
- (A2,"b"),(B3,"b")
- (A2,"b"),(B3,"q")
- (A2,"p"),(B3,"b")
- (A2,"p"),(B3,"q")
name: The name of the pattern.
e.g. "black king, queen and knight against white bishops and queen"
If the name already exists, it appends the new test cases.
black_pattern: A list of (square, string).
Each string contains the symbols of the black pieces that
can occupy that square.
The king should not be included.
e.g. [(H7,"pq"),(D4,"pbnrq"),(E4,"bn")]
black_king_square: The square occupied by the black king.
white: A list of (square,white_piece_symbol) indicating where the white army is.
e.g. [(A2,"P"),(A3,"Q")]
is_insufficient: Does the given input represent a position in which white can mate?
Ideally, if is_insufficient==False, the provided position should
showcase that possibility.
generate_insufficient: Produce tests for the case 'not is_insufficient' when
'is_insufficient==False'.
e.g. If black_pattern=[(A2,"bnq")], then create tests
for the cases where black_pattern=[(A2,"pr")]
There is no validation for the data provided by the caller.
"""
black_squares = [i[0] for i in black_pattern]
base_board = WrappedBoard("8/8/8/8/8/8/8/8 b - - 0 1", name, is_insufficient)
for square,piece in white:
base_board.set_piece_at( square, Piece.from_symbol(piece) )
base_board.set_piece_at( black_king_square, Piece.from_symbol("k") )
self.tests.setdefault(name,[])
self.add_boards_from(
name,
black_pattern,
is_insufficient,
base_board
)
if generate_insufficient and is_insufficient == False:
for anti_pattern in self.__anticombinations(black_pattern):
self.add_boards_from(
name,
[(sq,anti_pattern[n]) for n,sq in enumerate(black_squares)],
not is_insufficient,
base_board
)
if False:#not dont_spam:
for board in self.tests[name]:
if board.is_checkmate()==board.is_insufficient:
print("In '",name,"' there exists a board such as\
\nboard.is_checkmate() == ",board.is_checkmate()," == board.is_insufficient",sep="")
board.print()
def add_single_test(self, name, fen, is_insufficient=False):
board = WrappedBoard(fen,name,is_insufficient)
self.__add( board )
def add_tests_from_white_pattern(self, name, white_pattern, black_king_square=A1, is_insufficient=False):
"""Creates tests when a white pattern=[(sq,"pieces"),...] is given."""
white_combinations = self.__compute_combinations([piece for sq,piece in white_pattern])
for white_side in white_combinations:
board = WrappedBoard()
board.set_piece_at(black_king_square,Piece.from_symbol("k"))
for white_piece in white_side:
sq = board.get_empty_square()
board.set_piece_at(sq,Piece.from_symbol(white_piece))
board.is_insufficient = is_insufficient
board.name = name
self.__add( board )
def __print_test(self,name):
return "\n".join([str(n)+".\n"+board.__str__()+"\n"+str(board.is_insufficient)+"\n" for n,board in enumerate(self.tests[name],1)])
def __repr__(self):
return self.tests.__repr__()
def __str__(self):
return "\n".join([name+":\n\n"+self.__print_test(name)+"\n" for name in self.tests])
def print_by_name(self,name):
print("\n",name,":\n",sep="")
for n,j in enumerate(self.tests[name],1):
print(n,".",sep="")
print(j)
print(j.is_insufficient)
print()
def print(self):
for name in self.tests:
self.print_by_name(name)
print("Generated",len(self),"positions.")
def __compute_combinations(self, pattern, index=0, result=[]):
"""
Computes the combinations from a pattern.
e.g pattern=["ab","cde"]->["ac","ad","ae","bc","bd","be"]
"""
if index == len(pattern):
return result
if result == []:
return self.__compute_combinations(pattern, index+1, pattern[index])
new_result = []
for comb in result:
for piece in pattern[index]:
new_result.append( "".join(comb+piece) )
return self.__compute_combinations(pattern, index+1, set(new_result))
def add_boards_from(self, name, pattern, is_insufficient, base_board):
"""Adds test boards for a black pattern=list of (square, string)."""
num_pieces = range(len(pattern))
baseFEN = base_board.fen()
black_combinations = self.__compute_combinations( [i[1] for i in pattern] )
for possibillity in black_combinations:
board = WrappedBoard( baseFEN, name, is_insufficient )
for i in num_pieces:
piece = Piece.from_symbol( possibillity[i] )
sq = pattern[i][0]
if possibillity[i] == "p" and base_board.is_backrank(sq):
sq = board.get_empty_square()
board.set_piece_at( sq, piece )
self.__add( board )
if black_combinations == []:
board = WrappedBoard( baseFEN, name, is_insufficient )
self.__add( board )
def __anticombinations(self, pattern):
"""
Generates all the combinations of material that occupy the same squares
and is not covered by the given pattern.
"""
default_pattern = dict([(i[0],"pbnrq") for i in pattern])
anti_patterns = set()
for i in pattern:
new_pattern = deepcopy(default_pattern)
new_pattern[i[0]] = "".join(
set([j for j in new_pattern[i[0]]])
.difference( [j for j in i[1]] )
)
anti_patterns.update( self.__compute_combinations( [new_pattern[j[0]] for j in pattern] ) )
return anti_patterns
def __getitem__(self, name):
return self.tests[name]
def __len__(self):
return sum([len(self.tests[name]) for name in self.tests])
def find_sufficient_subset_composition(self, board):
""""Finds tests with sufficient material in the given board."""
for name in self.tests:
for n,candidate_board in enumerate(self.tests[name]):
if candidate_board.is_insufficient==False and candidate_board <= board:
print(candidate_board.comment+", index:"+str(n),candidate_board,candidate_board.fen(),candidate_board.is_insufficient,sep="\n",end="\n\n")
def find_tests_with_subset_composition(self, board):
for name in self.tests:
for n,candidate_board in enumerate(self.tests[name]):
if candidate_board <= board:
print(candidate_board.comment+", index:"+str(n),candidate_board,candidate_board.fen(),candidate_board.is_insufficient,sep="\n",end="\n\n")
def randomised_tests(self, percentage=.1, correct=True):
"""
Picks a percentage of the existing tests and adds some 'random' black
material to create new tests.
"""
from random import randint,sample
limit = int(percentage*len(self))+1
for n in range(limit):
board = WrappedBoard()
board.set_piece_at(A1,Piece.from_symbol("k"))
white = randint(1,5)
sq = 48
for white_piece in range(white):
board.set_piece_at(sq,Piece.from_symbol("PBNRQ"[randint(0,4)]))
black = randint(0,10)
sq = 8
for black_piece in range(black):
board.set_piece_at(sq,Piece.from_symbol("pbnrq"[randint(0,4)]))
sq += 1
self.__add(board)
if correct:
self.correct_contradictions()
def create_tests_with_pawns(self, percentage=.1, correct=True):
from random import randint,sample
for name in deepcopy(self.tests):
limit = 1 + int(percentage*len(self.tests[name]))
for board in sample(self.tests[name], limit):
temp = board.deepcopy()
for sq in SquareSet(temp.occupied_co[True]):
if temp.is_backrank(sq):
temp.set_piece_at(sq, None)
sq = temp.get_empty_square()
temp.set_piece_at(sq, Piece.from_symbol("P"))
temp.comment = "pawns-only"
self.__add(temp)
if correct:
self.correct_contradictions()
def off_by_one(self, correct=True):
"""Generate tests with one more or one less black pieces from the existing tests."""
newtests = dict()
for name in self.tests:
newtests = []
for cand_board in self.tests[name]:
sq = cand_board.get_empty_square()
for piece_type in range(1,6):
board = cand_board.deepcopy()
board.set_piece_at(sq,Piece(piece_type,False))
newtests.append(board)
board.set_piece_at(sq,None)
for sq in SquareSet(cand_board.occupied_co[0]):
if cand_board.piece_type_at(sq)!=6:
board = cand_board.deepcopy()
board.is_insufficient = True
board.set_piece_at(sq,None)
newtests.append(board)
for board in newtests:
self.__add( board )
if correct:
self.correct_contradictions()
def correct_contradictions(self):
"""
Sometimes, when more than two patterns are used and anti-patterns are enabled,
the generated tests produce contradictions.
For example, the position 8/8/8/8/8/2Q5/b7/kr6 is generated from the pattern:
[(A2,"pb"), (B1,"b")],
black_king_square=A1,
white=[(C3,"Q")],
is_insufficient=False
Strictly speaking, white cannot deliver mate in this position; if black were to
to respect the pattern and keep their pieces on A2 and B1. Though, a queen on C1
mates a king on A1 obstructed by a rook on A2.
Therefore white has sufficient material in the first case and we need to correct
the value board.is_insufficient for the first board.
"""
for name in self.tests:
for n,board in enumerate(self.tests[name]):
if board.is_insufficient==True and board.has_sufficient_subset():
self.tests[name][n].is_insufficient = False
if board.is_insufficient != board.has_insufficient_material(True):
board.print()
raise Exception("Sanity check failed")
def __brute_force_black_side(self, king_board, black_side_num):
"""
Fills the 'king_board' with combinations of black material so that black has at most
'black_side_num' pieces and return a list with all those combinations.
"""
def rec(board, black_num):
if black_num==0:
return None
sq = board.get_empty_square()
for black in "pbnrq":
temp_board = board.deepcopy()
temp_board.set_piece_at(sq,Piece.from_symbol(black))
temp_board.compute_white_composition()
temp_board.compute_black_composition()
temp_board.is_insufficient = not self.has_sufficient_subset(temp_board)
output.append(temp_board)
if not temp_board.is_insufficient:
if black_num==2:
rec(temp_board, 1)
elif black_num==1:
rec(temp_board, 0)
else:
rec(temp_board, 2)
else:
rec(temp_board, black_num-1)
output = []
rec(king_board, black_side_num)
return output
def brute_force_and_assess_positions(self, max_black_pieces=5, whites = [["Q"],["P"],["N"],["R"],["B"], ["Q","P"],["R","N"],["R","B"],["N","N"],["B","B"],["B",None,"B"],["B","N"]]):
"""Generates positions with up to 'max_black_pieces' and assess them."""
king_board = WrappedBoard()
king_board.set_piece_at(A1,Piece.from_symbol("k"))
boards = self.__brute_force_black_side(king_board, max_black_pieces)
for board in boards:
for white_side in whites:
temp = board.deepcopy()
for n,white in enumerate(white_side):
temp.set_piece_at(A7+n,Piece.from_symbol(white) if white else None)
self.add_single_test(
"brute-force",
temp.fen(),
temp.is_insufficient
)
def export_to(self, file_name, preamble="", formatting=lambda x: x, epilogue="", write_type="w"):
"""
Writes the tests in a file.
Includes a preamble before the tests, uses a formatting function and
adds a epilogue after the tests.
"""
self.correct_contradictions()
FENs = set()
refined_tests = []
for name in self.tests:
for board in self.tests[name]:
if board.fen() not in FENs:
refined_tests.append(board)
FENs.add(board.fen())
with open(file_name,write_type) as file:
file.write(preamble)
for board in refined_tests:
file.write(formatting(board))
file.write(epilogue)
def __piece(self, symbol):
return Piece.from_symbol(symbol if symbol not in ["D","L"] else "B")
def __find_posts_to_attack_from(self, target, piece_type):
board = Board.empty()
board.set_piece_at( target, self.__piece( piece_type ) )
if piece_type=="D":
if target in self.BB_DARK_SQUARES:
return board.attacks(target)
else:
return SquareSet(0)
elif piece_type=="L":
if target in self.BB_LIGHT_SQUARES:
return board.attacks(target)
else:
return SquareSet(0)
else:
return board.attacks(target)
def __get_white_configurations(self, king, escape_squares, white_minor_pieces):
"""
Generates possible white configurations that minimise the squares
available to the king to which he can escape to when up to two
white minor pieces are given.
"""
boards = []
for n,checker in enumerate(white_minor_pieces):
for sq in self.__find_posts_to_attack_from(king, checker):
board = WrappedBoard('8/8/8/8/8/8/8/8 b - - 0 1', "", True)
board.set_piece_at( king, Piece(6, False) )
board.set_piece_at( sq, self.__piece(checker) )
board.checker = checker
board.checker_sq = sq
if len(white_minor_pieces)==2:
board.not_checker = white_minor_pieces[(1+n)%2]
boards.append( board )
if len(white_minor_pieces) == 1:
output = set()
for board in boards:
if board.checker != "N" and board.bishops & int(self.BB_BORDER) == 0:
# discard some cases to reduce the search space
continue
output.add(board.fen())
return [WrappedBoard(fen) for fen in output]
output = set()
for board in boards:
checker = board.checker
checker_sq = board.checker_sq
not_checker = board.not_checker
for esc_sq in escape_squares:
for sq in self.__find_posts_to_attack_from(esc_sq, not_checker):
if checker_sq == sq:
continue
temp_board = board.deepcopy()
temp_board.set_piece_at( sq, self.__piece(not_checker) )
if temp_board.is_legal( Move(king, sq) ) or temp_board.is_legal( Move(king, checker_sq) ) or not temp_board.is_check() or len(temp_board.checkers())==2:
continue
if white_minor_pieces == ['D','D'] or white_minor_pieces == ['L','L']:
if sq in SquareSet.ray(king, checker_sq) or king in temp_board.attacks(sq)&temp_board.attacks(checker_sq):
# discard some cases to reduce the total number of cases
continue
if white_minor_pieces == ['D','L']:
if temp_board.occupied_co[1]&0x007e_7e7e_7e7e_7e00!=0:
# discard some cases to reduce the total number of cases
continue
output.add( temp_board.fen() )
if white_minor_pieces == ['D','N'] or white_minor_pieces == ['L','N']: #double check
for sq in self.__find_posts_to_attack_from(king, not_checker):
if checker_sq == sq:
continue
temp_board = board.deepcopy()
temp_board.set_piece_at( sq, self.__piece(not_checker) )
if temp_board.is_legal( Move(king, sq) ) or temp_board.is_legal( Move(king, checker_sq) ) or not temp_board.is_check():
continue
if checker == "N":
bishop, knight = sq, checker_sq
else:
knight, bishop = sq, checker_sq
if bishop not in self.BB_BORDER:
# discard some cases to reduce the total number of cases
continue
if len(SquareSet.between(king,bishop)&temp_board.attacks(knight)) == 0:
continue
output.add(temp_board.fen())
return [WrappedBoard(fen) for fen in output]
def __can_piece_save_king(self, board, piece, squares_to_stop_check):
"""
Is the piece able to attack one of the 'squares_to_stop_check'
and save their king?
"""
for sq in squares_to_stop_check:
try:
board.find_move(piece, sq)
return True
except ValueError:
pass
return False
def __get_black_configurations(self, king, escape_squares, white_board):
"""
Fills the empty squares around the king with black pieces
so white mates and returns a board with the found pattern.
"""
white_board.black_pattern = []
checkers = white_board.checkers()
for checker_sq in checkers:
try:
white_board.find_move(king, checker_sq)
return white_board
except ValueError:
pass
available_squares = [sq for sq in escape_squares if not white_board.is_attacked_by(True,sq)]
if popcount(checkers)>1:
for sq in available_squares:
white_board.black_pattern.append(
(sq,"bnrq") if white_board.is_backrank(sq) else (sq,"pnbrq")
)
return white_board
squares_to_stop_check = (
SquareSet.from_square(checker_sq)|white_board.attacks(checker_sq)
)&(~white_board.occupied_co[0])
for sq in available_squares:
white_board.set_piece_at(sq, Piece.from_symbol("p"))
for black_piece in available_squares:
possible_pieces = ""
if black_piece not in self.BB_BACKRANKS:
white_board.set_piece_at(black_piece,Piece.from_symbol("p"))
if self.__can_piece_save_king(white_board, black_piece, squares_to_stop_check)==False:
possible_pieces += "p"
white_board.set_piece_at(black_piece,Piece.from_symbol("n"))
if self.__can_piece_save_king(white_board, black_piece, squares_to_stop_check)==False:
possible_pieces += "n"
white_board.set_piece_at(black_piece,Piece.from_symbol("q"))
if self.__can_piece_save_king(white_board, black_piece, squares_to_stop_check)==False:
possible_pieces += "brq"
else:
white_board.set_piece_at(black_piece,Piece.from_symbol("b"))
if self.__can_piece_save_king(white_board, black_piece, squares_to_stop_check)==False:
possible_pieces += "b"
white_board.set_piece_at(black_piece,Piece.from_symbol("r"))
if self.__can_piece_save_king(white_board, black_piece, squares_to_stop_check)==False:
possible_pieces += "r"
white_board.set_piece_at(black_piece,Piece.from_symbol("p"))
if possible_pieces == "":
white_board.black_pattern == None
break
else:
white_board.black_pattern.append((black_piece,possible_pieces))
for sq in available_squares:
white_board.set_piece_at(sq, None)
return white_board
def print_patterns(self, king_square, white_pieces):
"""The current implementation only works for minor pieces."""
board=Board.empty()
board.set_piece_at(king_square,Piece.from_symbol("k"))
escape_squares = board.attacks(king_square)
white_boards = self.__get_white_configurations( king_square, escape_squares, white_pieces)
patterns = list( (board, self.__get_black_configurations( king_square, escape_squares, board ).black_pattern) for board in white_boards )
output = []
for board, pattern in patterns:
nxt = [(square_name(i[0]).upper(),"".join([lt if lt!="b" else ("d" if i[0] in self.BB_DARK_SQUARES else "l") for lt in i[1]])) for i in pattern], [square_name(sq).upper() for sq in SquareSet(board.occupied_co[1])]
if pattern and nxt not in output:
output.append(nxt)
s = ""
for j in nxt[0]:
s+=j[1]
print(s,nxt)
return output
def generate_patterns( self, white_sides = [ ['D'], ['N'], ['D','N'], ['N','N'], ['D','L'], ['D','D'] ], king_squares = [A1,A2,A3,A4] ):
"""
Finds mating patterns for the given white sides.
The current implementation only works for minor pieces.
"""
## D=dark square bishop, L=light square bishop
for king in king_squares:
board = WrappedBoard('8/8/8/8/8/8/8/8 b - - 0 1')
board.set_piece_at(king,Piece(6,False))
escape_squares = board.attacks(king)
for white_side in white_sides:
white_configurations = self.__get_white_configurations(king, escape_squares, white_side)
for white_configuration in white_configurations:
board_with_pattern = self.__get_black_configurations(king, escape_squares, white_configuration)
white_configuration.compute_white_composition()
self.add_boards_from(
str(white_configuration.white_composition).replace("'","").replace(", ","-"),
board_with_pattern.black_pattern,
False,
white_configuration
)
if __name__ == "__main__":