voroskoi/pistike - Change CU3XNAGXZHXACBEDPM3THFT6AWAJ4HC5PXZM3Z72WWVMSHPOOXFQC

Move search to separate thread, implement uci stop

Created by voroskoi on January 27, 2023

CU3XNAGXZHXACBEDPM3THFT6AWAJ4HC5PXZM3Z72WWVMSHPOOXFQC

Dependencies

In channels

main

Change contents

Insertion in src/uci.zig at line 8 [7.32]

[7.270]

const Search = @import("Search.zig").Search;
var log_level = std.log.default_level;

Replacement in src/uci.zig at line 12 [7.32]

B:BD[7.271] → [7.271:309]

const search = @import("search.zig");

[7.271]

[7.309]

// https://www.wbec-ridderkerk.nl/html/UCIProtocol.html
pub fn loop(allocator: std.mem.Allocator) !void {
    var gs = try GameState.init(allocator, null);
    var search = Search.init(&gs);
    var buf: [512]u8 = undefined;
    const stdin = std.io.getStdIn().reader();
    const stdout = std.io.getStdOut();
    try hello();

Replacement in src/uci.zig at line 23 [7.32]

B:BD[7.310] → [8.0:48]

pub fn parseGo(gs: *GameState, in: Str) !void {

[7.310]

[7.357]

    while (true) {
        const input = try stdin.readUntilDelimiterOrEof(&buf, '\n') orelse break;
        if (std.mem.eql(u8, input, "quit")) {
            std.log.debug("received UCI quit, quitting...", .{});
            break;
        }
        if (std.mem.eql(u8, input, "debug on")) {
            log_level = std.log.Level.debug;
            std.log.debug("log level set to debug", .{});
        } else if (std.mem.eql(u8, input, "debug off")) {
            log_level = std.log.default_level;
        }
        if (std.mem.eql(u8, input, "stop")) {
            std.log.debug("received UCI stop command", .{});
            @atomicStore(bool, &search.stop, true, std.builtin.AtomicOrder.Unordered);
            std.log.debug("searching stopped", .{});
        }
        if (std.mem.eql(u8, input, "isready")) _ = try stdout.write("readyok\n");
        if (input.len >= 8) {
            if (std.mem.eql(u8, input[0..8], "position")) {
                try parsePosition(&gs, input);
                gs.show();
            }
        }
        if (input.len >= 3) {
            if (std.mem.eql(u8, input[0..3], "uci")) {
                if (std.mem.eql(u8, input, "ucinewgame")) {
                    try parsePosition(&gs, "position startpos");
                    std.log.debug("new uci game initialized", .{});
                } else {
                    try hello();
                }
            }
        }
        if (input.len >= 2) {
            if (std.mem.eql(u8, input[0..2], "go")) {
                const srch = try std.Thread.spawn(
                    std.Thread.SpawnConfig{},
                    parseGo,
                    .{ &search, input },
                );
                srch.detach();
            }
        }
    }
}
fn hello() !void {
    const stdout = std.io.getStdOut();
    _ = try stdout.write("id name pistike\n");
    _ = try stdout.write("id author voroskoi\n");
    _ = try stdout.write("uciok\n");
}
pub fn parseGo(search: *Search, in: Str) !void {

Replacement in src/uci.zig at line 87 [7.32]

B:BD[7.443] → [7.443:509]

B:BD[7.509] → [8.49:89]

        const depth = try std.fmt.parseUnsigned(u4, in[9..], 10);
        try search.bestMove(gs, depth);

[7.443]

[7.552]

        const depth = try std.fmt.parseUnsigned(u8, in[9..], 10);
        try search.bestMove(depth);
        return;

Replacement in src/uci.zig at line 93 [7.32]
B:BD[7.599] → [8.90:122]
```
    try search.bestMove(gs, 6);
```
[7.599]
[7.634]
```
    try search.bestMove(6);
```

Replacement in src/score.zig at line 6 [9.2114]

B:BD[9.2280] → [9.2280:2330]

const GameState = @import("Board.zig").GameState;

[9.2280]

[8.3140]

const Search = @import("Search.zig").Search;

Replacement in src/score.zig at line 24 [9.2114]

B:BD[8.3428] → [3.554:611]

pub fn moves(gs: *const GameState, ml: *MoveList) void {

[8.3428]

[3.611]

pub fn moves(search: *const Search, ml: *MoveList) void {

Replacement in src/score.zig at line 26 [9.2114]

B:BD[3.640] → [3.640:683]

        mp.score = scoreMove(gs, mp.move);

[3.640]

[3.683]

        mp.score = scoreMove(search, mp.move);

Replacement in src/score.zig at line 30 [9.2114]

B:BD[3.692] → [3.692:750]

fn scoreMove(gs: *const GameState, move: BitMove) isize {

[3.692]

[9.2591]

fn scoreMove(search: *const Search, move: BitMove) isize {

Replacement in src/score.zig at line 34 [9.2114]

B:BD[9.2682] → [9.2682:2724]

        const pieces = switch (gs.side) {

[9.2682]

[9.2724]

        const pieces = switch (search.state.side) {

Replacement in src/score.zig at line 40 [9.2114]

B:BD[9.2891] → [9.2891:2961]

            if (gs.bitboards[@enumToInt(piece)].isSet(move.target)) {

[9.2891]

[9.2961]

            if (search.state.bitboards[@enumToInt(piece)].isSet(move.target)) {

Replacement in src/score.zig at line 48 [9.2114]

B:BD[9.3182] → [8.3429:3522]

        if (@bitCast(BitMoveType, killer_moves[0][gs.ply]) == @bitCast(BitMoveType, move)) {

[9.3182]

[9.3319]

        if (@bitCast(BitMoveType, killer_moves[0][search.ply]) == @bitCast(BitMoveType, move)) {

Replacement in src/score.zig at line 53 [9.2114]

B:BD[9.3396] → [8.3523:3621]

        else if (@bitCast(BitMoveType, killer_moves[1][gs.ply]) == @bitCast(BitMoveType, move)) {

[9.3396]

[9.3538]

        else if (@bitCast(BitMoveType, killer_moves[1][search.ply]) == @bitCast(BitMoveType, move)) {

Insertion in src/main.zig at line 4 [11.50]
[10.1666]
[7.4571]
```
const Search = @import("Search.zig").Search;
```
Deletion in src/main.zig at line 8 [11.50]
∅:D[12.1459] → [13.333:371]
B:BD[7.4603] → [13.333:371]
```
const search = @import("search.zig");
```
Replacement in src/main.zig at line 9 [11.50]
B:BD[11.80] → [14.1246:1264]
```
var debug = true;
```
[11.80]
[13.391]
```
var debug = false;
```
Insertion in src/main.zig at line 23 [11.50]
[13.544]
[14.1530]
```
        var search = Search.init(&gs);
```
Replacement in src/main.zig at line 36 [11.50]
B:BD[8.3935] → [6.1698:1735]
∅:D[15.533] → [14.1797:1842]
∅:D[16.1027] → [14.1797:1842]
∅:D[17.1128] → [14.1797:1842]
∅:D[12.1532] → [14.1797:1842]
∅:D[6.1735] → [14.1797:1842]
∅:D[8.3972] → [14.1797:1842]
∅:D[9.5628] → [14.1797:1842]
B:BD[14.1797] → [14.1797:1842]
```
        try search.bestMove(&gs, 8);
    } else try handleUCI(arena.allocator());
```
[8.3935]
[18.754]
```
        try search.bestMove(8);
    } else try uci.loop(arena.allocator());
```

Deletion in src/main.zig at line 39 [11.50]

∅:D[18.756] → [10.1821:1822]

B:BD[10.1821] → [10.1821:1822]

B:BD[10.1822] → [14.1843:1950]

∅:D[19.134] → [10.1889:1890]

∅:D[18.825] → [10.1889:1890]

∅:D[20.837] → [10.1889:1890]

∅:D[14.1950] → [10.1889:1890]

B:BD[10.1889] → [10.1889:1890]

B:BD[21.1] → [21.1:81]

B:BD[21.81] → [8.3973:4012]

∅:D[8.4012] → [21.129:366]

B:BD[21.129] → [21.129:366]


fn handleUCI(allocator: std.mem.Allocator) !void {
    var gs = try Board.GameState.init(allocator, null);
    var buf: [512]u8 = undefined;
    const stdin = std.io.getStdIn().reader();
    const stdout = std.io.getStdOut();
    while (true) {
        const input = try stdin.readUntilDelimiterOrEof(&buf, '\n') orelse break;
        if (std.mem.eql(u8, input, "quit")) break;
        if (std.mem.eql(u8, input, "isready")) _ = try stdout.write("readyok\n");

Deletion in src/main.zig at line 40 [11.50]

B:BD[21.367] → [21.367:457]

B:BD[21.457] → [7.4604:4655]

∅:D[7.4655] → [21.502:697]

B:BD[21.502] → [21.502:697]

B:BD[21.697] → [7.4656:4724]

∅:D[7.4724] → [21.759:959]

B:BD[21.759] → [21.759:959]

B:BD[21.959] → [8.4013:4058]

∅:D[8.4058] → [21.1051:1081]

B:BD[21.1051] → [21.1051:1081]

B:BD[21.1081] → [22.53792:53794]

B:BD[22.53897] → [22.53897:53898]

        if (input.len >= 8) {
            if (std.mem.eql(u8, input[0..8], "position")) {
                try uci.parsePosition(&gs, input);
                gs.show();
            }
        }
        if (input.len >= 3) {
            if (std.mem.eql(u8, input[0..3], "uci")) {
                if (std.mem.eql(u8, input, "ucinewgame"))
                    try uci.parsePosition(&gs, "position startpos")
                else
                    _ = try stdout.write("id name pistike\nuciok\n");
            }
        }
        if (input.len >= 2) {
            if (std.mem.eql(u8, input[0..2], "go")) {
                try uci.parseGo(&gs, input);
            }
        }
    }
}

Insertion in src/main.zig at line 42 [11.50]
[23.35322]
[24.105]
```
    _ = @import("Board.zig");
```
Replacement in src/main.zig at line 44 [11.50]
B:BD[24.135] → [18.826:856]
```
    _ = @import("Board.zig");
```
[24.135]
[25.4486]
```
    _ = @import("Search.zig");
```
Deletion in src/main.zig at line 47 [11.50]
B:BD[26.3442] → [25.4516:4547]
```
    _ = @import("search.zig");
```
Replacement in src/main.zig at line 49 [11.50]
B:BD[17.1130] → [17.1130:1163]
```
    // _ = @import("perft.zig");
```
[17.1130]
[11.3467]
```
    _ = @import("perft.zig");
```
File move: search.zig → Search.zig
BF:BFD[11.15] → [25.0:34]
BF:BF[25.34] → [25.35:35]
[11.15]
[25.35]

Replacement in src/Search.zig at line 21 [25.35]

B:BD[25.496] → [8.123:187]

// Maximum ply we can reach while searching
const MAX_PLY = 64;

[25.496]

[25.525]

pub const Search = struct {
    state: *GameState,
    stop: bool = false,
    ply: usize = 0,

Replacement in src/Search.zig at line 26 [25.35]
B:BD[25.526] → [8.188:218]
```
var nodes: usize = undefined;
```
[25.526]
[8.218]
```
    var nodes: usize = undefined;
```

Replacement in src/Search.zig at line 28 [25.35]

B:BD[8.219] → [8.219:315]

var pv_length: [MAX_PLY]usize = undefined;
var pv_table: [MAX_PLY][MAX_PLY]BitMove = undefined;

[8.219]

[3.0]

    // Maximum ply we can reach while searching
    const MAX_PLY = 64;

Replacement in src/Search.zig at line 31 [25.35]

B:BD[3.1] → [3.1:30]

var pv_follow: bool = false;

[3.1]

[9.195]

    // LMR
    const FULL_DEPTH_MOVES = 4;
    const REDUCTION_LIMIT = 3;

Replacement in src/Search.zig at line 35 [25.35]

B:BD[9.196] → [27.0:79]

∅:D[27.79] → [8.316:370]

B:BD[9.196] → [8.316:370]

B:BD[8.370] → [5.0:52]

// Late move reduction
const FULL_DEPTH_MOVES = 4;
const REDUCTION_LIMIT = 3;
pub fn bestMove(gs: *GameState, depth: usize) !void {
    const ALPHA = -25_000;
    const BETA = 25_000;

[9.196]

[5.52]

    // NULL move pruning
    const NULL_REDUCTION = 2;

Replacement in src/Search.zig at line 38 [25.35]

B:BD[5.53] → [5.53:111]

    var alpha: isize = ALPHA;
    var beta: isize = BETA;

[5.53]

[25.628]

    // Principle Variation
    var pv_length: [MAX_PLY]usize = undefined;
    var pv_table: [MAX_PLY][MAX_PLY]BitMove = undefined;
    var pv_follow: bool = false;

Replacement in src/Search.zig at line 43 [25.35]

B:BD[25.629] → [8.371:823]

    // clear helper data for search
    {
        score.killer_moves = [_][MAX_PLY]BitMove{
            [_]BitMove{@bitCast(BitMove, @as(BitMoveType, 0))} ** MAX_PLY,
        } ** 2;
        score.history_moves = [_][64]usize{[_]usize{0} ** 64} ** 12;
        pv_length = [_]usize{0} ** MAX_PLY;
        pv_table = [_][MAX_PLY]BitMove{
            [_]BitMove{@bitCast(BitMove, @as(BitMoveType, 0))} ** MAX_PLY,
        } ** MAX_PLY;
        nodes = 0;

[25.629]

[8.823]

    pub fn init(gs: *GameState) @This() {
        return Search{ .state = gs };

Replacement in src/Search.zig at line 47 [25.35]

B:BD[25.699] → [8.830:951]

B:BD[8.951] → [3.31:57]

    // iterative deepening
    var current_depth: usize = 1;
    while (current_depth <= depth) : (current_depth += 1) {
        pv_follow = true;

[25.699]

[16.184]

    pub fn bestMove(self: *@This(), depth: usize) !void {
        self.stop = false;
        const ALPHA = -25_000;
        const BETA = 25_000;

Replacement in src/Search.zig at line 52 [25.35]

B:BD[16.185] → [5.112:177]

        const scr = try negamax(gs, alpha, beta, current_depth);

[16.185]

[5.177]

        var alpha: isize = ALPHA;
        var beta: isize = BETA;

Replacement in src/Search.zig at line 55 [25.35]

B:BD[5.178] → [5.178:400]

        // ASPIRATION window: we fell out, so reset values and try again
        if (scr <= alpha or scr >= beta) {
            alpha = ALPHA;
            beta = BETA;
            current_depth -= 1;
            continue;

[5.178]

[5.400]

        // clear helper data for search
        {
            score.killer_moves = [_][MAX_PLY]BitMove{
                [_]BitMove{@bitCast(BitMove, @as(BitMoveType, 0))} ** MAX_PLY,
            } ** 2;
            score.history_moves = [_][64]usize{[_]usize{0} ** 64} ** 12;
            pv_length = [_]usize{0} ** MAX_PLY;
            pv_table = [_][MAX_PLY]BitMove{
                [_]BitMove{@bitCast(BitMove, @as(BitMoveType, 0))} ** MAX_PLY,
            } ** MAX_PLY;
            nodes = 0;

Replacement in src/Search.zig at line 68 [25.35]

B:BD[25.773] → [5.411:462]

        alpha = scr - 50;
        beta = scr + 50;

[25.773]

[5.462]

        // iterative deepening
        var current_depth: usize = 1;
        while (current_depth <= depth) : (current_depth += 1) {
            if (self.stopSearch()) break;
            pv_follow = true;

Replacement in src/Search.zig at line 74 [25.35]

∅:D[5.463] → [8.1053:1225]

B:BD[25.773] → [8.1053:1225]

        if (current_depth == depth) {
            try print_info(gs, scr, current_depth, true);
        } else {
            try print_info(gs, scr, current_depth, false);

[5.463]

[8.1225]

            const scr = try self.negamax(alpha, beta, current_depth);
            // ASPIRATION window: we fell out, so reset values and try again
            if (scr <= alpha or scr >= beta) {
                alpha = ALPHA;
                beta = BETA;
                current_depth -= 1;
                continue;
            }
            alpha = scr - 50;
            beta = scr + 50;
            try self.print_info(scr, current_depth);

Insertion in src/Search.zig at line 89 [25.35]

[8.1235]

[8.1791]


        // Print best move
        _ = try std.io.getStdOut().write(try std.fmt.allocPrint(
            self.state.allocator,
            "bestmove {s}{s}{s}\n",
            .{
                @tagName(pv_table[0][0].source),
                @tagName(pv_table[0][0].target),
                if (pv_table[0][0].prom != .none) @tagName(pv_table[0][0].prom) else "",
            },
        ));

Deletion in src/Search.zig at line 101 [25.35]
∅:D[16.962] → [25.1245:1247]
∅:D[8.1894] → [25.1245:1247]
∅:D[7.4570] → [25.1245:1247]
B:BD[25.1245] → [25.1245:1247]
```
}
```

Replacement in src/Search.zig at line 102 [25.35]

B:BD[4.1] → [4.1:27]

const NULL_REDUCTION = 2;

[4.1]

[25.1247]

    inline fn stopSearch(self: @This()) bool {
        if (@atomicLoad(bool, &self.stop, std.builtin.AtomicOrder.Unordered))
            return true
        else
            return false;
    }

Replacement in src/Search.zig at line 109 [25.35]

B:BD[25.1248] → [15.0:87]

∅:D[12.44] → [9.826:858]

B:BD[15.87] → [9.826:858]

fn negamax(gs: *GameState, alpha_orig: isize, beta: isize, depth_orig: usize) !isize {
    pv_length[gs.ply] = gs.ply;

[25.1248]

[9.858]

    fn negamax(self: *@This(), alpha_orig: isize, beta: isize, depth_orig: usize) !isize {
        if (self.stopSearch()) return 0;

Replacement in src/Search.zig at line 112 [25.35]

∅:D[9.859] → [15.87:163]

B:BD[15.87] → [15.87:163]

    if (depth_orig == 0) return try quiescenceSearch(gs, alpha_orig, beta);

[9.859]

[8.1895]

        pv_length[self.ply] = self.ply;

Replacement in src/Search.zig at line 114 [25.35]

B:BD[8.1896] → [8.1896:2004]

    // avoid overflow of ply arrays
    if (gs.ply > MAX_PLY - 1) {
        return EVAL_FUNCTION(gs);
    }

[8.1896]

[25.1401]

        if (depth_orig == 0) return try self.quiescenceSearch(alpha_orig, beta);

Replacement in src/Search.zig at line 116 [25.35]

B:BD[25.1402] → [25.1402:1430]

B:BD[25.1430] → [15.164:192]

    var alpha = alpha_orig;
    var depth = depth_orig;

[25.1402]

[25.1430]

        // avoid overflow of self.ply arrays
        if (self.ply > MAX_PLY - 1) {
            return EVAL_FUNCTION(self.state);
        }

Replacement in src/Search.zig at line 121 [25.35]

B:BD[25.1431] → [13.115:131]

    nodes += 1;

[25.1431]

[15.193]

        var alpha = alpha_orig;
        var depth = depth_orig;
        nodes += 1;

Replacement in src/Search.zig at line 126 [25.35]

B:BD[15.194] → [15.194:248]

B:BD[15.248] → [4.28:63]

∅:D[4.63] → [15.248:278]

B:BD[15.248] → [15.248:278]

    // increase search depth if king exposed to check
    const in_check = gs.inCheck();
    if (in_check) depth += 1;

[15.194]

[25.1780]

        // increase search depth if king exposed to check
        const in_check = self.state.inCheck();
        if (in_check) depth += 1;

Replacement in src/Search.zig at line 130 [25.35]
B:BD[25.1781] → [25.1781:1813]
```
    var legal_moves: usize = 0;
```
[25.1781]
[25.1884]
```
        var legal_moves: usize = 0;
```

Replacement in src/Search.zig at line 132 [25.35]

B:BD[25.1885] → [4.64:258]

    // NULL move pruning
    {
        if (depth >= 3 and !in_check and gs.ply != 0) {
            // backup board state
            var bck: GameState = undefined;
            gs.backup(&bck);

[25.1885]

[4.258]

        // NULL move pruning
        {
            if (depth >= 3 and !in_check and self.ply != 0) {
                // backup board state
                var bck: GameState = undefined;
                self.state.backup(&bck);

Replacement in src/Search.zig at line 139 [25.35]

B:BD[4.259] → [4.259:364]

            // prepare GameState
            gs.side = gs.side.enemy();
            gs.enpassant = null;

[4.259]

[4.364]

                // prepare GameState
                self.state.side = self.state.side.enemy();
                self.state.enpassant = null;

Replacement in src/Search.zig at line 143 [25.35]

B:BD[4.365] → [4.365:451]

            const s = -try negamax(gs, -beta, -beta + 1, depth - 1 - NULL_REDUCTION);

[4.365]

[4.451]

                const s = -try self.negamax(-beta, -beta + 1, depth - 1 - NULL_REDUCTION);

Replacement in src/Search.zig at line 145 [25.35]

B:BD[4.452] → [4.452:482]

            gs.restore(&bck);

[4.452]

[4.482]

                self.state.restore(&bck);

Replacement in src/Search.zig at line 147 [25.35]

B:BD[4.483] → [4.483:541]

            if (s >= beta) {
                return beta;

[4.483]

[4.541]

                if (s >= beta) {
                    return beta;
                }

Deletion in src/Search.zig at line 152 [25.35]
B:BD[4.565] → [4.565:571]
```
    }
```
Replacement in src/Search.zig at line 153 [25.35]
∅:D[4.572] → [17.114:149]
B:BD[25.1885] → [17.114:149]
∅:D[17.149] → [25.1920:1951]
∅:D[14.488] → [25.1920:1951]
B:BD[25.1920] → [25.1920:1951]
B:BD[25.1951] → [3.58:84]
```
    var ml = try MoveList.init(0);
    try gs.generateMoves(&ml);
    score.moves(gs, &ml);
```
[4.572]
[3.84]
```
        var ml = try MoveList.init(0);
        try self.state.generateMoves(&ml);
        score.moves(self, &ml);
```

Replacement in src/Search.zig at line 157 [25.35]

B:BD[3.85] → [3.85:397]

    // Honor following the PV line
    if (pv_follow) {
        pv_follow = false;
        for (ml.slice()) |*mp| {
            if (@bitCast(BitMoveType, pv_table[0][gs.ply]) == @bitCast(BitMoveType, mp.move)) {
                pv_follow = true;
                mp.score = score.PV_SCORE;
                break;

[3.85]

[3.397]

        // Honor following the PV line
        if (pv_follow) {
            pv_follow = false;
            for (ml.slice()) |*mp| {
                if (@bitCast(BitMoveType, pv_table[0][self.ply]) == @bitCast(BitMoveType, mp.move)) {
                    pv_follow = true;
                    mp.score = score.PV_SCORE;
                    break;
                }

Deletion in src/Search.zig at line 168 [25.35]
B:BD[3.421] → [3.421:427]
```
    }
```

Replacement in src/Search.zig at line 169 [25.35]

∅:D[3.428] → [17.150:223]

B:BD[25.1951] → [17.150:223]

    std.sort.sort(MovePrio, ml.slice(), {}, comptime MovePrio.moreThan);

[3.428]

[25.1951]

        std.sort.sort(MovePrio, ml.slice(), {}, comptime MovePrio.moreThan);

Replacement in src/Search.zig at line 171 [25.35]

B:BD[25.1952] → [27.80:115]

∅:D[27.115] → [17.224:252]

B:BD[25.1952] → [17.224:252]

∅:D[17.252] → [25.1987:2052]

∅:D[14.526] → [25.1987:2052]

B:BD[25.1987] → [25.1987:2052]

    var moves_searched: usize = 0;
    for (ml.slice()) |mp| {
        var bck: GameState = undefined;
        gs.backup(&bck);

[25.1952]

[25.2052]

        var moves_searched: usize = 0;
        for (ml.slice()) |mp| {
            var bck: GameState = undefined;
            self.state.backup(&bck);

Replacement in src/Search.zig at line 176 [25.35]

B:BD[25.2053] → [25.2053:2074]

B:BD[25.2074] → [14.527:570]

∅:D[14.570] → [25.2114:2201]

B:BD[25.2114] → [25.2114:2201]

        gs.ply += 1;
        if (!gs.makeMove(mp.move, .all)) {
            gs.ply -= 1;
            gs.restore(&bck);
            continue;
        }

[25.2053]

[25.2201]

            self.ply += 1;
            if (!self.state.makeMove(mp.move, .all)) {
                self.ply -= 1;
                self.state.restore(&bck);
                continue;
            }

Replacement in src/Search.zig at line 183 [25.35]
B:BD[25.2202] → [25.2202:2228]
```
        legal_moves += 1;
```
[25.2202]
[25.2228]
```
            legal_moves += 1;
```

Replacement in src/Search.zig at line 185 [25.35]

B:BD[25.2229] → [27.116:152]

B:BD[27.152] → [6.0:142]

∅:D[6.142] → [27.1135:1152]

B:BD[27.1135] → [27.1135:1152]

B:BD[27.1152] → [6.143:535]

        var scr: isize = undefined;
        // Normal negamax without PVS or LMR
        if (moves_searched == 0) {
            scr = -try negamax(gs, -beta, -alpha, depth - 1);
        } else {
            // Conditions to consider LMR
            if (moves_searched >= FULL_DEPTH_MOVES and
                gs.ply >= REDUCTION_LIMIT and
                !mp.move.capture and mp.move.prom == .none and
                !gs.inCheck())
            {
                // reduced-depth, narrow score search for lame moves
                scr = -try negamax(gs, -alpha - 1, -alpha, depth -| 3);

[25.2229]

[27.1299]

            var scr: isize = undefined;
            // Normal negamax without PVS or LMR
            if (moves_searched == 0) {
                scr = -try self.negamax(-beta, -alpha, depth - 1);

Replacement in src/Search.zig at line 190 [25.35]

B:BD[27.1320] → [6.536:654]

                // hack to ensure that we continue with PVS code below
                scr = alpha + 1;
            }

[27.1320]

[27.1867]

                // Conditions to consider LMR
                if (moves_searched >= FULL_DEPTH_MOVES and
                    self.ply >= REDUCTION_LIMIT and
                    !mp.move.capture and mp.move.prom == .none and
                    !self.state.inCheck())
                {
                    // reduced-depth, narrow score search for lame moves
                    scr = -try self.negamax(-alpha - 1, -alpha, depth -| 3);
                } else {
                    // hack to ensure that we continue with PVS code below
                    scr = alpha + 1;
                }

Replacement in src/Search.zig at line 203 [25.35]

B:BD[27.1868] → [6.655:1131]

            // Continue PVS code
            if (scr > alpha) {
                // Once you've found a move with a score that is between alpha and beta,
                // the rest of the moves are searched with the goal of proving that they are all bad.
                // It's possible to do this a bit faster than a search that worries that one
                // of the remaining moves might be good.
                scr = -try negamax(gs, -alpha - 1, -alpha, depth - 1);

[27.1868]

[27.2080]

                // Continue PVS code
                if (scr > alpha) {
                    // Once you've found a move with a score that is between alpha and beta,
                    // the rest of the moves are searched with the goal of proving that they are all bad.
                    // It's possible to do this a bit faster than a search that worries that one
                    // of the remaining moves might be good.
                    scr = -try self.negamax(-alpha - 1, -alpha, depth - 1);

Replacement in src/Search.zig at line 211 [25.35]

B:BD[27.2081] → [6.1132:1697]

                // If the algorithm finds out that it was wrong, and that one of the
                // subsequent moves was better than the first PV move, it has to search again,
                // in the normal alpha-beta manner.  This happens sometimes, and it's a waste of time,
                // but generally not often enough to counteract the savings gained from doing the
                // "bad move proof" search referred to earlier.
                if (scr > alpha and scr < beta) {
                    scr = -try negamax(gs, -beta, -alpha, depth - 1);

[27.2081]

[12.1211]

                    // If the algorithm finds out that it was wrong, and that one of the
                    // subsequent moves was better than the first PV move, it has to search again,
                    // in the normal alpha-beta manner.  This happens sometimes, and it's a waste of time,
                    // but generally not often enough to counteract the savings gained from doing the
                    // "bad move proof" search referred to earlier.
                    if (scr > alpha and scr < beta) {
                        scr = -try self.negamax(-beta, -alpha, depth - 1);
                    }

Replacement in src/Search.zig at line 221 [25.35]

B:BD[12.1381] → [27.2285:2295]

[12.1381]

[25.2295]


            self.ply -= 1;
            self.state.restore(&bck);
            moves_searched += 1;

Replacement in src/Search.zig at line 226 [25.35]

B:BD[25.2296] → [25.2296:2343]

B:BD[25.2343] → [27.2296:2325]

        gs.ply -= 1;
        gs.restore(&bck);
        moves_searched += 1;

[25.2296]

[25.2343]

            // fail-hard beta cutoff
            if (scr >= beta) {
                // store killer moves
                if (!mp.move.capture) {
                    score.killer_moves[1][self.ply] = score.killer_moves[0][self.ply];
                    score.killer_moves[0][self.ply] = mp.move;
                }

Replacement in src/Search.zig at line 234 [25.35]

B:BD[25.2344] → [25.2344:2377]

B:BD[25.2377] → [9.925:1158]

        // fail-hard beta cutoff
        if (scr >= beta) {
            // store killer moves
            if (!mp.move.capture) {
                score.killer_moves[1][gs.ply] = score.killer_moves[0][gs.ply];
                score.killer_moves[0][gs.ply] = mp.move;

[25.2344]

[9.1158]

                // node (move) fails high
                return beta;

Replacement in src/Search.zig at line 238 [25.35]

∅:D[9.1173] → [25.2406:2479]

B:BD[25.2406] → [25.2406:2479]

            // node (move) fails high
            return beta;
        }

[9.1173]

[25.2479]

            // found a better move
            if (scr > alpha) {
                // store history moves
                if (!mp.move.capture) {
                    score.history_moves[@enumToInt(mp.move.piece)][@enumToInt(mp.move.target)] += depth;
                }

Replacement in src/Search.zig at line 245 [25.35]

B:BD[25.2480] → [25.2480:2511]

B:BD[25.2511] → [9.1174:1387]

        // found a better move
        if (scr > alpha) {
            // store history moves
            if (!mp.move.capture) {
                score.history_moves[@enumToInt(mp.move.piece)][@enumToInt(mp.move.target)] += depth;
            }

[25.2480]

[9.1387]

                // PV (principal valuation) node
                alpha = scr;

Replacement in src/Search.zig at line 248 [25.35]

B:BD[9.1388] → [9.1388:1458]

            // PV (principal valuation) node
            alpha = scr;

[9.1388]

[9.1458]

                {
                    // write PV move
                    pv_table[self.ply][self.ply] = mp.move;

Replacement in src/Search.zig at line 252 [25.35]

B:BD[9.1459] → [9.1459:1558]

            {
                // write PV move
                pv_table[gs.ply][gs.ply] = mp.move;

[9.1459]

[9.1558]

                    // copy move from deeper self.ply into the current self.ply's line
                    var next: usize = self.ply + 1;
                    while (next < pv_length[self.ply + 1]) : (next += 1) {
                        pv_table[self.ply][next] = pv_table[self.ply + 1][next];
                    }

Replacement in src/Search.zig at line 258 [25.35]

B:BD[9.1559] → [9.1559:1820]

                // copy move from deeper ply into the current ply's line
                var next: usize = gs.ply + 1;
                while (next < pv_length[gs.ply + 1]) : (next += 1) {
                    pv_table[gs.ply][next] = pv_table[gs.ply + 1][next];

[9.1559]

[9.1820]

                    // adjust pv_length
                    pv_length[self.ply] = pv_length[self.ply + 1];

Deletion in src/Search.zig at line 261 [25.35]
∅:D[9.1838] → [25.2613:2614]
B:BD[25.2613] → [25.2613:2614]
B:BD[25.2614] → [9.1839:1934]
```
                // adjust pv_length
                pv_length[gs.ply] = pv_length[gs.ply + 1];
```
Deletion in src/Search.zig at line 263 [25.35]
B:BD[25.2739] → [25.2739:2745]
```
    }
```

Replacement in src/Search.zig at line 264 [25.35]

B:BD[25.2746] → [25.2746:3024]

    // Detect check- and stalemate
    if (legal_moves == 0) {
        if (in_check) {
            // Adding ply helps the engine finding fastest mates.
            return eval.CHECKMATE_SCORE + @intCast(isize, gs.ply);
        } else {
            return eval.STALEMATE_SCORE;

[25.2746]

[25.3024]

        // Detect check- and stalemate
        if (legal_moves == 0) {
            if (in_check) {
                // Adding self.ply helps the engine finding fastest mates.
                return eval.CHECKMATE_SCORE + @intCast(isize, self.ply);
            } else {
                return eval.STALEMATE_SCORE;
            }

Deletion in src/Search.zig at line 273 [25.35]

B:BD[25.3034] → [25.3034:3041]

B:BD[25.3140] → [25.3140:3422]

B:BD[25.3422] → [13.132:149]

B:BD[13.149] → [2.130:172]

∅:D[2.172] → [25.3464:3585]

∅:D[13.191] → [25.3464:3585]

∅:D[14.652] → [25.3464:3585]

B:BD[25.3464] → [25.3464:3585]

    }
    // node (move) fails low
    return alpha;
}
// quiescenceSearch helps the engine not thow away its pieces because of
// a temporary seemingly good move. (Horizon effect)
fn quiescenceSearch(gs: *GameState, alpha_orig: isize, beta: isize) !isize {
    var alpha = alpha_orig;
    nodes += 1;
    const evaluation = EVAL_FUNCTION(gs);
    // fail-hard beta cutoff
    if (evaluation >= beta) {
        // node (move) fails high
        return beta;
    }

Replacement in src/Search.zig at line 274 [25.35]

B:BD[25.3586] → [25.3586:3713]

    // found a better move
    if (evaluation > alpha) {
        // PV (principal validation) node
        alpha = evaluation;

[25.3586]

[25.3713]

        // node (move) fails low
        return alpha;

Replacement in src/Search.zig at line 278 [25.35]

B:BD[25.3720] → [17.253:288]

∅:D[17.288] → [25.3755:3786]

∅:D[14.722] → [25.3755:3786]

B:BD[25.3755] → [25.3755:3786]

B:BD[25.3786] → [3.429:455]

∅:D[3.455] → [17.289:362]

B:BD[25.3786] → [17.289:362]

    var ml = try MoveList.init(0);
    try gs.generateMoves(&ml);
    score.moves(gs, &ml);
    std.sort.sort(MovePrio, ml.slice(), {}, comptime MovePrio.moreThan);

[25.3720]

[25.3786]

    // quiescenceSearch helps the engine not thow away its pieces because of
    // a temporary seemingly good move. (Horizon effect)
    fn quiescenceSearch(self: *@This(), alpha_orig: isize, beta: isize) !isize {
        if (self.stopSearch()) return 0;

Replacement in src/Search.zig at line 283 [25.35]
B:BD[25.3787] → [17.363:391]
∅:D[17.391] → [25.3817:3882]
∅:D[14.760] → [25.3817:3882]
B:BD[25.3817] → [25.3817:3882]
```
    for (ml.slice()) |mp| {
        var bck: GameState = undefined;
        gs.backup(&bck);
```
[25.3787]
[25.3882]
```
        var alpha = alpha_orig;
```

Replacement in src/Search.zig at line 285 [25.35]

B:BD[25.3883] → [25.3883:3904]

B:BD[25.3904] → [14.761:809]

∅:D[14.809] → [25.3949:4037]

B:BD[25.3949] → [25.3949:4037]

B:BD[25.4037] → [9.1935:1997]

        gs.ply += 1;
        if (!gs.makeMove(mp.move, .captures)) {
            gs.ply -= 1;
            gs.restore(&bck);
            continue;
        }
        const scr = -try quiescenceSearch(gs, -beta, -alpha);

[25.3883]

[25.4101]

        nodes += 1;

Replacement in src/Search.zig at line 287 [25.35]

B:BD[25.4102] → [25.4102:4149]

        gs.ply -= 1;
        gs.restore(&bck);

[25.4102]

[25.4149]

        const evaluation = EVAL_FUNCTION(self.state);

Replacement in src/Search.zig at line 290 [25.35]
B:BD[25.4183] → [9.1998:2025]
```
        if (scr >= beta) {
```
[25.4183]
[25.4212]
```
        if (evaluation >= beta) {
```
Replacement in src/Search.zig at line 296 [25.35]
B:BD[25.4317] → [9.2026:2053]
```
        if (scr > alpha) {
```
[25.4317]
[25.4346]
```
        if (evaluation > alpha) {
```
Replacement in src/Search.zig at line 298 [25.35]
B:BD[25.4392] → [9.2054:2079]
```
            alpha = scr;
```
[25.4392]
[25.4419]
```
            alpha = evaluation;
```

Replacement in src/Search.zig at line 300 [25.35]

B:BD[25.4429] → [25.4429:4435]

[25.4429]

[25.4435]


        var ml = try MoveList.init(0);
        try self.state.generateMoves(&ml);
        score.moves(self, &ml);
        std.sort.sort(MovePrio, ml.slice(), {}, comptime MovePrio.moreThan);

Replacement in src/Search.zig at line 306 [25.35]

B:BD[25.4436] → [25.4436:4483]

B:BD[25.4483] → [8.2005:2007]

    // node (move) fails low
    return alpha;
}

[25.4436]

[8.2007]

        for (ml.slice()) |mp| {
            var bck: GameState = undefined;
            self.state.backup(&bck);

Replacement in src/Search.zig at line 310 [25.35]

B:BD[8.2008] → [8.2008:2166]

fn print_info(gs: *const GameState, scr: isize, depth: usize, best: bool) !void {
    var ret = std.ArrayList(u8).init(gs.allocator);
    defer ret.deinit();

[8.2008]

[8.2166]

            self.ply += 1;
            if (!self.state.makeMove(mp.move, .captures)) {
                self.ply -= 1;
                self.state.restore(&bck);
                continue;
            }
            const scr = -try self.quiescenceSearch(-beta, -alpha);
            self.ply -= 1;
            self.state.restore(&bck);
            // fail-hard beta cutoff
            if (scr >= beta) {
                // node (move) fails high
                return beta;
            }

Replacement in src/Search.zig at line 328 [25.35]

B:BD[8.2167] → [8.2167:2353]

    const info = try std.fmt.allocPrint(
        gs.allocator,
        "info score cp {d} depth {d} nodes {d} pv ",
        .{ scr, depth, nodes },
    );
    try ret.appendSlice(info);

[8.2167]

[8.2353]

            // found a better move
            if (scr > alpha) {
                // PV (principal validation) node
                alpha = scr;
            }
        }

Replacement in src/Search.zig at line 335 [25.35]

B:BD[8.2354] → [8.2354:2719]

    // loop over the pv_line
    var count: usize = 0;
    while (count < pv_length[0]) : (count += 1) {
        // print PV move
        const m = pv_table[0][count];
        const move = try std.fmt.allocPrint(
            gs.allocator,
            "{s}{s} ",
            .{ @tagName(m.source), @tagName(m.target) },
        );
        try ret.appendSlice(move);

[8.2354]

[8.2719]

        // node (move) fails low
        return alpha;

Deletion in src/Search.zig at line 338 [25.35]
B:BD[8.2725] → [8.2725:2751]
```
    try ret.append('\n');
```

Replacement in src/Search.zig at line 339 [25.35]

B:BD[8.2752] → [8.2752:3089]

    if (best) {
        const bestmove = try std.fmt.allocPrint(gs.allocator, "bestmove {s}{s}{s}\n", .{
            @tagName(pv_table[0][0].source),
            @tagName(pv_table[0][0].target),
            if (pv_table[0][0].prom != .none) @tagName(pv_table[0][0].prom) else "",
        });
        try ret.appendSlice(bestmove);
    }

[8.2752]

[8.3089]

    fn print_info(self: @This(), scr: isize, depth: usize) !void {
        var ret = std.ArrayList(u8).init(self.state.allocator);
        defer ret.deinit();

Replacement in src/Search.zig at line 343 [25.35]

B:BD[8.3090] → [8.3090:3139]

∅:D[8.3139] → [25.4483:4485]

B:BD[25.4483] → [25.4483:4485]

    _ = try std.io.getStdOut().write(ret.items);
}

[8.3090]

[14.810]

        const info = try std.fmt.allocPrint(
            self.state.allocator,
            "info score cp {d} depth {d} nodes {d} pv ",
            .{ scr, depth, nodes },
        );
        try ret.appendSlice(info);

Replacement in src/Search.zig at line 350 [25.35]

B:BD[14.811] → [14.811:957]

test "bestMove" {
    var gs = try GameState.init(std.testing.allocator, null);
    gs.show();
    std.debug.print("{s}", .{bestMove(&gs, 4)});
}

[14.811]

        // loop over the pv_line
        var count: usize = 0;
        while (count < pv_length[0]) : (count += 1) {
            // print PV move
            const m = pv_table[0][count];
            const move = try std.fmt.allocPrint(
                self.state.allocator,
                "{s}{s} ",
                .{ @tagName(m.source), @tagName(m.target) },
            );
            try ret.appendSlice(move);
        }
        try ret.append('\n');
        _ = try std.io.getStdOut().write(ret.items);
    }
};

Insertion in src/Board.zig at line 7 [28.16071]
[23.35371]
[28.16210]
```
const Search = @import("Search").Search;
```
Deletion in src/Board.zig at line 205 [28.16071]
∅:D[29.183] → [30.36:56]
B:BD[30.36] → [30.36:56]
```
    ply: usize = 0,
```