A few bugs found

[wuwbobo2021]

I just realized that you’ve published a gomoku ‘AI’ project, which looks different than your previous programs. The code is not long, so I considered rewriting it in rust to see if it can be accelerated. As I read through the code, I gave up the idea. The so called AI engine don’t use any tree algorithm, so it’s already lightning-fast.

How does score_of_list() (segment of length 5) detect the barrier of opponent's stone? When calculating the score for a possible move, the march length 4 (in 8 directions) seems not enough for detecting invalid long connection, maybe 5 or 6?

[wuwbobo2021]

When I talked about the problem in your program, I forgot that it might came from my previous half-baked ideas that I had told you a long time ago. Maybe it’s my mistake?

Before considering specific score algorithms that may be mapped into the hardware accelerator (OpenCL, Verilog, etc.) in the future, I should make a strict definition for the score to be calculated. A serial algorithm is better for verifying other accelerated ones. Also, if functions that were supposed to be accelerated are to be executed by simplest CPU instructions, it might be even slower.

PS: I disgree with your short segment idea (which is described as a “key” method) for calculating the “score” of each move. Imagine you are in a thread handling a tree branch, scores of all directions of lines should be kept for the thread, when the thread decides to go to a child node, it should recalculate the score sum of lines passing through the next move and store the score difference value for the child node, so the overall score can be recovered when it comes back to the parent node. If so, how can you make those lines shorter?

Temporarily going out from the sadness of being in the last days of my “peaceful” time, now I try to finish my long-lost boring idea and make the definition. To keep my promise, I’ll not put the test program in my own repository.

Standing on one player’s side, the ultimate goal is to get an exactly continuous sequence of 5 stones. I’m counting for possibilities of reaching it by reusing each group of stones. Before calculating the overall score for the board, break it into lines. Stones of the same color should be grouped to be counted according to the group length 1 to 5, in which 5 means no further calculation is required. Length 1 to 4 can be powered differently to form the score sum.

One line can be split into slices by the opponent's stones (and by space no longer than 5 between two stone strings of the same color, if the sum of their lengths > 5 ?), their scores will be summed to get the score of the line. So I get another data structure for the segment: a sequence of space lengths and stone lengths. Each item in these stone lengths corresponds to a string of stones which has two imaginary endpoints (or arrows) at both sides representing the “liberties”.

For a short segment of s1 spaces, n stones and s2 spaces, it’s easy to calulate. If n > 5, don’t count; if n = 5, count 1 for stones length 5 and end calculation; else: if s1 + n >= 5, mark valid for the stone string’s left endpoint, or else mark invalid; same for the right endpoint: n + s2 >= 5. If they are both < 5, then let s2 borrow s1 and make the left endpoint invalid. At last, count the valid endpoints for stones length n.

For a segment of s1 spaces, m stones, s2 spaces, n stones and s3 spaces, it’s a bit complicated. The left of m and right of n would be kept if s1 + m >= 5, n + s3 >= 5. If L = m + s2 + n > 5, the right point of m and left point of n should be marked invalid; else, the right of m and the left of n should be paired and converted, I call it “grouping elevation”. If L = 5, count 1 for stones length m + n; if L < 5, the m + n group should have its own left and right endpoint: consider what will happen when s2 is filled, is its endpoints valid? the group’s endpoint validity should be consistent with that.

I considered the segment X XX X, in which means space and X means stones of the same color, left and right of the segment are boundaries. There’s no enough space at left of first X, don’t count 1 of length 1 for it’s left endpoint; the next is the first X’s right endpoint, because it’s not the last stone string, length of X XX is checked, it’s no longer than 5, so X and XX are grouped; it’s less than 5, so consider the endpoint validity of XXXX in XXXX X, its left point is valid, while the right isn’t. Then consider XX in the original segment, its left point is already converted, for the right point there’s XX X, the right of XX and left of X should be paired, then check XXXX in X XXXX, both endpoints are invalid. The right point of the last X is of course invalid. At last I get only 1 score for stones length 3, none for other lengths.

I considered the segment X X X. The right of first X should be paired with left of second X (get 2); then check the endpoint validity for XXX in XXX * X, the left is invalid, when checking the right, XXX and X should be further paired, len of XXXXX is 5, so count 1 for stones length 2+1 = 3. This further pairing takes the right point of the original second X and left of the original third X away. At last I get only 1 score for stones length 3, none for other lengths.

I’ll put the code of two algorithms here a few days later, one for verifying, one for possible acceleration in the future (processing overlapping segments of 5,6 or 7), and a testbench which generates infinite amount of lines to verify the consistency of both algorithm’s results. Again, it will not be hosted in my own repo.

[wuwbobo2021]

