voroskoi/pistike - Change R5F5KMWWZ4VS67CSIWRNRM4LNPPXVXSQZLHEZMT6XZODV4AK2MBQC

Implement iterative deepening

Created by voroskoi on January 23, 2023

R5F5KMWWZ4VS67CSIWRNRM4LNPPXVXSQZLHEZMT6XZODV4AK2MBQC

Dependencies

In channels

main

Change contents

Replacement in src/uci.zig at line 11 [4.32]

B:BD[4.310] → [4.310:357]

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

[4.310]

[4.357]

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

Replacement in src/uci.zig at line 15 [4.32]

B:BD[4.509] → [4.509:552]

        return search.bestMove(gs, depth);

[4.509]

[4.552]

        try search.bestMove(gs, depth);

Replacement in src/uci.zig at line 19 [4.32]
B:BD[4.599] → [4.599:634]
```
    return search.bestMove(gs, 6);
```
[4.599]
[4.634]
```
    try search.bestMove(gs, 6);
```
Replacement in src/search.zig at line 21 [5.35]
B:BD[5.525] → [6.0:22]
```
var nodes: usize = 0;
```
[5.496]
[5.525]
```
// Maximum ply we can reach while searching
const MAX_PLY = 64;
```

Replacement in src/search.zig at line 24 [5.35]

B:BD[5.526] → [7.37:195]

var pv_length: [64]usize = [_]usize{0} ** 64;
var pv_table: [64][64]BitMove = [_][64]BitMove{[_]BitMove{@bitCast(BitMove, @as(BitMoveType, 0))} ** 64} ** 64;

[5.526]

[7.195]

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

Replacement in src/search.zig at line 29 [5.35]

B:BD[7.196] → [2.0:53]

pub fn bestMove(gs: *GameState, depth: usize) !Str {

[7.196]

[5.580]

pub fn bestMove(gs: *GameState, depth: usize) !void {

Replacement in src/search.zig at line 33 [5.35]

B:BD[5.629] → [2.54:107]

    const scr = try negamax(gs, ALPHA, BETA, depth);

[5.629]

[5.698]

    // 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 46 [5.35]

B:BD[5.699] → [2.108:184]

    var ret = std.ArrayList(u8).init(gs.allocator);
    defer ret.deinit();

[5.699]

[2.184]

    // iterative deepening
    var current_depth: usize = 1;
    while (current_depth <= depth) : (current_depth += 1) {
        nodes = 0; // TODO: remove

Replacement in src/search.zig at line 51 [5.35]

B:BD[2.185] → [2.185:371]

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

[2.185]

[5.772]

        const scr = try negamax(gs, ALPHA, BETA, current_depth);

Replacement in src/search.zig at line 53 [5.35]

B:BD[5.773] → [7.354:484]

B:BD[7.484] → [2.372:607]

    // 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);

[5.773]

[7.555]

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

Deletion in src/search.zig at line 59 [5.35]
B:BD[7.561] → [2.608:634]
```
    try ret.append('\n');
```

Replacement in src/search.zig at line 60 [5.35]

B:BD[7.562] → [2.635:926]

    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);

[7.562]

[7.594]

    // TO BE REMOVED BELOW THIS LINE...
    // ---------------------------------------------------- //
    // 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 75 [5.35]

B:BD[7.595] → [2.927:962]

    return try ret.toOwnedSlice();

[7.595]

[5.1245]

    const scr = try negamax(gs, ALPHA, BETA, depth);
    try print_info(gs, scr, depth, true);

Insertion in src/search.zig at line 84 [5.35]

[8.163]

[5.1401]


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

Insertion in src/search.zig at line 237 [5.35]

[5.4483]

}
fn print_info(gs: *const GameState, scr: isize, depth: usize, best: bool) !void {
    var ret = std.ArrayList(u8).init(gs.allocator);
    defer ret.deinit();
    const info = try std.fmt.allocPrint(
        gs.allocator,
        "info score cp {d} depth {d} nodes {d} pv ",
        .{ scr, depth, nodes },
    );
    try ret.appendSlice(info);
    // 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);
    }
    try ret.append('\n');
    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);
    }
    _ = try std.io.getStdOut().write(ret.items);

Replacement in src/score.zig at line 7 [7.2114]
B:BD[7.2330] → [7.2330:2381]
```
// This value is arbitrary
const KILLER_MAX = 64;
```
[7.2330]
[7.2381]
```
const Square = @import("Board.zig").Square;
```

Insertion in src/score.zig at line 14 [7.2114]

[7.2534]

// Killer moves [first/second][MAX_PLY]
pub var killer_moves: [2][64]BitMove = undefined;
// History moves [piece][square]
pub var history_moves: [@typeInfo(Chess.PE).Enum.fields.len - 1][@typeInfo(Square).Enum.fields.len]usize = undefined;

Replacement in src/score.zig at line 38 [7.2114]

B:BD[7.3182] → [7.3182:3319]

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

[7.3182]

[7.3319]

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

Replacement in src/score.zig at line 43 [7.2114]

B:BD[7.3396] → [7.3396:3538]

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

[7.3396]

[7.3538]

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

Deletion in src/score.zig at line 86 [7.2114]

B:BD[7.5182] → [7.5182:5471]


// Killer moves
pub var killer_moves: [2][KILLER_MAX]BitMove = .{
    [_]BitMove{@bitCast(BitMove, @as(BitMoveType, 0))} ** KILLER_MAX,
    [_]BitMove{@bitCast(BitMove, @as(BitMoveType, 0))} ** KILLER_MAX,
};
pub var history_moves: [12][64]usize = [_][64]usize{[_]usize{0} ** 64} ** 12;

Replacement in src/main.zig at line 22 [10.50]

B:BD[9.1531] → [2.963:1027]

        std.debug.print("{s}", .{try search.bestMove(&gs, 5)});

[9.1531]

[9.1797]

        // var ml = try Board.MoveList.init(0);
        // try gs.generateMoves(&ml);
        // std.sort.sort(Board.MovePrio, ml.slice(), {}, comptime Board.MovePrio.moreThan);
        // for (ml.slice()) |mp| {
        //     mp.move.show();
        //     std.debug.print("{d}\n", .{mp.score});
        // }
        try search.bestMove(&gs, 5);

Replacement in src/main.zig at line 40 [10.50]

B:BD[11.81] → [11.81:129]

    const stdout = std.io.getStdOut().writer();

[11.81]

[11.129]

    const stdout = std.io.getStdOut();

Replacement in src/main.zig at line 67 [10.50]

B:BD[11.959] → [4.4725:4780]

∅:D[4.4780] → [11.1008:1051]

B:BD[11.1008] → [11.1008:1051]

                var res = try uci.parseGo(&gs, input);
                _ = try stdout.write(res);

[11.959]

[11.1051]

                try uci.parseGo(&gs, input);

Insertion in README.md at line 101 [12.34]

[3.1872]

    - [Iterative Deepening](https://www.chessprogramming.org/Iterative_Deepening)