lucasart/demolito

UCI Chess Engine

demolito's Issues

killers

do not SEE prune checking moves

For example, this mate would be found at depth 1, if the qsearch did not SEE prune Bxg3+ (or Qxg3+):

position startpos moves f2f4 e7e5 f4e5 d7d6 e5d6 f8d6 b1c3
eval
r n b q k . n r
p p p . . p p p
. . . b . . . .
. . . . . . . .
. . . . . . . .
. . N . . . . .
P P P P P . P P
R . B Q K B N R
rnbqk1nr/ppp2ppp/3b4/8/8/2N5/PPPPP1PP/R1BQKBNR b KQkq - 1
score cp -102
go depth 3
info depth 1 score cp -62 nodes 44 pv b8c6
info depth 2 score mate 3 nodes 1261 pv d8h4 g2g3 h4g3 h2g3 d6g3

tt refined eval

depth and ply limit in search

enforce ply limit, and depth limit for QS, using eval+see logic like DiscoCheck.

lazy SEE

Selector::select() to return SEE, either from scores[] if the move is a capture, or by calculating SEE. Use the work already done in Selector::score().

handle normal chess

Move::from_string() and Move::to_string() only work in Chess960.

check extension

enable check extension for see >= 0.

mobility eval

replicate DiscoCheck to start with.

Chess960 opening set

generate 2 ply opening set.

search doesn't stop with unoptimized debug compile

• with -O3 -DNDEBUG no problem
• with -O0 problem occurs. repro: position startpos, go depth 1. search doesn't stop after depth 1, nor heed "stop" command.

tt refined eval

• use for qsearch stand pat
• refine only upwards
• use for eval >= beta condition in null search (warning: must prevent double null move explicitly)

detect repetitions

• need a (thread local) array of keys.
• iterate backward: 2-rep until we pass the root, then 3-rep.

PST

Replicate PST from DiscoCheck. Multiply by 2 for better resolution, and double material values (EP = 200).

pawn eval

• isolated
• chained
• hole
• passed
• shield: didn't work.
• pawn hash (per thread)

UCI mate score display

repetition bug

position fen rnbqk1nr/ppppppbp/8/6p1/1P6/2P5/P1QPPPPP/RNB1KBNR b HAha - 0 1 moves b8c6 g1f3 c6b4 c2b2 b4d5 f3g5 g8f6 d2d4 e8h8 b1d2 d7d6 d2e4 e7e5 c1e3 c8f5 e4f6 d8f6 g5f3 b7b6 e1a1 a8d8 h1g1 f5e4 b2d2 f8e8 c1b2 f6f5 f3g5 g7f6 g5e4 f5e4 d2d3 e4g4 b2b1 g4e4 b1b2 e4h4 h2h3 h7h6 b2b1 c7c6 d1d2 a7a6 d2d1 h6h5 d1d2 h4e4 d2d1 d5c3 b1c2 e5d4 d3e4 e8e4 d1d4 f6d4 e3d4 c3d5 c2d3 e4e6 e2e4 d5f4 d3e3 f4d5 e3d3 d5b4 d3e3 d6d5 f2f3 b4c2 e3d3 c2d4 d3d4 d5e4 d4c4 g8g7 f1e2 g7f6 g1e1 f6f5 g2g4 h5g4 h3g4 f5e5 f3e4 d8d4 c4c3 d4e4 c3d3 e6d6 d3c3 f7f6 a2a3 e5d5 c3d3 e4d4 d3e3 d6e6 e3f3 d4d2 e2c4 d5c4 e1e6 d2d3 f3e4 d3d4 e4f5 d4d5 f5f6 c4c5 e6e7 d5d2 f6e5 d2e2 e5f6 e2e7 f6e7 c5d4 e7d6 c6c5 g4g5 b6b5 g5g6 a6a5 g6g7 b5b4 g7g8q b4a3 g8d5 d4e3 d5c5 e3e4 c5e5 e4d3 e5a5 d3e3 a5a3 e3d4 a3b4 d4d3 d6d5 d3e3 b4e4 e3d2 d5d4 d2d1 e4e5 d1d2 e5e3 d2c2 e3c3 c2d1 c3d3 d1e1 d4e4 e1f2 d3f3 f2e1 f3e3 e1d1 e4d4 d1c2 e3d3 c2b2 d3c3 b2b1
eval
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . K . . . .
. . Q . . . . .
. . . . . . . .
. k . . . . . .
8/8/8/8/3K4/2Q5/8/1k6 w - - 29
eval = 1067
go depth 2
info depth 1 score cp 1071 nodes 38 pv c3e3
info depth 2 score cp 1092 nodes 162 pv c3d2 b1a1
bestmove c3d2 ponder b1a1