I've finished the code, which should be my last effort in gomoku. Maybe it's stupid, but it's verified by myself. Please close this issue if you are sure of making an engine based on the algorithm, otherwise I'll probably send it to the author of rapfi.

To test the code, install the rust toolchain and execute cargo new caro-rust somewhere, put the code in main.rs, and make sure the content of Cargo.toml is

[package]
name = "caro-rust"
version = "0.1.0"
edition = "2021"

[dependencies]
rand = "0.8.5"

[profile.release]
opt-level = 3

Run cargo test, then cargo run --release.

code in main.rs:

// the black/white score of a line in the five-in-a-row board is defined here:
// the score table [x, x, x, x, x] counts scores of length 1, 2, 3, 4, 5.
// split the line by stones of the opponent's color;
// generate a sequence of spaces and connections of different lengths;
// every two connections divided by a space form a group if the sum of their lengths
// is no longer than 5;
// count each connection's score by its length and by checking spaces at both sides:
// if it's not grouped with the connection at one side and the space is enough at
// that side, count 1 of its length for that side; if there's no enough space at
// both sides, then check the sum of spaces at both sides, count 1 if that's enough.
// count each group's score according to the sum of both connection's lengths:
// check spaces at both sides of the group just like checking for a single connection
// (without worrying about further grouping except for X.X.X), except for groups of
// length 5: count 1 immediately. the special case X.X.X is a valid group of score length 3.

// another algorithm with lots of logic operations is written here for verification,
// it can be rewritten in Verilog (and maybe OpenCL) for acceleration.

#[derive(Clone, Copy, PartialEq, Eq)]
pub enum PosState { //it can be 2 bits "placed" and "white" in Verilog
    Empty,
    Black,
    White
}

impl PosState {
    #[inline(always)] fn is_empty(&self) -> bool { *self == PosState::Empty }
    #[inline(always)] fn is_black(&self) -> bool { *self == PosState::Black }
    #[inline(always)] fn is_white(&self) -> bool { *self == PosState::White }
    #[inline(always)] fn is_stone(&self, white: bool) -> bool {
        if white { self.is_white() } else { self.is_black() }
    }
    #[inline(always)] fn is_not(&self, white: bool) -> bool { !self.is_stone(white) }
}

const E: PosState = PosState::Empty;
const B: PosState = PosState::Black;
const W: PosState = PosState::White;

impl std::fmt::Debug for PosState {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            PosState::Empty => write!(f, "."),
            PosState::Black => write!(f, "X"),
            PosState::White => write!(f, "O")
        }
    }
}

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct SeqScore {
    cnts: [u8; 5],
}
impl SeqScore {
    pub fn new() -> Self {
        SeqScore { cnts: [0; 5] }
    }

    #[inline(always)] pub fn add(&mut self, len: u8, cnt: u8) {
        self.cnts[(len - 1) as usize] += cnt;
    }

    #[inline(always)] pub fn enter(&mut self, other: SeqScore) {
        for i in 0..5 {
            self.cnts[i] += other.cnts[i];
        }
    }

    #[inline(always)] pub fn score_of_len(&self, len: u8) -> u8 {
        self.cnts[(len - 1) as usize]
    }
}

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct ScoreSum {
    cnts: [i32; 5],
}

impl ScoreSum {
    pub fn new() -> Self {
        ScoreSum { cnts: [0; 5] }
    }

    #[inline(always)] pub fn enter(&mut self, sc: SeqScore) {
        for i in 0..5 {
            self.cnts[i] += sc.cnts[i] as i32;
        }
    }

    #[inline(always)] pub fn subtract(&mut self, sc: SeqScore) {
        for i in 0..5 {
            self.cnts[i] -= sc.cnts[i] as i32;
        }
    }

    #[inline(always)] pub fn score_of_len(&self, len: u8) -> i32 {
        self.cnts[(len - 1) as usize]
    }

    #[inline(always)] pub fn clear(&mut self) { self.cnts = [0; 5]; }
}

mod serial_calc {
    use crate::*;

    #[derive(Clone, Copy, Debug)]
    struct Conn {
        len: u8,
        l_grp: bool,
        r_grp: bool,
    }
    impl Conn {
        pub fn new(len: u8) -> Self {
            Conn { len, l_grp: false, r_grp: false }
        }
    }

    // number as const template param must be usize, otherwise u8 would be used
    #[derive(Debug)]
    pub struct SerialCalc<const SZ: usize> {
        spaces: [u8; SZ], //count of spaces = count + 1
        conns: [Conn; SZ], //lengths of connected stones
        count: usize, //count of connections. index of array must be usize
    }

