In this attempt, we design and implement a tiny language for position querying. It is tiny since we focus on conditions/expressions only and ignore all other aspects. Users can query other information using SQL queries.
1. The query language
The EBNF (Extended Backus Naur Form) of the language as the below:
Code: Select all
clause = condition { ("and" | "or" | "&&" | "||") condition }
condition = expression { ( "=" | "<" | "<="| " >" | ">=" | "==“ | "!=" | "<>" ) expression }
expression = term {( "+" | "-" ) term }
term = factor {( "*" | "/" ]) factor}
factor = number | piece | "(" expression ")"
piece = piecename (<empty> | square | squareset)
piecename = "K" | "Q" | "R" | "B" | "N" | "P" | "k" | "q" | "r" | "b" | "n" | "p" | "white" | "black"
squareset = column | row | "[" (square | squarerange | columnrange | rowrange) { "," (square | squarerange | columnrange | rowrange) } "]"
squarerange = square "-" square
columnrange = column "-" column
rowrange = row "-" row
square = column row
column = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h"
row = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8"
A condition/expression may have some chess piece names such as Q (for white Queens), p (for black Pawns). When evaluating, they are counted as cardinalities/total numbers of those chess pieces on the chessboard.
Examples:
Code: Select all
R the total number of White Rooks
qb3 the total number of Black Queens on square b3
B3 the total number of White Bishops on row 3
bb the total number of Black Bishops on column b
n[b-e] the total number of Black Knights from column b to e
P[a4, c5, d5] the total number of White Pawns on squares a4, c5, and d5
The condition may be implicit or explicit:
Code: Select all
R the implicit form of the comparison R != 0
R == 3 the total of White Rooks must be 3
q[5-7] >= 2 the total of Black Queens from row 5 to row 7 must be equal or larger than 2
Code: Select all
// find all positions having 3 White Queens
Q = 3
// Find all positions having two Black Rooks in the middle squares
r[e4, e5, d4, d5] = 2
// White Pawns in d4, e5, f4, g4, Black King in b7
P[d4, e5, f4, g4] = 4 and kb7
// black Pawns in column b, row 5, from square a2 to d2 must be smaller than 4
p[b, 5, a2 - d2] < 4
// Black Pawns in column c more than 1
pc > 1
// White Pawns in row 3 from 2
P3 >= 2
// Two Bishops in column c, d, e, f
B[c-f] + b[c-f] = 2
// There are 5 white pieces in row 6
white6 = 5
2. Parser
Because the language is very simple and input strings are typically so short, we implement its parser in a simple, straightforward way, using the recursive method. From an input string (query), the parser will create an evaluation tree. That tree will be evaluated at every chess position with the parameters as a set of bitboards of that position. The position and its game will be picked up as the result if the evaluation of the tree is true (not zero).
3. Benchmarks
We query the database which was created from the previous attempt (Attempt 9th). This time we use strings in the above language to query. For example, to query all games with positions having three white Queens, we use the string:
Code: Select all
Q = 3
Query string: “Q = 3”
Code: Select all
Search with query Q = 3...
1. gameId: 13613, fen: r1b3Q1/pp6/1kn5/2bp4/5Q2/4QK2/1pq2P2/5BNR b - 0 23
2. gameId: 185316, fen: r1QQ1r2/p5bk/1p4p1/4p3/4q1p1/6Q1/P6P/R1R3K1 b - 0 35
3. gameId: 203116, fen: 1QQ1rbk1/5ppp/p2q1n2/3p4/4n3/1P1BPr1P/1B3P2/Q1R2RK1 b - 0 34
4. gameId: 286972, fen: 1QQ5/5pk1/5qp1/7p/4B3/1Q3P2/6PP/3R3K b - 0 42
5. gameId: 419965, fen: 1QQ5/4r1pk/Q6p/8/8/7P/6PK/8 b - 0 45
…
50. gameId: 3264750, fen: 2Q3Q1/8/4b3/8/1k6/8/p4K2/Q7 b - 0 65
51. gameId: 3265286, fen: Q2QQR2/6k1/8/8/5KP1/8/8/8 b - 0 71
52. gameId: 3389288, fen: QQ6/8/8/3K2p1/6kp/8/7Q/8 b - 0 63
53. gameId: 3437474, fen: QQ6/8/K7/8/1Q6/8/k7/8 b - 0 94
54. gameId: 3438425, fen: 1QQ2rk1/4q1bp/Q2p1np1/4p3/2P1Pp1P/5P2/5BP1/4KB1R b K 0 28
55. gameId: 3444434, fen: 1Q1QQ3/8/8/5k2/8/8/P7/2K5 b - 0 59
56. gameId: 3445945, fen: 4Q2k/5Q2/p5p1/1p2P3/3P4/P2p2QP/3q4/2r3RK b - 0 48
57. gameId: 3450566, fen: 1Q3Q1Q/6B1/8/1p2p3/4k3/2P1p3/PP2K3/7R b - 0 47
Elapsed: 242118 ms, 04:02, total results: 57, time per results: 4247 ms
Query string: “r[e4, e5, d4, d5] = 2”
Code: Select all
1. gameId: 475, fen: 6k1/7p/6p1/2Br1p2/1p2r2P/pP2N1P1/P2K4/8 w - 0 42
2. gameId: 1008, fen: 5bk1/5ppp/p3p3/3rP1P1/Pp1rNP2/1P6/5RKP/4R3 w - 1 31
3. gameId: 1051, fen: 6k1/2q2p1p/6p1/p2r4/1pPr3P/3p4/P2Q1PP1/2R3K1 w - 0 32
4. gameId: 1857, fen: 6k1/2p3p1/p1n2p1p/2nr4/PpN1rP2/1P6/1BP3PP/R3R1K1 w - 0 25
5. gameId: 2927, fen: 5k2/3q1p1Q/3p2p1/p2Pr1P1/2P1r3/2R5/P6P/5R1K w - 0 34
…
8200. gameId: 3452200, fen: 5R2/pp6/2p3k1/4r1pN/3r2P1/1P1P4/P1PK4/8 w - 2 33
8201. gameId: 3452276, fen: 6k1/pp4p1/7p/P2r1P1P/4r1P1/1P6/4K3/R7 w - 0 28
8202. gameId: 3452545, fen: 6k1/6pp/5p1q/3rp3/4r3/1P6/P1P2P2/3KR3 w - 0 34
8203. gameId: 3452636, fen: 2k5/1p6/8/p2r2PR/4r3/1KP1p3/PP6/4R3 w - 0 32
8204. gameId: 3452998, fen: 8/2pb4/3p1k1p/pPpPrp2/P1P1rN2/2R1R1PP/5K2/8 w - 2 52
8205. gameId: 3453043, fen: 5nk1/5p2/4p1p1/3rP2q/pp1r4/4QRPP/P4PK1/1B2R3 w - 1 32
8206. gameId: 3453642, fen: 8/1R3K1k/8/3r4/3r2BP/2n5/8/2B5 w - 10 63
8207. gameId: 3454480, fen: 6k1/1p1n1ppp/2p5/p1PprP2/N3r3/PP2P3/5KPP/R3R3 w - 1 23
8208. gameId: 3455477, fen: 6k1/2p2pp1/p6p/1p1rr3/1Bb5/P5NP/1PBb1PP1/R2R2K1 w - 4 28
8209. gameId: 3455554, fen: 6k1/p4ppp/5n2/1pqrr1N1/2p4P/8/PPQ2PP1/R2R2K1 w - 0 26
8210. gameId: 3456127, fen: 8/5k2/8/3r4/3r1p2/8/2K4Q/8 w - 14 95
8211. gameId: 3456227, fen: 4q3/5pk1/5np1/1p1pr3/p2r2P1/P1N1PP2/1P2R1K1/4Q3 w - 0 50
8212. gameId: 3456229, fen: 8/4qppk/5p1p/3rrP1P/6P1/3R3K/P2Q4/1R6 w - 0 53
Elapsed: 253891 ms, 04:13, total results: 8212, time per results: 30 ms
c. Three White Pawns in d4, e5, f4, g4, Black King in b7
Search with query: “P[d4, e5, f4, g4] = 4 and kb7”
Code: Select all
1. gameId: 841, fen: 8/1k4pp/p1p1pp2/4P3/PK1P1PP1/7P/8/8 w - 1 35
2. gameId: 6425, fen: 3r1n1r/pk1qnpp1/1pp1p2p/3pP2P/NB1P1PP1/P2Q3R/1PP5/2KR4 w - 1 18
3. gameId: 26939, fen: 4r3/pk2npp1/q1p1p2p/2BpP2P/3P1PP1/2P5/P1QK4/R7 w - 0 25
4. gameId: 28376, fen: 8/pk3p2/R1n1p1p1/3pP3/2pP1PPp/2P2B1P/2P5/1rBK1n2 w - 3 52
5. gameId: 33063, fen: 1r5r/1k2np2/1pp1p1p1/p2pP3/P1nP1PPp/2PB3P/2P2B2/RR2K3 w - 1 27
6. gameId: 35027, fen: r6r/pk2nppq/1pn1p2p/3pP2P/b1pP1PPN/P1P1B3/R1PKB3/3Q3R b - f3 0 18
7. gameId: 36328, fen: r1r5/1k1q1p2/1p2p1p1/3pP2p/bn1P1PP1/2p1NB1P/2P2K2/R2Q3R b - 0 42
8. gameId: 39399, fen: 3r1b1r/pkpq2pp/1p2p2n/n2pPp2/3P1PP1/P1NQ3P/1PPBN3/2K3RR b - g3 0 15
9. gameId: 45124, fen: 4r3/1k2nrp1/2b1p1Np/1p1pP2P/p1pP1PP1/P6R/1PB2R2/6K1 b - 0 43
10. gameId: 50501, fen: 3r3r/pkqn1p2/2n1p1pp/1p1pP3/2pP1PP1/2P2N2/PPNQ3P/1K1R3R b - g3 0 20
…
470. gameId: 3316120, fen: 4q1rr/pkn1npbp/1pp1pBp1/3pP3/3P1PP1/1NPB1Q1P/PP6/2KR3R w - 1 19
471. gameId: 3319876, fen: 8/1k2np2/1rp1p1pp/3pP3/P2P1PP1/KN6/2R4P/8 w - 2 36
472. gameId: 3333216, fen: 3r3r/1knnbp2/qp2p1p1/2ppP3/p2P1PP1/2P1BNN1/PP2Q1K1/R4R2 w - 1 19
473. gameId: 3359102, fen: 5r2/1k3p1p/p1p1p1p1/1nP1P3/1NpP1PP1/7P/8/KR6 w - 1 36
474. gameId: 3374676, fen: 8/1k3p2/4p3/p2pP3/p2P1PP1/4K3/Nb6/8 b - g3 0 44
475. gameId: 3381812, fen: 4r1b1/1kp3Kp/2p3p1/B1RpPp2/3P1PP1/P6P/8/8 b - 0 51
476. gameId: 3386119, fen: 7r/pk1b1ppr/1pn1p1p1/3pP3/q1pP1PP1/P1P2R1P/1QPB1R2/5BK1 b - g3 0 23
477. gameId: 3390871, fen: 3r1b1r/pk1qn1p1/1pn1p2p/3pPp1P/3P1PP1/5N1Q/PP1BN1K1/2R4R w - 1 18
478. gameId: 3402434, fen: 3rn2r/pk1q1pbp/1pp1p1p1/3pP3/3P1PP1/3RQNNP/PPP5/2K4R w - 2 20
479. gameId: 3408344, fen: 1rnq3r/pk1b1pp1/1p2p2p/n2pP2P/PBpP1PPN/2P5/2P1B3/R1Q1K2R w KQ 1 17
480. gameId: 3411214, fen: r4q2/bk2nr2/1pp3pp/3pP3/PP1P1PP1/2NQ1RKP/8/2R5 w - 3 29
481. gameId: 3432729, fen: 6n1/1k3pbp/6p1/p1BpP3/P2P1PP1/7P/8/N5K1 w - 1 33
482. gameId: 3444804, fen: 8/pk3ppp/1p2p3/3pP3/P1rP1PPP/R2K4/8/8 w - 0 32
483. gameId: 3452950, fen: 3r1b1r/pkqbnpp1/1p2p2p/n2pP2P/2pP1PP1/P1P1B2B/1P1NN3/R2QK2R w KQ 1 15
Elapsed: 249175 ms, 04:09, total results: 483, time per results: 515 ms
Search string: “B[c-f] + b[c-f] == 2”
Code: Select all
1. gameId: 3, fen: rn1q1rk1/ppp1ppbp/3p1np1/8/3PPBb1/2N2N2/PPPQ1PPP/R3KB1R w KQ 1 6
2. gameId: 2, fen: r2qkb1r/pp3ppp/1n1p2b1/1BPPp3/1P1N2P1/5P1P/P7/R1BQK2R b KQkq 0 16
3. gameId: 4, fen: r2q1rk1/1bp1pp1p/p1n2bp1/1p1B4/3P4/2N1P3/PP3PPP/R2QK1NR w KQ 1 11
4. gameId: 1, fen: r4rk1/pb2bppp/8/2ppP3/8/2P1BN2/P4PPP/R4RK1 w - 0 15
5. gameId: 5, fen: rnNq3r/1p1pkppp/p3pn2/8/1bP5/2N5/PP2PPPP/R1BQKB1R b KQ 0 8
7. gameId: 7, fen: 6. gameId: 6, fen: r1b2rk1/pp1nqpbp/2pp1npB/4p3/3PP3/2NB3P/PPPQNPP1/R4RK1 b - 1 10
…
3326756. gameId: 3456396, fen: r2qk2r/bpp2ppp/p2pbn2/8/4P3/P2N1P2/1PPPN1PP/R1BQK2R w KQkq 1 11
3326757. gameId: 3456397, fen: rnb1k2r/pp2npb1/2pp1qpp/4p3/4P3/1BNP1Q1P/PPP2PP1/R1B1K1NR b KQkq 0 9
3326758. gameId: 3456398, fen: r2qkb1r/pbppnpp1/1p5p/3NN3/2B1P3/P2P4/1PP2PPP/R2QK2R w KQkq 0 10
3326759. gameId: 3456393, fen: r2q1rk1/ppp2pp1/2np3p/2b5/4PQ2/2N2NP1/PP3Bb1/R3K3 w Q 0 16
3326760. gameId: 3456399, fen: 1r4r1/2b1k2p/2Pp1pbn/1p1Pp1p1/pP2P1P1/3KBP2/N6P/RN4R1 w - 1 30
Elapsed: 190605 ms, 03:10, total results: 3326760, time per results: 0 ms
e. Find all games with 5 White pieces on row 6
Search string: “white6 = 5”
Code: Select all
1. gameId: 139197, fen: 8/4q2k/BR1QPbpP/4p3/4P3/4B2r/2KN2n1/8 b - 0 43
2. gameId: 229745, fen: 5b2/p1k2Pp1/P1P1KPPp/3B3P/8/8/8/8 b - 0 46
3. gameId: 410414, fen: 8/8/1PBKPR2/8/3k4/3r4/4r3/8 b - 0 77
4. gameId: 416799, fen: 5q1k/p1r5/P2pBNQP/3P4/5K2/8/8/8 b - 5 56
5. gameId: 448981, fen: 3r3r/4k2p/PPR1B2P/6K1/6P1/8/8/8 b - 0 76
…
50. gameId: 3173451, fen: 2k5/6pp/PPPPK3/8/8/7P/6P1/8 b - 5 67
51. gameId: 3176339, fen: 4b3/2k1P3/R2PBKpP/5p2/5P2/8/7r/8 b - 0 62
52. gameId: 3180607, fen: 1rb2r2/8/ppPPnNQR/5kP1/P3pp2/1Nq5/8/1R4K1 b - 2 43
53. gameId: 3270729, fen: r5k1/8/PK2NRP1/7p/7P/6P1/8/8 b - 0 65
54. gameId: 3276938, fen: n5rk/q4r1p/B1RRQ1pB/p1p1p2n/Pp2P2P/1P4P1/2P2P2/6K1 b - 3 43
55. gameId: 3325056, fen: 3k4/5B1b/1PKPP2P/5p2/5P2/8/8/8 b - 0 67
56. gameId: 3329210, fen: r5k1/8/PR2PPK1/8/8/8/8/8 b - 1 58
57. gameId: 3438015, fen: r3k1r1/1q6/bPpR1PBQ/2Pp4/P2P3P/6P1/8/6K1 b - 2 42
Elapsed: 283500 ms, 04:43, total results: 57, time per results: 4973 ms
4. Quick conclusions for this attempt
- All results are identical to the previous attempt
- As fast as the previous attempt (9th)
- Even though the language is tiny and so simple it can query almost all kinds of position questions
- Due to the simpleness, we believe users won’t have much trouble learning and using this language
The query language and parser work so well!
5. Source code
All code of this Attempt has been pushed already into a new branch “searchwithtextparser”.