Only after c3e3 is played, it understands that b1c2 is draw by repetition:

position fen rnbqk1nr/ppppppbp/8/6p1/1P6/2P5/P1QPPPPP/RNB1KBNR b HAha - 0 1 moves b8c6 g1f3 c6b4 c2b2 b4d5 f3g5 g8f6 d2d4 e8h8 b1d2 d7d6 d2e4 e7e5 c1e3 c8f5 e4f6 d8f6 g5f3 b7b6 e1a1 a8d8 h1g1 f5e4 b2d2 f8e8 c1b2 f6f5 f3g5 g7f6 g5e4 f5e4 d2d3 e4g4 b2b1 g4e4 b1b2 e4h4 h2h3 h7h6 b2b1 c7c6 d1d2 a7a6 d2d1 h6h5 d1d2 h4e4 d2d1 d5c3 b1c2 e5d4 d3e4 e8e4 d1d4 f6d4 e3d4 c3d5 c2d3 e4e6 e2e4 d5f4 d3e3 f4d5 e3d3 d5b4 d3e3 d6d5 f2f3 b4c2 e3d3 c2d4 d3d4 d5e4 d4c4 g8g7 f1e2 g7f6 g1e1 f6f5 g2g4 h5g4 h3g4 f5e5 f3e4 d8d4 c4c3 d4e4 c3d3 e6d6 d3c3 f7f6 a2a3 e5d5 c3d3 e4d4 d3e3 d6e6 e3f3 d4d2 e2c4 d5c4 e1e6 d2d3 f3e4 d3d4 e4f5 d4d5 f5f6 c4c5 e6e7 d5d2 f6e5 d2e2 e5f6 e2e7 f6e7 c5d4 e7d6 c6c5 g4g5 b6b5 g5g6 a6a5 g6g7 b5b4 g7g8q b4a3 g8d5 d4e3 d5c5 e3e4 c5e5 e4d3 e5a5 d3e3 a5a3 e3d4 a3b4 d4d3 d6d5 d3e3 b4e4 e3d2 d5d4 d2d1 e4e5 d1d2 e5e3 d2c2 e3c3 c2d1 c3d3 d1e1 d4e4 e1f2 d3f3 f2e1 f3e3 e1d1 e4d4 d1c2 e3d3 c2b2 d3c3 b2b1 c3e3
eval
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . K . . . .
. . . . Q . . .
. . . . . . . .
. k . . . . . .
8/8/8/8/3K4/4Q3/8/1k6 b - - 30
eval = -1071
go depth 1
info depth 1 score cp 0 nodes 5 pv b1c2
bestmove b1c2 ponder 0000

Move::is_pseudo_legal()

Will be needed to verify the hash move, and to detect TT collisions

tt policy

• replace if key is different, or depth is higher: no mesurable impact (tiny gain?)
• 2 slot tt clusters, replace the one with the lowest depth: small regression.

fix SEE for quiet moves

Bug exposed by the fact that sorting all moves by SEE has the same node counts as sorting only captures by SEE.

bench crash

• instrument search at root
• iterate until crash can be produced at root
• add more assert
• repeat with larger set of positions

aspiration windows

• geometric increase (double width).
• assume no search instability (which is still the case). change to half-window when instability gets introduced.

eval bug

position fen r1bqkbnr/pp1ppppp/2n5/2p5/4P3/5N2/PPPP1PPP/RNBQKB1R w HAha - 0
eval
r . b q k b n r
p p . p p p p p
. . n . . . . .
. . p . . . . .
. . . . P . . .
. . . . . N . .
P P P P . P P P
R N B Q K B . R
r1bqkbnr/pp1ppppp/2n5/2p5/4P3/5N2/PPPP1PPP/RNBQKB1R w HAha - 0
eval = 0
position fen r1bqkbnr/pp1ppppp/2n5/2p5/4P3/5N2/PPPP1PPP/RNBQKB1R w HAha - 0 moves e1e2
eval
r . b q k b n r
p p . p p p p p
. . n . . . . .
. . p . . . . .
. . . . P . . .
. . . . . N . .
P P P P K P P P
R N B Q . B . R
r1bqkbnr/pp1ppppp/2n5/2p5/4P3/5N2/PPPPKPPP/RNBQ1B1R b ha - 1
eval = -56

retire discoCheckers

Not used anymore, since we got rid of Move::gives_check()

tempo

disco check

disco check refinment of see pruning

killers

use std::vector for pv

currently, without PVS, the slowdown is huge (30% slower). but with PVS, PV nodes will be few, especially in long searches, so I can implement a zero cost model for non PV nodes, and allow a 30% slowdown in PV nodes.