    impl<const SZ: usize> SerialCalc<SZ> {
        pub fn new() -> Self {
            assert!(SZ >= 5 && SZ <= 26); //26 can be changed to another u8 value
            SerialCalc {
                spaces: [0; SZ],
                conns: [Conn::new(0); SZ],
                count: 0,
            }
        }

        pub fn load(&mut self, seq: &[bool]) {
            self.count = 0;

            let mut pre_val = false;
            let mut cnt: u8 = 0;

            for &val in seq {
                if val == pre_val {
                    cnt += 1;
                } else {
                    if pre_val == false {
                        self.spaces[self.count] = cnt;
                    } else {
                        self.conns[self.count] = Conn::new(cnt);
                        self.count += 1;
                    }
                    cnt = 1;
                    pre_val = val;
                }
            }

            // load the last connection or space
            if pre_val {
                self.conns[self.count] = Conn::new(cnt);
                self.count += 1;
                self.spaces[self.count] = 0;
            } else {
                self.spaces[self.count] = cnt;
            }

            // space at boundary is unique (without risk of long connection)
            self.spaces[0] += 1;
            self.spaces[self.count] += 1;
        }

        pub fn calc_score(&mut self) -> SeqScore {
            let mut score = SeqScore::new();
            if self.count == 0 { return score; }

            // spaces[i]          spaces[i + 1]              spaces[i + 2]
            //           conns[i]               conns[i + 1]               conns[i + 2]
            //           ------------ len_with_r -----------
            // note: range "0..n" in rust doesn't include n, while "0..=n" does include n

            // grouping
            for i in 0..self.count-1 {
                if self.conns[i].len + self.spaces[i + 1] + self.conns[i + 1].len <= 5 {
                    self.conns[i].r_grp = true;
                    self.conns[i + 1].l_grp = true;
                }
            }

            // count score for each connection
            for i in 0..self.count {
                if self.conns[i].len > 5 { continue; }
                if self.conns[i].len == 5 {
                    score.add(5, 1); return score;
                }

                let mut try_borrow = true;

                if self.conns[i].l_grp == false && self.conns[i].len + (self.spaces[i] - 1) >= 5 {
                    score.add(self.conns[i].len, 1); //the left is valid
                    try_borrow = false;
                }

                if self.conns[i].r_grp == false && self.conns[i].len + (self.spaces[i + 1] - 1) >= 5 {
                    score.add(self.conns[i].len, 1); //the right is valid
                    try_borrow = false;
                }

                if try_borrow && (self.spaces[i] - 1) + self.conns[i].len + (self.spaces[i + 1] - 1) >= 5 {
                    // one of conns[i].l_grp and conns[i].r_grp should be false, except case of X...X...X
                    score.add(self.conns[i].len, 1); //borrowing
                }
            }

            // count score for groups
            for i in 0..self.count-1 {
                if self.conns[i].r_grp == false { continue; }
                let len_score = self.conns[i].len + self.conns[i + 1].len;
                let len_with_r = len_score + self.spaces[i + 1];

                let mut try_borrow = true;

                if len_with_r == 5 {
                    score.add(len_score, 1); continue; //don't consider the left/right side
                }

                if i + 2 < self.count
                && (len_with_r + self.spaces[i + 2] + self.conns[i + 2].len) == 5 {
                    score.add(3, 1); //the only case of double grouping (occurs at the right side)
                    try_borrow = false;
                }
                else if len_with_r + (self.spaces[i + 2] - 1) >= 5 {
                    score.add(len_score, 1); //the right is valid
                    try_borrow = false;
                }

                if len_with_r + (self.spaces[i] - 1) >= 5 {
                    score.add(len_score, 1); //the left is valid
                    try_borrow = false;
                }

                if try_borrow && len_with_r + (self.spaces[i] - 1) + (self.spaces[i + 2] - 1) >= 5 {
                    score.add(len_score, 1); //borrowing
                }
            }

            return score;
        }
    }

    fn calc_score<const SZ: usize, const FOR_WH: bool>(seq: &[PosState; SZ]) -> SeqScore {
        let mut calc: SerialCalc<SZ> = SerialCalc::new();
        let mut score = SeqScore::new();

        let mut seq_bool = [false; SZ];
        let mut seq_bool_cnt: usize = 0;

        for &st in seq {
            if st.is_stone(! FOR_WH) {
                if seq_bool_cnt >= 5 {
                    calc.load(&seq_bool[0..seq_bool_cnt]);
                    score.enter(calc.calc_score());
                }
                seq_bool_cnt = 0;
            } else {
                seq_bool[seq_bool_cnt] = ! st.is_empty();
                seq_bool_cnt += 1;
            }
        }

        if seq_bool_cnt > 0 {
            calc.load(&seq_bool[0..seq_bool_cnt]);
            score.enter(calc.calc_score());
        }

        return score;
    }
    pub fn calc_score_serial_black<const SZ: usize>(seq: &[PosState; SZ]) -> SeqScore {
        calc_score::<SZ, false>(seq)
    }
    pub fn calc_score_serial_white<const SZ: usize>(seq: &[PosState; SZ]) -> SeqScore {
        calc_score::<SZ, true>(seq)
    }

