voroskoi/pistike - Change XRCSCQWQKVYASIMAJO7JVUJXHXE44FZROCJPBW2BR7EE4RPEIBKAC

Implement killer and history moves, add pv_table

Created by voroskoi on January 22, 2023

XRCSCQWQKVYASIMAJO7JVUJXHXE44FZROCJPBW2BR7EE4RPEIBKAC

Dependencies

In channels

main

Change contents

Insertion in src/search.zig at line 16 [4.35]
[4.495]
[4.495]
```
const score = @import("score.zig");
```

Insertion in src/search.zig at line 21 [4.35]

[4.526]

[5.4449]

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

Replacement in src/search.zig at line 28 [4.35]

B:BD[4.629] → [4.629:698]

    const score = negamax(gs, ALPHA, BETA, depth) catch unreachable;

[4.629]

[4.698]

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

Replacement in src/search.zig at line 30 [4.35]

B:BD[4.699] → [6.23:114]

    std.debug.print("info score cp {d} depth {d} nodes: {d}\n", .{ score, depth, nodes });

[4.699]

[4.772]

    std.debug.print("info score cp {d} depth {d} nodes: {d} ", .{ scr, depth, nodes });

Replacement in src/search.zig at line 32 [4.35]

B:BD[4.773] → [4.773:825]

    if (@bitCast(BitMoveType, gs.best_move) != 0) {

[4.773]

[4.825]

    // loop over the pv_line
    var count: usize = 0;
    while (count < pv_length[0]) : (count += 1) {
        // print PV move
        pv_table[0][count].print();
        std.debug.print(" ", .{});
    }
    std.debug.print("\n", .{});
    if (@bitCast(BitMoveType, pv_table[0][0]) != 0) {

Replacement in src/search.zig at line 44 [4.35]

B:BD[4.890] → [4.890:1057]

            @tagName(gs.best_move.source),
            @tagName(gs.best_move.target),
            if (gs.best_move.prom != .none) @tagName(gs.best_move.prom) else "",

[4.890]

[4.1057]

            @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 "",

Insertion in src/search.zig at line 52 [4.35]
[7.87]
[7.87]
```
    pv_length[gs.ply] = gs.ply;
```

Deletion in src/search.zig at line 72 [4.35]

B:BD[4.1813] → [4.1813:1884]


    var best_sofar: BitMove = @bitCast(BitMove, @as(BitMoveType, 0));

Replacement in src/search.zig at line 90 [4.35]

B:BD[4.2229] → [4.2229:2295]

        const score = -try negamax(gs, -beta, -alpha, depth - 1);

[4.2229]

[4.2295]

        const scr = -try negamax(gs, -beta, -alpha, depth - 1);

Replacement in src/search.zig at line 96 [4.35]

B:BD[4.2377] → [4.2377:2406]

        if (score >= beta) {

[4.2377]

[4.2406]

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

Replacement in src/search.zig at line 108 [4.35]

B:BD[4.2511] → [4.2511:2613]

        if (score > alpha) {
            // PV (principal validation) node
            alpha = score;

[4.2511]

[4.2613]

        if (scr > alpha) {
            // store history moves
            if (!mp.move.capture) {
                score.history_moves[@enumToInt(mp.move.piece)][@enumToInt(mp.move.target)] += depth;
            }
            // PV (principal valuation) node
            alpha = scr;
            {
                // write PV move
                pv_table[gs.ply][gs.ply] = mp.move;
                // 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];
                }

Replacement in src/search.zig at line 127 [4.35]

B:BD[4.2614] → [4.2614:2673]

B:BD[4.2673] → [8.571:609]

            // if root move
            if (gs.ply == 0) {
                best_sofar = mp.move;

[4.2614]

[4.2715]

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

Deletion in src/search.zig at line 143 [4.35]

B:BD[4.3041] → [4.3041:3140]

    if (alpha_orig != alpha) {
        // init best move
        gs.best_move = best_sofar;
    }

Replacement in src/search.zig at line 183 [4.35]

B:BD[4.4037] → [4.4037:4101]

        const score = -try quiescenceSearch(gs, -beta, -alpha);

[4.4037]

[4.4101]

        const scr = -try quiescenceSearch(gs, -beta, -alpha);

Replacement in src/search.zig at line 189 [4.35]
B:BD[4.4183] → [4.4183:4212]
```
        if (score >= beta) {
```
[4.4183]
[4.4212]
```
        if (scr >= beta) {
```
Replacement in src/search.zig at line 195 [4.35]
B:BD[4.4317] → [4.4317:4346]
```
        if (score > alpha) {
```
[4.4317]
[4.4346]
```
        if (scr > alpha) {
```
Replacement in src/search.zig at line 197 [4.35]
B:BD[4.4392] → [4.4392:4419]
```
            alpha = score;
```
[4.4392]
[4.4419]
```
            alpha = scr;
```

File addition: score.zig (----------)

[9.15]

const std = @import("std");
const Chess = @import("Chess.zig");
const BitMove = @import("Board.zig").BitMove;
const BitMoveType = @import("Board.zig").BitMoveType;
const GameState = @import("Board.zig").GameState;
// This value is arbitrary
const KILLER_MAX = 64;
// These values are arbitrary, but only decreasing makes sense.
const CAPTURE_BOOST = 10_000;
const KILLER_FIRST = 9_000;
const KILLER_SECOND = 8_000;
pub fn Move(gs: *const GameState, move: BitMove) isize {
    if (move.capture) {
        var target_piece = Chess.PE.P; // this could be p as well
        const pieces = switch (gs.side) {
            .white => &[_]Chess.PE{ .p, .n, .b, .r, .q, .k },
            .black => &[_]Chess.PE{ .P, .N, .B, .R, .Q, .K },
        };
        for (pieces) |piece| {
            if (gs.bitboards[@enumToInt(piece)].isSet(move.target)) {
                target_piece = piece;
                break;
            }
        }
        return MVV_LVA[@enumToInt(move.piece)][@enumToInt(target_piece)] + CAPTURE_BOOST;
    } else {
        // score 1st killer move
        if (gs.ply < KILLER_MAX and
            @bitCast(BitMoveType, killer_moves[0][gs.ply]) == @bitCast(BitMoveType, move))
        {
            return KILLER_FIRST;
        }
        // score 2nd killer move
        else if (gs.ply < KILLER_MAX and
            @bitCast(BitMoveType, killer_moves[1][gs.ply]) == @bitCast(BitMoveType, move))
        {
            return KILLER_SECOND;
        }
        // score history moves
        else {
            return @intCast(
                isize,
                history_moves[@enumToInt(move.piece)][@enumToInt(move.target)],
            );
        }
        return 0;
    }
    return 0;
}
// most valuable victim & less valuable attacker
//    (Victims) Pawn Knight Bishop   Rook  Queen   King
//  (Attackers)
//        Pawn   105    205    305    405    505    605
//      Knight   104    204    304    404    504    604
//      Bishop   103    203    303    403    503    603
//        Rook   102    202    302    402    502    602
//       Queen   101    201    301    401    501    601
//        King   100    200    300    400    500    600
// MVV LVA [attacker][victim]
const MVV_LVA: [12][12]isize = .{
    .{ 105, 205, 305, 405, 505, 605, 105, 205, 305, 405, 505, 605 },
    .{ 104, 204, 304, 404, 504, 604, 104, 204, 304, 404, 504, 604 },
    .{ 103, 203, 303, 403, 503, 603, 103, 203, 303, 403, 503, 603 },
    .{ 102, 202, 302, 402, 502, 602, 102, 202, 302, 402, 502, 602 },
    .{ 101, 201, 301, 401, 501, 601, 101, 201, 301, 401, 501, 601 },
    .{ 100, 200, 300, 400, 500, 600, 100, 200, 300, 400, 500, 600 },
    .{ 105, 205, 305, 405, 505, 605, 105, 205, 305, 405, 505, 605 },
    .{ 104, 204, 304, 404, 504, 604, 104, 204, 304, 404, 504, 604 },
    .{ 103, 203, 303, 403, 503, 603, 103, 203, 303, 403, 503, 603 },
    .{ 102, 202, 302, 402, 502, 602, 102, 202, 302, 402, 502, 602 },
    .{ 101, 201, 301, 401, 501, 601, 101, 201, 301, 401, 501, 601 },
    .{ 100, 200, 300, 400, 500, 600, 100, 200, 300, 400, 500, 600 },
};
// 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;

Insertion in src/main.zig at line 17 [9.50]

[3.969]

            // "rnbqkb1r/pp1p1pPp/8/2p1pP2/1P1P4/3P3P/P1P1P3/RNBQKBNR w KQkq e6 0 1" // killer

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

B:BD[8.1531] → [3.1068:1128]

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

[8.1531]

[8.1797]

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

Insertion in src/Board.zig at line 7 [10.16071]
[2.35371]
[10.16210]
```
const score = @import("score.zig");
```

Insertion in src/Board.zig at line 145 [10.16071]

[11.1072]

[10.19744]

    pub fn print(self: @This()) void {
        std.debug.print("{s}{s}", .{
            @tagName(self.source),
            @tagName(self.target),
        });
    }

Deletion in src/Board.zig at line 211 [10.16071]
B:BD[10.20370] → [12.118:183]
```
    best_move: BitMove = @bitCast(BitMove, @as(BitMoveType, 0)),
```

Deletion in src/Board.zig at line 462 [10.16071]

B:BD[10.30262] → [13.3292:3544]

                .N, .n => try self.genMoves(ml, board, piece),
                .B, .b => try self.genMoves(ml, board, piece),
                .R, .r => try self.genMoves(ml, board, piece),
                .Q, .q => try self.genMoves(ml, board, piece),

Insertion in src/Board.zig at line 463 [10.16071]

[10.30536]

                else => try self.genMoves(ml, board, piece),

Insertion in src/Board.zig at line 514 [10.16071]
[10.32431]
[10.32431]
```
                // promotion
```

Replacement in src/Board.zig at line 523 [10.16071]

B:BD[8.3313] → [3.1384:1480]

                        try ml.append(MovePrio{ .move = move, .score = self.scoreMove(move) });

[8.3313]

[10.32838]

                        try ml.append(MovePrio{ .move = move, .score = score.Move(self, move) });

Insertion in src/Board.zig at line 527 [10.16071]

[8.3429]

                        // single pawn move

Replacement in src/Board.zig at line 533 [10.16071]

B:BD[8.3692] → [3.1481:1570]

                        try ml.append(.{ .move = move, .score = self.scoreMove(move) });

[8.3692]

[8.3778]

                        try ml.append(.{ .move = move, .score = score.Move(self, move) });

Insertion in src/Board.zig at line 536 [10.16071]
[10.33139]
[10.33220]
```
                    // double pawn move
```

Replacement in src/Board.zig at line 548 [10.16071]

B:BD[8.3875] → [3.1571:1660]

                        try ml.append(.{ .move = move, .score = self.scoreMove(move) });

[8.3875]

[10.33794]

                        try ml.append(.{ .move = move, .score = score.Move(self, move) });

Replacement in src/Board.zig at line 569 [10.16071]

B:BD[8.4036] → [3.1661:1750]

                        try ml.append(.{ .move = move, .score = self.scoreMove(move) });

[8.4036]

[10.34600]

                        try ml.append(.{ .move = move, .score = score.Move(self, move) });

Replacement in src/Board.zig at line 578 [10.16071]

B:BD[8.4189] → [3.1751:1836]

                    try ml.append(.{ .move = move, .score = self.scoreMove(move) });

[8.4189]

[10.34941]

                    try ml.append(.{ .move = move, .score = score.Move(self, move) });

Replacement in src/Board.zig at line 599 [10.16071]

B:BD[8.4338] → [3.1837:1922]

                    try ml.append(.{ .move = move, .score = self.scoreMove(move) });

[8.4338]

[10.35780]

                    try ml.append(.{ .move = move, .score = score.Move(self, move) });

Replacement in src/Board.zig at line 643 [10.16071]

B:BD[8.4487] → [3.1923:2008]

                    try ml.append(.{ .move = move, .score = self.scoreMove(move) });

[8.4487]

[10.37280]

                    try ml.append(.{ .move = move, .score = score.Move(self, move) });

Replacement in src/Board.zig at line 682 [10.16071]

B:BD[8.4636] → [3.2009:2094]

                    try ml.append(.{ .move = move, .score = self.scoreMove(move) });

[8.4636]

[10.38633]

                    try ml.append(.{ .move = move, .score = score.Move(self, move) });

Replacement in src/Board.zig at line 719 [10.16071]

B:BD[8.4785] → [3.2095:2180]

                    try ml.append(.{ .move = move, .score = self.scoreMove(move) });

[8.4785]

[10.40419]

                    try ml.append(.{ .move = move, .score = score.Move(self, move) });

Replacement in src/Board.zig at line 726 [10.16071]

B:BD[8.4934] → [3.2181:2266]

                    try ml.append(.{ .move = move, .score = self.scoreMove(move) });

[8.4934]

[10.40697]

                    try ml.append(.{ .move = move, .score = score.Move(self, move) });

Deletion in src/Board.zig at line 896 [10.16071]

B:BD[8.5033] → [8.5033:5235]

B:BD[8.5235] → [7.566:698]

∅:D[7.698] → [8.5367:5671]

B:BD[8.5367] → [8.5367:5671]

∅:D[8.5671] → [11.4727:4737]

B:BD[11.4727] → [11.4727:4737]

B:BD[11.4737] → [8.5672:5691]

∅:D[8.5691] → [11.4737:4743]

B:BD[11.4737] → [11.4737:4743]

B:BD[11.4743] → [8.5692:7141]

    pub fn scoreMove(gs: @This(), move: BitMove) isize {
        if (move.capture) {
            var target_piece = Chess.PE.P; // this could be p as well
            const pieces = switch (gs.side) {
                .white => &[_]Chess.PE{ .p, .n, .b, .r, .q, .k },
                .black => &[_]Chess.PE{ .P, .N, .B, .R, .Q, .K },
            };
            for (pieces) |piece| {
                if (gs.bitboards[@enumToInt(piece)].isSet(move.target)) {
                    target_piece = piece;
                    break;
                }
            }
            return MVV_LVA[@enumToInt(move.piece)][@enumToInt(target_piece)];
        }
        return 0;
    }
    // most valuable victim & less valuable attacker
    //    (Victims) Pawn Knight Bishop   Rook  Queen   King
    //  (Attackers)
    //        Pawn   105    205    305    405    505    605
    //      Knight   104    204    304    404    504    604
    //      Bishop   103    203    303    403    503    603
    //        Rook   102    202    302    402    502    602
    //       Queen   101    201    301    401    501    601
    //        King   100    200    300    400    500    600
    // MVV LVA [attacker][victim]
    const MVV_LVA: [12][12]u10 = .{
        .{ 105, 205, 305, 405, 505, 605, 105, 205, 305, 405, 505, 605 },
        .{ 104, 204, 304, 404, 504, 604, 104, 204, 304, 404, 504, 604 },
        .{ 103, 203, 303, 403, 503, 603, 103, 203, 303, 403, 503, 603 },
        .{ 102, 202, 302, 402, 502, 602, 102, 202, 302, 402, 502, 602 },
        .{ 101, 201, 301, 401, 501, 601, 101, 201, 301, 401, 501, 601 },
        .{ 100, 200, 300, 400, 500, 600, 100, 200, 300, 400, 500, 600 },
        .{ 105, 205, 305, 405, 505, 605, 105, 205, 305, 405, 505, 605 },
        .{ 104, 204, 304, 404, 504, 604, 104, 204, 304, 404, 504, 604 },
        .{ 103, 203, 303, 403, 503, 603, 103, 203, 303, 403, 503, 603 },
        .{ 102, 202, 302, 402, 502, 602, 102, 202, 302, 402, 502, 602 },
        .{ 101, 201, 301, 401, 501, 601, 101, 201, 301, 401, 501, 601 },
        .{ 100, 200, 300, 400, 500, 600, 100, 200, 300, 400, 500, 600 },
    };

Replacement in build.zig at line 55 [9.3504]

B:BD[14.54478] → [14.54478:54536]

B:BD[14.54536] → [15.1415:1507]

    exe.linkLibCpp();
    exe.addIncludePath("src/nnue");
    exe.addCSourceFiles(&[_][]const u8{ "src/nnue/nnue.cpp", "src/nnue/misc.cpp" }, flags);

[9.4170]

    // exe.linkLibCpp();
    // exe.addIncludePath("src/nnue");
    // exe.addCSourceFiles(&[_][]const u8{ "src/nnue/nnue.cpp", "src/nnue/misc.cpp" }, flags);