the advantage is to get rid of VLA, which are not C++ standard (only standard in C). also, it means less stack usage.

SMP - step 1

• start N searching threads on id_loop().
• main thread does: select() for timeout read from stdin, check search termination conditions (time, nodes). Kill searching threads when done.

safe checks

• safe checks: simplest form (not defended by pawns)
• exclude squares defended by king or occupied by attacker's pieces
• tune weight (ballpark)
• exclude all defended squares (not only by king or pawns)

search bug

exposed by a406eed

quiet checks at depth == 0

from DiscoCheck

prune sub promotions in QSearch

from DiscoCheck

TT

Start with the most basic:

• TT Entry: 8 bytes key + 8 bytes data. 2+2+2 for move, score, eval. 1+1 for depth, bound.
• always replace.
• use xor trick, with relaxed atomics to prevent compiler reloading.

draw detection

1. done: 50 move rule
2. todo: insufficient material

never return before depth 1 is completed

this would lead to sending an illegal move to the GUI. can happen in extreme conditions, with few msec or a low lim.nodes value.

attacks

• calculate attack arrays in mobility()
• use in tactics()
• use in king_attacks()

bug in castlable_rooks_ok

Last check is wrong. (k,k+1) is for f < FILE_H, and vice versa.

Move::givesCheck()

fix castling

illegal move 0000

position fen rnbqk1nr/ppppppbp/8/6p1/1P6/2P5/P1QPPPPP/RNB1KBNR b HAha - 0 1 moves b8c6 d2d4 e7e5 g1f3 e5d4 b4b5 g5g4 c2e4 g8e7 e4g4 e8h8 c1h6 e7f5 h6g7 f5g7 b5c6 d7d5 g4h4 d8h4 c6b7 c8b7 f3h4 g7e6 h4f5 c7c5 e2e3 d4e3 f2e3 a8d8 b1d2 c5c4 e1f2 f8e8 f1e2 b7c6 f5d4 d8d6 e2f3 e8d8 d2c4 e6d4 c4d6 d4f3 d6f7 g8f7 g2f3 f7e6 f3f4 e6f5 f2e2 f5e4 a1d1 c6b5 e2d2 b5c4 a2a3 h7h6 h1e1 a7a6 h2h3 h6h5 a3a4 a6a5 h3h4 d8d6 d1c1 d6d8 c1c2 c4b3 c2b2 b3a4 b2a2 a4c6 a2a5 d8d7 a5c5 d7d6 d2e2 d6e6 e1d1 e6d6 c3c4 e4f5 c4d5 c6a4 d1e1 a4b3 e2f3 d6d7 e3e4 f5f6 f3e3 d7e7 e3d4 e7d7 e1e3 b3a4 e3d3 d7e7 d5d6 e7d7 c5h5 d7d6 h5d5 d6e6 d5f5 f6e7 f5e5 a4c6 f4f5 e6e5 d4e5 c6b5 f5f6 e7f7 d3d4 f7g6 d4d1 b5c6 d1e1 c6b5 e1g1 g6h5 f6f7 b5d3 f7f8q
isready
go depth 2
info depth 1 score cp -1329 nodes 12 pv h5h4
info depth 2 score cp -16383 nodes 3793 pv
bestmove 0000 ponder g1b1

PV

• ss->pv[MAX_PLY]
• make ss per thread

value_t instead of int

typedef it to int for now, but use value_t everywhere that is correct (alpha, beta, scores in search, scores in sort, see scores, material values). will allow experimenting with int16_t for compactness, for example.

reductions

1. done: reduce 1 ply. exclude: first move, in check, give check, capture/promotion. 100 elo gain!
2. done: depth >= 3 only. otherwise useless re-search (eg. search(2) does reduced search(0) and verifies with search(1), which is practically the same as search(0)).
3. done: reduce bad captures
4. didn't work: reduce bad checks, unless discovered
5. didn't work: extend disco checks with see < 0

PVS

Only after TT (no point before). TT move must be sorted first.

history

In the history branch:

• introduce History table
• update History
• use History for move ordering: doesn't work !?
• use History or move order for reduction (ie. LMR or History pruning)

null move

type safety

• Color: done
• Piece: done
• Rank: done
• File: done
• Square: done

UCI

minimum implementation to get started:

• uci
• isready
• ucinewgame
• position
• go
• quit
• eval

stop, ponderhit will be managed by the search (IO thread).

razoring

compact move lists

all moves[] and scores[] array from sort live on the stack, and will use (12+4)*192*192=576kB per thread, which can be significant with many threads.

Possibilities:

• use move_t for moves
• use int16_t for scores
• use int8_t for Move data members

What is the right tradeoff here ?

killers