    #[test]
    fn serial_calc_load_test() {
        let mut calc: SerialCalc<15> = SerialCalc::new();

        calc.load(&[false, true, true, false, false, true, true, true, false, true]);
        assert_eq!(calc.count, 3);
        assert_eq!(&calc.spaces[0..4], &[1+1, 2, 1, 0+1]);
        assert_eq!((calc.conns[0].len, calc.conns[1].len, calc.conns[2].len), (2, 3, 1));

        calc.load(&[true, false, true, false, false, true, true, true, false, true, false]);
        assert_eq!(calc.count, 4);
        assert_eq!(&calc.spaces[0..5], &[0+1, 1, 2, 1, 1+1]);
        assert_eq!(
            (calc.conns[0].len, calc.conns[1].len, calc.conns[2].len, calc.conns[3].len),
            (1, 1, 3, 1)
        );
    }

    #[test]
    fn calc_score_serial_test() {
        let row = [W, E, W, E, W, E, E, E, E];
        assert_eq!(calc_score_serial_white(&row), SeqScore{cnts: [1, 1, 1, 0, 0]});

        let row = [E, E, W, W, E, E, W, E, W];
        assert_eq!(calc_score_serial_white(&row), SeqScore{cnts: [0, 1, 1, 0, 0]});

        let row = [E, E, W, W, E, E, W, W, E];
        assert_eq!(calc_score_serial_white(&row), SeqScore{cnts: [0, 1, 0, 0, 0]});

        let row = [E, E, W, W, E, E, W, E, W, W, W, E, W, W, W];
        assert_eq!(calc_score_serial_white(&row), SeqScore{cnts: [0, 1, 1, 1, 0]});

        let row = [E, E, W, W, E, E, W, W, W, E, E, W, E, E, E];
        assert_eq!(calc_score_serial_white(&row), SeqScore{cnts: [1, 1, 1, 0, 0]});

        let row = [E, E, W, W, E, E, W, W, W, E, E, W, W, E, E];
        assert_eq!(calc_score_serial_white(&row), SeqScore{cnts: [0, 2, 1, 0, 0]});

        let row = [W, E, W, E, W, E, W, E, W, W, W, E, E, E, E];
        assert_eq!(calc_score_serial_white(&row), SeqScore{cnts: [0, 0, 3, 1, 0]});

        let row = [E, E, W, W, E, E, E, E, W, W, E, E];
        assert_eq!(calc_score_serial_white(&row), SeqScore{cnts: [0, 2, 0, 0, 0]});

        let row = [E, E, W, W, E, E, W, E, W, E, E, W];
        assert_eq!(calc_score_serial_white(&row), SeqScore{cnts: [0, 2, 1, 0, 0]});

        let row = [E, E, W, W, W, W, W, E, W, E, E, W];
        assert_eq!(calc_score_serial_white(&row).score_of_len(5), 1);

        let row = [W, W, W, W, W, W, B, E, E, E, E, W];
        assert_eq!(calc_score_serial_white(&row), SeqScore{cnts: [1, 0, 0, 0, 0]});

        let row = [B, E, W, E, W, E, E, W, E, E, E, B, W, E, E, W, W, E, E];
        assert_eq!(calc_score_serial_white(&row), SeqScore{cnts: [1, 3, 1, 0, 0]});

        let row = [E, E, W, B, E, E, W, E, E, E, W, E, E, E, W, B, B, B, B];
        assert_eq!(calc_score_serial_white(&row), SeqScore{cnts: [2, 2, 0, 0, 0]});

        let mut bulk = gen_random_rows::<19>(65536);
        for row in &mut bulk {
            let score = calc_score_serial_white(row);
            reverse_row(row);
            assert_eq!(score, calc_score_serial_white(row));
        }
    }
}

mod par_sim_calc {
    use crate::*;

