I wrote some 'monomorphed' code for my chess engine which works perfectly: it is very very fast (much faster than without monomorphization so at least I did something right).
Of course the below code does not compile in rust playground because there is no Position.
However there are some filosophical issues / questions for me.
The code is 'unsafe' in a way that the current 'generate_moves' function is depending on the fact that I pass the consts C_WHITE or C_BLACK (0 or 1). Is it possible to let the const parameters be typed (with a trait or other 'type const' construction so that it is only possible to pass the type values WHITE or BLACK? Without sacrificing performance.
I also implemented a Not for Color, simply xoring the value. Would it be possible to eliminate the THEM const parameter and declaring THEM as a const inside the function?
In gen_moves() it would be nice if the match statement would contain just WHITE and BLACK and no 'unreachable' arm. (An enum is not an option because of too much internal stuff). Is that doable somehow?
(In this whole thing I trust the compiler to eliminate 'dead code' for white / black)
(I asked a similar question before, but I think it must be possible without 'nightly builds')
use std::ops::Not;
pub struct Position
{
pub to_move: Color,
// more fields...
}
impl Position
{
fn new() -> Self
{
Self
{
to_move: WHITE,
}
}
}
// lowest level consts
pub const C_WHITE: u8 = 0;
pub const C_BLACK: u8 = 1;
#[repr(transparent)]
#[derive(Default, Clone, Copy, PartialEq, Eq)]
pub struct Color(pub u8); // white = 0, black = 1
impl Color
{
pub const WHITE : Color = Color(C_WHITE);
pub const BLACK : Color = Color(C_BLACK);
// ... more impl code...
}
impl Not for Color
{
type Output = Color;
#[inline]
fn not(self) -> Self::Output
{
Color(self.0 ^ 1)
}
}
// just some 'easy' consts for shorter code
pub const WHITE : Color = Color::WHITE;
pub const BLACK : Color = Color::WHITE;
pub fn gen_moves(pos: &Position)
{
match pos.to_move // Position.to_move: Color
{
WHITE => generate::<C_WHITE, C_BLACK>(pos),
_ => generate::<C_BLACK, C_WHITE>(pos)
}
}
// current implementation:
fn generate<const US: u8, const THEM: u8>(pos: &Position)
{
if US == 0
{
println!("code for white");
}
if US == 1
{
println!("code for black");
}
}
// implementation I would like:
/*
fn generate_wished<const US: Color, const THEM: Color>(pos: &Position)
{
if US == WHITE
{
println!("code for white");
}
if US == BLACK
{
println!("code for black");
}
}
*/
fn main()
{
let pos: Position = Position::new();
gen_moves(&pos);
}
Too many conversions needed. in Move, Position, Piece etc. which makes it slower and less readable.
Also this was an minimal example, there are more of these monomorphizations in the program with other types.
bool is a perfect fit because there's only 2 colors/values so your checks will be exhaustive, allowing better optimizations.
If you insist on using the type system though, structs and a trait is the way to go:
trait PieceColor {
const IS_WHITE: bool;
}
struct White;
impl PieceColor for White {
const IS_WHITE: bool = true;
}
struct Black;
impl PieceColor for Black {
const IS_WHITE: bool = false;
}
in order to make piece colors statically known to compiler. Then instead of u8 use PieceColor as type.
If statements can then be:
fn generate<US: PieceColor>(pos: &Position)
{
if US::IS_WHITE {
println!("code for white");
} else {
println!("code for black");
}
}
where:
you don't need THEM generic - THEM::IS_WHITE is always !US::IS_WHITE.
Position.to_move() needs to return bool though, so it becomes Position.is_white_turn().
Do note that using generics for generate_wished doesn't actually yield faster code because gen_moves function has branching anyway. This only makes sense if you have multiple functions using similar branching that are called from multiple places. If you had branching in both places, it is better though. You can also just use a single const IS_WHITE: bool generic in generate though.
So, enum seems like the best approach.
If you use #[repr(u8)] you don't need to do any conversions:
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[repr(u8)]
enum PieceColor {
Black = 0,
White = 1,
}
impl PieceColor {
#[inline(always)]
pub fn as_u8(self) -> u8 {
// this is 0 cost
self as u8
}
}
Also, given that it's chess and the order of player moves is known at compile time, you could get away with making Position statically store the to_move information:
This would allow you to fully statically encode the turn information in the type system and the compiler could go nuts with optimizations for each side - you'd remove branching over colors in all functions.
Flippable2DPieceArray could be even further optimized, but I'll let you write some code yourself
Thanks. very clear!
I have been thinking about making color a bool and will consider it again.
The conversions at other places I have to rewrite then.
For example Piece = 1..6 and 8..14. the "black bit' is bit #3.
To let the compiler go nuts on optimization is too much.
To copy the board when making a move would cost too much. However the idea could be applied maybe in other area's of the program.
Edit: The 'color' monomorphization is in the rest of the program applied as well.
Like Position.GetPawns etc. etc.
If you use #[repr(u8)] you don't need to do any conversions:
Wow! I did not know that! I will have a look into that!
Storing pieces in an enum with a Blank variant is also a good idea, you don't need to waste (your and compute) time fiddling with bits. You could make the least significant bit represent color though but the performance gain from that is not really that big.
There's no copy. You can safely use std::mem::transmute between turns in this case as it's only type information you're changing:
impl Position<Black> {
pub fn move(self, from: Location, to: Location) -> Position<White> {
// change the Flippable2DPieceArray data... (check, remove, add, ...)
if self.pieces.check_if_can(from) {
let piece = self.pieces.get(from);
self.pieces.set(from, Piece::Blank);
self.pieces.set(to, piece);
} else {
return Err(); // ok, the type changes, you propagate "invalid move" info, ...
}
// and then we simply change the type, which gets compiled away
unsafe {
return std::mem::transmute<_, Position<White>>(self);
}
}
}
Sounds very promising, this transmute, however I keep a history of states in a Vec (a field of Position) which grows with make_move and shrinks when unmake_move, so I am not sure if this transmute still works then?
The moves (a bitpacked u16 struct) I pass to make_move must be valid.
The pieces is a simple 64 sized array of Piece, together with some 64-bits bitmasks (bitboards).
Yeah, storing the current position is completely detached from actual data. It's only used to make the compiler generate two separate implementations. You can do whatever you want with the contained data between moves.
In my example, I use transmute in order to avoid copying, but treat it as "setting the value" of the generic.
