Re: Simplifying code
Posted: Fri Apr 24, 2020 9:50 pm
Just create the board at program entry, and then pass a pointer to that board to each function such as search() or perft().
In that function you can create a local move list over which you can iterate. As those functions are recursive, each function call will automatically have its own move list on the stack. Because you're using only one board, you'll obviously have to use make/unmake. It's the fastest way. copy/make is too slow, because you'll have to copy the entire position, bitboards, lists and all. This is my board:
This would take:
bb_side: 8 bytes x 6 pieces x 2 sides = 96 bytes
bb_pieces: 8 bytes x 2 sides = 16 bytes
game_state: This is also a struct with its own fields. It's 24 bytes.
history: this is the game history. It is an array that holds 2048 game states: 49.152 bytes.
piece_list: 8 bytes x 64 squares (my pieces are usize/u64, as Rust requires this for array indexing): 512 bytes
zobrist_randoms: Atomic Counting Reference Pointer to the Zobrist Randoms struct. 8 bytes.
move_generator: Atomic Counting Reference Pointer to the Move Generator struct. 8 bytes.
The last two exist so I don't need to pass the zobrist randoms and move generator to any functions. I can't just call them globally; Rust has no global variables. (Well; it does; if you prefer working AGAINST the language, you can hack it...)
The total is 49.816 bytes. I wouldn't want to copy that on each move, billions of times in a game.
In a different language such as C, you could store the history list, zobrist randoms and move generator globally, but the rest is essential to be copied because it changes on every move. Even so, you'd need to copy 648 bytes. A billion copies of 648 bytes comes down to 600 GB of copying.
I'd rather do make/unmake to be honest...
I first had my material count in the game state struct, thinking to save two instructions: not having to update it in reverse when doing unmake(). It was only 2x 8 bytes to copy... so, should work, right? But then I did some research. My game state struct was 26 bytes, and Rust pads it up to 32, which is the first multiple of 8. So, I was copying 6 bytes extra on each make/unmake. I took the material count out, which dropped the struct to 24 bytes; this is exactly a multiple of 8 so it isn't padded. Taking out 2 bytes therefore saved me 8 bytes of copying during make and unmake, and the engine sped up by a few MILLION moves per second. It gained me 10% speed. So yes, taking one or two bytes off of struct type that is copied back and forth billions of times can actually speed up your engine by 10% percent.
I managed to pull this optimization (and some others, cutting if-statements and assignments where possible) off in a few places in make and unmake, and it dropped my perft 7 speed from 120 seconds to 79 seconds. Speedup is 34%.
In a chess engine, speed is your currency. This currency buys you deeper search (if you just use the speed) or better evaluation accuracy (you can trade the speed for more/better evaluation parameters without losing search depth). The more speed you have (efficient move generation, make/unmake, search with good move ordering and pruning), the more other things you can "buy".
Making your evaluation better = more strength... but... it also loses speed, and thus search depth, which costs you strength. The gain through evaluation better be higher than the loss of strength due to searching less deep. So, if you add an evaluation parameter that costs you 3% speed and then can you manage to speed up the engine by 3%, your evaluation was basically free.
In that function you can create a local move list over which you can iterate. As those functions are recursive, each function call will automatically have its own move list on the stack. Because you're using only one board, you'll obviously have to use make/unmake. It's the fastest way. copy/make is too slow, because you'll have to copy the entire position, bitboards, lists and all. This is my board:
Code: Select all
pub struct Board {
pub bb_side: [[Bitboard; NR_OF_PIECES as usize]; EACH_SIDE as usize],
pub bb_pieces: [Bitboard; EACH_SIDE as usize],
pub game_state: GameState,
pub history: History,
pub piece_list: [Piece; NR_OF_SQUARES as usize],
pub material_count: [u16; EACH_SIDE as usize],
zobrist_randoms: Arc<ZobristRandoms>,
move_generator: Arc<MoveGenerator>,
}
bb_side: 8 bytes x 6 pieces x 2 sides = 96 bytes
bb_pieces: 8 bytes x 2 sides = 16 bytes
game_state: This is also a struct with its own fields. It's 24 bytes.
history: this is the game history. It is an array that holds 2048 game states: 49.152 bytes.
piece_list: 8 bytes x 64 squares (my pieces are usize/u64, as Rust requires this for array indexing): 512 bytes
zobrist_randoms: Atomic Counting Reference Pointer to the Zobrist Randoms struct. 8 bytes.
move_generator: Atomic Counting Reference Pointer to the Move Generator struct. 8 bytes.
The last two exist so I don't need to pass the zobrist randoms and move generator to any functions. I can't just call them globally; Rust has no global variables. (Well; it does; if you prefer working AGAINST the language, you can hack it...)
The total is 49.816 bytes. I wouldn't want to copy that on each move, billions of times in a game.
In a different language such as C, you could store the history list, zobrist randoms and move generator globally, but the rest is essential to be copied because it changes on every move. Even so, you'd need to copy 648 bytes. A billion copies of 648 bytes comes down to 600 GB of copying.
I'd rather do make/unmake to be honest...
I first had my material count in the game state struct, thinking to save two instructions: not having to update it in reverse when doing unmake(). It was only 2x 8 bytes to copy... so, should work, right? But then I did some research. My game state struct was 26 bytes, and Rust pads it up to 32, which is the first multiple of 8. So, I was copying 6 bytes extra on each make/unmake. I took the material count out, which dropped the struct to 24 bytes; this is exactly a multiple of 8 so it isn't padded. Taking out 2 bytes therefore saved me 8 bytes of copying during make and unmake, and the engine sped up by a few MILLION moves per second. It gained me 10% speed. So yes, taking one or two bytes off of struct type that is copied back and forth billions of times can actually speed up your engine by 10% percent.
I managed to pull this optimization (and some others, cutting if-statements and assignments where possible) off in a few places in make and unmake, and it dropped my perft 7 speed from 120 seconds to 79 seconds. Speedup is 34%.
In a chess engine, speed is your currency. This currency buys you deeper search (if you just use the speed) or better evaluation accuracy (you can trade the speed for more/better evaluation parameters without losing search depth). The more speed you have (efficient move generation, make/unmake, search with good move ordering and pruning), the more other things you can "buy".
Making your evaluation better = more strength... but... it also loses speed, and thus search depth, which costs you strength. The gain through evaluation better be higher than the loss of strength due to searching less deep. So, if you add an evaluation parameter that costs you 3% speed and then can you manage to speed up the engine by 3%, your evaluation was basically free.