    #[inline(always)] fn count_rlb(r: bool, l: bool, b: bool) -> u8 {
        let mut cnt: u8 = 0;
        if l { cnt += 1; }
        if r { cnt += 1; }
        if !l && !r && b { cnt += 1; }
        return cnt;
    }

    fn calc_score<const SZ: usize, const FOR_WH: bool>(seq: &[PosState; SZ]) -> SeqScore {
        const SZ_MAX: usize = 26;
        assert!(SZ >= 5 && SZ_MAX <= 26);

        let mut score = SeqScore::new();

        // a position beyond the original boundary equals a len 1 space in the middle
        // [PosState; SZ + 2] is not possible: rustc error
        // "generic parameters may not be used in const operations"
        // "const parameters may only be used as standalone arguments, i.e. `SZ`"
        let arr_len = SZ + 2; 
        let mut arr = [E; SZ_MAX + 2];
        for (i, &st) in seq.iter().enumerate() {
            arr[i + 1] = st;
        }

        // grade 1 simulation

        for i in 0..(SZ + 2 - (5 + 2 - 1)) { // -XXXXX-
            if arr[i]    .is_not(FOR_WH)
            && arr[i + 1].is_stone(FOR_WH)
            && arr[i + 2].is_stone(FOR_WH)
            && arr[i + 3].is_stone(FOR_WH)
            && arr[i + 4].is_stone(FOR_WH)
            && arr[i + 5].is_stone(FOR_WH)
            && arr[i + 6].is_not(FOR_WH) {
                score.add(5, 1); return score;
            }
        }

        let mut arr_conn1 = [false; SZ];
        let arr_conn1_len = SZ + 2 - (3 - 1); // -X-
        for i in 0..arr_conn1_len {
            arr_conn1[i] =
                arr[i]    .is_not(FOR_WH) &&
                arr[i + 1].is_stone(FOR_WH) &&
                arr[i + 2].is_not(FOR_WH);
        }

        let arr_conn2_len = SZ + 2 - (4 - 1); // -XX-
        let mut arr_conn2 = [false; SZ];
        for i in 0..arr_conn2_len {
            arr_conn2[i] =
                arr[i]    .is_not(FOR_WH) &&
                arr[i + 1].is_stone(FOR_WH) &&
                arr[i + 2].is_stone(FOR_WH) &&
                arr[i + 3].is_not(FOR_WH);
        }

        let arr_conn3_len = SZ + 2 - (5 - 1); // -XXX-
        let mut arr_conn3 = [false; SZ];
        for i in 0..arr_conn3_len {
            arr_conn3[i] =
                arr[i]    .is_not(FOR_WH) &&
                arr[i + 1].is_stone(FOR_WH) &&
                arr[i + 2].is_stone(FOR_WH) &&
                arr[i + 3].is_stone(FOR_WH) &&
                arr[i + 4].is_not(FOR_WH);
        }

        let arr_conn4_len = SZ + 2 - (6 - 1); // -XXXX-
        let mut arr_conn4 = [false; SZ];
        for i in 0..arr_conn4_len {
            arr_conn4[i] =
                arr[i]    .is_not(FOR_WH) &&
                arr[i + 1].is_stone(FOR_WH) &&
                arr[i + 2].is_stone(FOR_WH) &&
                arr[i + 3].is_stone(FOR_WH) &&
                arr[i + 4].is_stone(FOR_WH) &&
                arr[i + 5].is_not(FOR_WH);
        }

        let arr_empty2_len = SZ + 2 - (2 - 1);
        let mut arr_empty2 = [false; SZ_MAX + 2];
        for i in 0..arr_empty2_len {
            arr_empty2[i] = arr[i].is_empty() && arr[i + 1].is_empty();
        }

        let arr_empty3_len = SZ + 2 - (3 - 1);
        let mut arr_empty3 = [false; SZ];
        for i in 0..arr_empty3_len {
            arr_empty3[i] = arr_empty2[i] && arr[i + 2].is_empty();
        }

        let arr_empty4_len = SZ + 2 - (4 - 1);
        let mut arr_empty4 = [false; SZ];
        for i in 0..arr_empty4_len {
            arr_empty4[i] = arr_empty3[i] && arr[i + 3].is_empty();
        }

        // grade 2 simulation

        // -XXXXXXX-
        // -X.X-
        //  -X.X-
        //   -X.X-
        //    -X.X-
        //     -X.X-
        let arr_2_in_3_len = SZ + 2 - (3 + 2 - 1);
        let mut arr_2_in_3 = [false; SZ];
        for i in 0..arr_2_in_3_len {
            arr_2_in_3[i] = arr_conn1[i] && arr[i + 2].is_empty() && arr_conn1[i + 2];
        }

        let arr_2_in_4_len = SZ + 2 - (4 + 2 - 1);
        let mut arr_2_in_4 = [false; SZ]; // -X..X-
        for i in 0..arr_2_in_4_len {
            arr_2_in_4[i] = arr_conn1[i] && arr_empty2[i + 2] && arr_conn1[i + 3];
        }

        let arr_3_in_4_len = SZ + 2 - (4 + 2 - 1);
        let mut arr_3_in_4 = [false; SZ]; // -X.XX- -XX.X-
        for i in 0..arr_3_in_4_len {
            arr_3_in_4[i] =
                (arr_conn1[i] && arr[i + 2].is_empty() && arr_conn2[i + 2]) ||
                (arr_conn2[i] && arr[i + 3].is_empty() && arr_conn1[i + 3]);
        }

        let arr_2_in_5_len = SZ + 2 - (5 + 2 - 1);
        let mut arr_2_in_5 = [false; SZ]; // -X...X-
        for i in 0..arr_2_in_5_len {
            arr_2_in_5[i] = arr_conn1[i] && arr_empty3[i + 2] && arr_conn1[i + 4];
        }

        let arr_3_in_5_len = SZ + 2 - (5 + 2 - 1);
        let mut arr_3_in_5 = [false; SZ]; // -XX..X- -X..XX- -X.X.X-
        for i in 0..arr_3_in_5_len {
            arr_3_in_5[i] =
                (arr_conn2[i] && arr_empty2[i + 3] && arr_conn1[i + 4]) ||
                (arr_conn1[i] && arr_empty2[i + 2] && arr_conn2[i + 3]) ||
                (arr_2_in_3[i] && arr_2_in_3[i + 2]); //the only case of double grouping
        }

        let arr_4_in_5_len = SZ + 2 - (5 + 2 - 1);
        let mut arr_4_in_5 = [false; SZ]; // -XXX.X- -X.XXX- -XX.XX-
        for i in 0..arr_4_in_5_len {
            arr_4_in_5[i] =
                (arr_conn3[i] && arr[i + 4].is_empty() && arr_conn1[i + 4]) ||
                (arr_conn1[i] && arr[i + 2].is_empty() && arr_conn3[i + 2]) ||
                (arr_conn2[i] && arr[i + 3].is_empty() && arr_conn2[i + 3]);
        }

        // grade 3 simulation

        // -x-     |     -x- |  -x-    |    -x-  |   -x-
        //   ....- | -....   | -. ...- | -... .- | -.. ..-
        // i123456   0123i56   0i23456   012i456   01i3456
        for i in 0..arr_conn1_len {
            if !arr_conn1[i] { continue; } //extracted from r,l,b to accelerate simulation
            // conditions like i + 6 < arr_len should be mapped to different logics for each i
            score.add(1, count_rlb(
                i + 6 < arr_len && arr_empty4[i + 2] && arr[i + 6].is_not(FOR_WH), //right
                i >= 4          && arr[i - 4].is_not(FOR_WH) && arr_empty4[i - 3], //left
                (i >= 1 && i + 5 < arr_len &&
                    arr[i - 1].is_not(FOR_WH) && arr[i].is_empty() &&
                    arr_empty3[i + 2] && arr[i + 5].is_not(FOR_WH)) ||
                (i >= 3 && i + 3 < arr_len &&
                    arr[i - 3].is_not(FOR_WH) && arr_empty3[i - 2] &&
                    arr[i + 2].is_empty() && arr[i + 3].is_not(FOR_WH)) ||
                (i >= 2 && i + 4 < arr_len &&
                    arr[i - 2].is_not(FOR_WH) && arr_empty2[i - 1] &&
                    arr_empty2[i + 2] && arr[i + 4].is_not(FOR_WH))
            ));
        }

        // -xx-    |    -xx- |  -xx-   |   -xx-
        //    ...- | -...    | -.  ..- | -..  .-
        for i in 0..arr_conn2_len {
            if !arr_conn2[i] { continue; }
            score.add(2, count_rlb(
                i + 6 < arr_len && arr_empty3[i + 3] && arr[i + 6].is_not(FOR_WH),
                i >= 3          && arr[i - 3].is_not(FOR_WH) && arr_empty3[i - 2],
                (i >= 1 && i + 5 < arr_len &&
                    arr[i - 1].is_not(FOR_WH) && arr[i].is_empty()
                    && arr_empty2[i + 3] && arr[i + 5].is_not(FOR_WH)) ||
                (i >= 2 && i + 4 < arr_len &&
                    arr[i - 2].is_not(FOR_WH) && arr_empty2[i - 1] &&
                    arr[i + 3].is_empty() && arr[i + 4].is_not(FOR_WH))
            ));
        }

        // -xxx-   |   -xxx- |  -xxx-
        //     ..- | -..     | -.   .-
        for i in 0..arr_conn3_len {
            if !arr_conn3[i] { continue; }
            score.add(3, count_rlb(
                i + 6 < arr_len && arr_empty2[i + 4] && arr[i + 6].is_not(FOR_WH),
                i >= 2 && arr[i - 2].is_not(FOR_WH) && arr_empty2[i - 1],
                i >= 1 && i + 5 < arr_len &&
                    arr[i - 1].is_not(FOR_WH) && arr[i].is_empty() &&
                    arr[i + 4].is_empty() && arr[i + 5].is_not(FOR_WH)
            ));
        }

        // -xxxx-  |  -xxxx-
        //      .- | -.
        for i in 0..arr_conn4_len {
            if !arr_conn4[i] { continue; }
            score.add(4, count_rlb(
                i + 6 < arr_len && arr[i + 5].is_empty() && arr[i + 6].is_not(FOR_WH),
                i >= 1 && arr[i - 1].is_not(FOR_WH) && arr[i].is_empty(),
                false
            ));
        }

        // -x.x-   |   -x.x- |  -x.x-
        //     ..- | -..     | -.   .-
        // see arr_conn3 processing above
        for i in 0..arr_2_in_3_len {
            if !arr_2_in_3[i] { continue; }
            score.add(2, count_rlb(
                i + 6 < arr_len && arr_empty2[i + 4] && arr[i + 6].is_not(FOR_WH),
                i >= 2 && arr[i - 2].is_not(FOR_WH) && arr_empty2[i - 1],
                i >= 1 && i + 5 < arr_len &&
                    arr[i - 1].is_not(FOR_WH) && arr[i].is_empty() &&
                    arr[i + 4].is_empty() && arr[i + 5].is_not(FOR_WH)
            ));
        }

        // see arr_conn4 processing above
        for i in 0..arr_2_in_4_len {
            if !arr_2_in_4[i] { continue; }
            score.add(2, count_rlb(
                i + 6 < arr_len && arr[i + 5].is_empty() && arr[i + 6].is_not(FOR_WH),
                i >= 1 && arr[i - 1].is_not(FOR_WH) && arr[i].is_empty(),
                false
            ));
        }
        for i in 0..arr_3_in_4_len {
            if !arr_3_in_4[i] { continue; }
            score.add(3, count_rlb(
                i + 6 < arr_len && arr[i + 5].is_empty() && arr[i + 6].is_not(FOR_WH),
                i >= 1 && arr[i - 1].is_not(FOR_WH) && arr[i].is_empty(),
                false
            ));
        }

        for b in arr_2_in_5 { if b { score.add(2, 1); } }
        for b in arr_3_in_5 { if b { score.add(3, 1); } }
        for b in arr_4_in_5 { if b { score.add(4, 1); } }

        return score;
    }

    pub fn calc_score_par_sim_black<const SZ: usize>(seq: &[PosState; SZ]) -> SeqScore {
        calc_score::<SZ, false>(seq)
    }
    pub fn calc_score_par_sim_white<const SZ: usize>(seq: &[PosState; SZ]) -> SeqScore {
        calc_score::<SZ, true>(seq)
    }

    #[test]
    pub fn calc_score_par_sim_test() {
        let row = [E, E, W, W, E, E, W, W, W, E, E, W, W, E, E];
        assert_eq!(calc_score_par_sim_white(&row), SeqScore{cnts: [0, 2, 1, 0, 0]});

        let row = [W, E, W, E, W, E, W, E, W, W, W, E, E, E, E];
        assert_eq!(calc_score_par_sim_white(&row), SeqScore{cnts: [0, 0, 3, 1, 0]});

        let row = [E, E, W, W, E, E, E, E, W, W, E, E];
        assert_eq!(calc_score_par_sim_white(&row), SeqScore{cnts: [0, 2, 0, 0, 0]});

        let row = [E, E, W, W, E, E, W, E, W, E, E, W];
        assert_eq!(calc_score_par_sim_white(&row), SeqScore{cnts: [0, 2, 1, 0, 0]});

        let row = [E, E, W, W, W, W, W, E, W, E, E, W];
        assert_eq!(calc_score_par_sim_white(&row).score_of_len(5), 1);

        let row = [W, W, W, W, W, W, B, E, E, E, E, W];
        assert_eq!(calc_score_par_sim_white(&row), SeqScore{cnts: [1, 0, 0, 0, 0]});

        let row = [B, E, W, E, W, E, E, W, E, E, E, B, W, E, E, W, W, E, E];
        assert_eq!(calc_score_par_sim_white(&row), SeqScore{cnts: [1, 3, 1, 0, 0]});

        let mut bulk = gen_random_rows::<19>(65536);
        for row in &mut bulk {
            let score = calc_score_par_sim_white(row);
            reverse_row(row);
            let score_r = calc_score_par_sim_white(row);
            if score != score_r {
                let mut row_org = row.clone(); reverse_row(&mut row_org);
                println!("reverse test failed:\n{:?} {:?}\n{:?} {:?}", row_org, score, row, score_r);
                return;
            }
        }
    }
}

extern crate rand;
use rand::Rng;

fn gen_random_rows<const SZ: usize>(cnt_rows: usize) -> Vec<[PosState; SZ]> {
    const RND_TABLE: [(PosState, usize); 55] = [
        (B, 1), (B, 1), (B, 1), (B, 1), (B, 2), (B, 2), (B, 2), (B, 3), (B, 3), (B, 4), (B, 2),
        (W, 1), (W, 1), (W, 1), (W, 1), (W, 2), (W, 2), (W, 2), (W, 3), (W, 3), (W, 4), (W, 2),
        (W, 1), (W, 1), (W, 1), (W, 1), (W, 2), (W, 2), (W, 2), (W, 1), (W, 3), (W, 4), (W, 2),
        (E, 1), (E, 1), (E, 1), (E, 1), (E, 2), (E, 2), (E, 2), (E, 3), (E, 3), (E, 4), (E, 6),
        (E, 1), (E, 1), (E, 1), (E, 1), (E, 2), (E, 2), (E, 2), (E, 2), (E, 2), (E, 3), (E, 1),
    ];

    let mut last_st = E;
    let mut row = [E; SZ];
    let mut rows = Vec::new();
    for _ in 0..cnt_rows {
        let mut len_filled = 0;
        loop {
            let ch = rand::thread_rng().gen_range(0..RND_TABLE.len());
            let (st, len) = RND_TABLE[ch];
            if last_st == st || len_filled + len > SZ {
                continue;
            }
            for i in len_filled..(len_filled + len) {
                row[i] = st;
            }
            len_filled += len; last_st = st;
            if len_filled == SZ { break; }
        }
        rows.push(row);
    }
    return rows;
}

fn reverse_row<const SZ: usize>(row: &mut [PosState; SZ]) {
    for i in 0..row.len()/2 {
        let tmp = row[SZ - i - 1];
        row[SZ - i - 1] = row[i];
        row[i] = tmp;
    }
}

#[test]
fn reverse_row_test() {
    let mut row =   [B, E, W, E, W, E];
    reverse_row(&mut row);
    assert_eq!(row, [E, W, E, W, E, B]);

    let mut row =   [B, E, W, E, W, E, E, W, E, B, E, B, W, E, E, W, W, E, E];
    reverse_row(&mut row);
    assert_eq!(row, [E, E, W, W, E, E, W, B, E, B, E, W, E, E, W, E, W, E, B]);
}

use serial_calc::calc_score_serial_black;
use serial_calc::calc_score_serial_white;
use par_sim_calc::calc_score_par_sim_black;
use par_sim_calc::calc_score_par_sim_white;

fn measure_exec_time_ms<F: FnOnce()>(fn_exec: F) -> u128 {
    use std::time::{SystemTime, UNIX_EPOCH};
    let t_start = SystemTime::now().duration_since(UNIX_EPOCH).unwrap().as_millis();
    fn_exec();
    let t_end = SystemTime::now().duration_since(UNIX_EPOCH).unwrap().as_millis();
    return t_end - t_start;
}

fn main() {
    let bulk_size = 2097152;
    println!("running endless consistency test, len-19 x {bulk_size} per bulk...");

    let mut bulk_cnt = 0;
    loop {
        let bulk = gen_random_rows::<19>(bulk_size);

        let mut scores_ser: Vec<SeqScore> = Vec::new();
        scores_ser.reserve(bulk_size);
        let ms_ser = measure_exec_time_ms(||
            for arr in &bulk {
                let score = calc_score_serial_white(arr);
                scores_ser.push(score);
            }
        );

        let mut scores_par_sim: Vec<SeqScore> = Vec::new();
        scores_par_sim.reserve(bulk_size);
        let ms_par_sim = measure_exec_time_ms(||
            for arr in &bulk {
                let score = calc_score_par_sim_white(arr);
                scores_par_sim.push(score);
            }
        );

        for i in 0..bulk.len() {
            if scores_ser[i] != scores_par_sim[i] {
                println!("\tfailed: {:?} ser:{:?} par:{:?}", bulk[i], scores_ser[i], scores_par_sim[i]);
            }
        }

        bulk_cnt += 1;
        println!("bulk {bulk_cnt}: success. serial: {ms_ser} ms. par_sim: {ms_par_sim} ms.");
    }
}

[nguyencongminh090]

Thanks for your time, but... I just do it for a friend.

• Algorithm is not mine
• I just write main.py as an adapter to transfer from simple command to piskvork protocol

Recently, I'm writing a socket program use C++, I may need your help. If you have interested, you can answer here.