Any engines with a "mostly functional" style of code?

[lojic]

In my professional coding, I typically use functional programming, so my functions operate only on their arguments and have no "side effects" outside of the function. They also tend to be relatively small with well defined purposes. However, most of the chess engine source code I've come across is full of global variables and side effects with very long functions, and it makes it more difficult to understand the code because you have to track down all sorts of variable references, and try to get an idea of where they may be modified, etc.

I realize this may be motivated by efficiency concerns (large functions to avoid functional call overhead in languages where it may be expensive, and global variables to avoid the cost of copying, etc.), and in some cases, a functional programming style can be a little less efficient (i.e. if you're creating new data structures vs. mutating existing ones, etc.).

I'm struggling a bit trying to strike a balance between my typical functional programming style, and a style that optimizes speed while still being very readable, testable & easy to understand. Are there examples of engines that play reasonably well while minimizing global variables and side effects?

I expect my current frustration is is due primarily to not fully understanding some of the algorithms, and once I do, I should be able to structure the code to my liking.

[emadsen]

I realize (code that causes side effects) may be motivated by efficiency concerns (large functions to avoid functional call overhead in languages where it may be expensive, and global variables to avoid the cost of copying, etc.), and in some cases, a functional programming style can be a little less efficient (i.e. if you're creating new data structures vs. mutating existing ones, etc.)

In my day job, I'm a fan of the functional programming style. I don't believe object-oriented design, even for business programming, is the end-all-be-all of software architecture. I like to sprinkle functional techniques into my OO code. But I don't buy into the "never mutate state" doctrine of functional programming. Often the entire point of a business application or systems integration is side effects. There's no business value without the side effect (update a record, sync data, etc). So I guess I buy into functional programming "a la carte": That is, I like to use lambda methods, closures, anonymous methods, etc. They are good substitutes for making everything a class and forcing consuming code to sub-class everything... too much ceremony. OO techniques do help control complexity in a large codebase, but sometimes OO is just too damn wordy. The functional style is more concise yet still readable.

Having said that...

In a chess engine, the functional programming style will be much worse than "a little less efficient". It will be terribly slow. In the world of chess engine programming, speed is king. A functional programming style (no in-place mutations of data structures) will kill an engine's strength.

You should not allocate any memory on the heap, at all, while in the search method or any method called from it.

I don't even use lambda methods in my engine's C# codebase. Lambdas allocate memory (that must be garbage-collected) every time they're encountered. That would kill performance in the tight loop of a chess engine's search method. Instead, I pre-allocate a delegate instance:

Code: Select all

public delegate (ulong Move, int MoveIndex) GetNextMove(Position Position, ulong ToSquareMask, int Depth, ulong BestMove);
private Delegates.GetNextMove _getNextMove = GetNextMove; // <- Assign the GetNextMove method to the delegate.
private Delegates.GetNextMove _getNextCapture = GetNextCapture; // <-- Assign the GetNextCapture method to the delegate.

Then invoke one or the other delegate instance:

Code: Select all

Delegates.GetNextMove getNextMove;
ulong moveGenerationToSquareMask;
if (Board.CurrentPosition.KingInCheck)
{
    // King is in check.  Search all moves.
    getNextMove = _getNextMove;
    moveGenerationToSquareMask = Board.AllSquaresMask;
    // Don't evaluate static score since moves when king is in check are not futile.
    Board.CurrentPosition.StaticScore = -StaticScore.Max;
}
else
{
    // King is not in check.  Search only captures.
    getNextMove = _getNextCapture;
    // ...
}
// ...
do
{
    var (move, _) = getNextMove(Board.CurrentPosition, moveGenerationToSquareMask, Depth, Move.Null); // Don't retrieve (or update) best move from the cache.  Rely on MVV / LVA move order.
    if (move == Move.Null) break;
    if (Board.IsMoveLegal(ref move)) legalMoveNumber++; // Move is legal.
    else continue; // Skip illegal move.
    if (ConsiderFutility && IsMoveFutile(Board, Depth, Horizon, move, legalMoveNumber, 0, drawnEndgame, Alpha, Beta)) continue; // Move is futile.  Skip move.
    // Play and search move.
    Board.PlayMove(move);
    var score = -GetQuietScore(Board, Depth + 1, Horizon, ToSquareMask, -Beta, -Alpha, GetStaticScore, ConsiderFutility);
    Board.UndoMove();
    if (Math.Abs(score) == StaticScore.Interrupted) return score; // Stop searching.
    if (score >= Beta) return Beta; // Position is not the result of best play by both players.
    Alpha = Math.Max(score, Alpha);
} while (true);

Functional programming techniques are great. I just wouldn't use them in a chess engine.

But of course, the beauty of writing your own chess engine is you can choose how to write it. It's yours. So please take what I said above as a suggestion, so you can make an informed decision, not a command. To each their own!

[lojic]

I realize (code that causes side effects) may be motivated by efficiency concerns (large functions to avoid functional call overhead in languages where it may be expensive, and global variables to avoid the cost of copying, etc.), and in some cases, a functional programming style can be a little less efficient (i.e. if you're creating new data structures vs. mutating existing ones, etc.)

...
Having said that...

In a chess engine, the functional programming style will be much worse than "a little less efficient". It will be terribly slow. In the world of chess engine programming, speed is king. A functional programming style (no in-place mutations of data structures) will kill an engine's strength.

You should not allocate any memory on the heap, at all, while in the search method or any method called from it.

Yes, of course. I should've clarified what I meant by a "mostly" functional style :)

Even though "premature optimization" can be a bad thing, I knew early on that, for a chess engine, speed was going to be important, and the typical lisp way of using pure functions, creating new data structures vs. mutating existing ones, etc. would be too slow, so for example, in my state, I pre-allocate fixed size vectors for each ply to hold moves (which are simply integers), etc. I'm allocating very, very little in the speed sensitive portions of the code. I've been able to pack most things into a fixed integer of bits.

I was primarily referring to minimizing the use of global variables, and having smaller functions. Scheme has very efficient function calls (it also has a very efficient garbage collector that I'm not using much :) ), and it has nice function inlining features, so breaking a large function into smaller, well defined, functions isn't too costly.

In my opinion, it makes code easier to reason about when variables are passed to the function vs. referring to global variables - even if you're passing pointers to minimizing copying.

[emadsen]

In my opinion, it makes code easier to reason about when variables are passed to the function vs. referring to global variables - even if you're passing pointers to minimizing copying.

Totally agree.

And like you said, the function inliner helps too. I even provide hints to the compiler for small functions in the hot path.

Code: Select all

[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static bool IsPassedPawn(Position Position, int Square, bool White)
{
    Debug.Assert(Position.GetPiece(Square) == (White ? Piece.WhitePawn : Piece.BlackPawn));
    return White
        ? (Board.WhitePassedPawnMasks[Square] & Position.BlackPawns) == 0
        : (Board.BlackPassedPawnMasks[Square] & Position.WhitePawns) == 0;
}

[mvanthoor]

Yes, of course. I should've clarified what I meant by a "mostly" functional style

I'm with Eric here. Personally, I don't like dogmatic approaches.

- I don't like it if a program has to be fully object-oriented
- I don't like it if a program has to be fully functionally written
- I also don't like it if the language has no options for new/modern concepts

If a programming language is fully object-oriented, even in places where it doesn't have to be (like, shoe-horn everything into an object, provide an interface for everything, build a class hierarchy), then this makes the program too complex. If a programming language goes for the full-on functional approach with 0 mutability and no side-effects, this will make the program too slow. If a programming language has no room for modern concepts, it's essentially stuck in the past.

It's actually why I like Rust so much: it doesn't stick to a single dogma. You want something that looks/works like an object? OK.

Code: Select all

struct Stuff {
	thing: u8
}

impl Stuff {
	pub fn new() {...}
	pub fn get() {...}
	pub fn set() {...}
}

Want a bit of polymorphism with the use of interfaces? Sure.

Code: Select all

trait IStuff {
	fn do_something() -> u8;
	fn more_stuff() -> u32;
}

struct Stuff {
	thing: u8
}

impl Stuff {
	pub fn new() {...}
	pub fn get() {...}
	pub fn set() {...}
}

impl IStuff for Stuff {
	fn do_something -> u8 { ... }
	fn more_stuff -> u32 { ... }
}

Every struct, enum, or whatever that implements IStuff can be used in place of other objects that implement IStuff.

You want to do some functional-like stuff? Why not...

Code: Select all

     let mut fen_parts: Vec<String> = match fen_string {
            Some(f) => f,
            None => FEN_START_POSITION,
        }
        .replace(EM_DASH, DASH.encode_utf8(&mut [0; 4]))
        .split(SPACE)
        .map(|s| s.to_string())
        .collect();

This is actually the entire initialization for my Zobrist hashes:

Code: Select all

    pub fn new() -> Self {
        let mut random = ChaChaRng::from_seed(RNG_SEED);
        let mut zobrist_randoms = Self {
            rnd_pieces: [[[EMPTY; NrOf::SQUARES]; NrOf::PIECE_TYPES]; Sides::BOTH],
            rnd_castling: [EMPTY; NrOf::CASTLING_PERMISSIONS],
            rnd_sides: [EMPTY; Sides::BOTH],
            rnd_en_passant: [EMPTY; NrOf::SQUARES + 1],
        };

        zobrist_randoms.rnd_pieces.iter_mut().for_each(|side| {
            side.iter_mut().for_each(|piece| {
                piece
                    .iter_mut()
                    .for_each(|square| *square = random.gen::<u64>())
            })
        });

        zobrist_randoms
            .rnd_castling
            .iter_mut()
            .for_each(|permission| *permission = random.gen::<u64>());

        zobrist_randoms
            .rnd_sides
            .iter_mut()
            .for_each(|side| *side = random.gen::<u64>());

        zobrist_randoms
            .rnd_en_passant
            .iter_mut()
            .for_each(|ep| *ep = random.gen::<u64>());

        zobrist_randoms // <- returns the randoms here
    }

As you can see, it is not 100% functional, because each piece of code mutates the zobrist_randoms; had I wanted to, I could have strung everything together into one massive completely functional statement-thing, but I didn't want to, because that makes it unreadable / hard to understand for me. Rust has functional-style iter, filter, map, reduce, closures/anonymous functions/lambda functions, and can return functions from functions. (And thus also has higher-order functions.) I think you -could- write your program like 90% functional if you so wanted to, but I don't know for sure; I have never tried.

Or do you want to go old-style? Fine...

Code: Select all

fn main() -> u8 {
	let x = 5;
	
	do_whatever(5);
	extra_things();
	
	0
}

fn do_whatever(v: u8) { ... }
fn extra_things()

Whatever you want.

I use everything. Some things are object-like structs, such as my board, and hash table. Other things are completely procedural such as the "misc" module, because it collects miscellaneous functions, or the print module, that collects functions for printing things (half of that has functions annotated with "aloow_dead_code", because they're used while developing/debugging only). And within functions, I actually try to stick to some of the functional stuff like iter/map/filter/zip/etc... if possible, so I don't have to worry about bounds checking and defining each step myself. It works in Rust because the compiler strips all of it away. The language has zero overhead abstractions. (But I'm not going to go out of my way to use an iterator/map construct, if a "for i in 0..x { ... } construct is much easier to write and understand in that particular case.)

Oh, by the way: Rust does not allow global variables. You can have global things such as constants or static stuff if you want, but you can't change it. If you want global, mutable stuff, you have to go unsafe. That is the reason why I have an engine struct/object, and I do things like passing a reference to my move generator to make_move and perft. It can't be just initialized "somewhere" in the global outer space and be called from anywhere. Actually; with the crate lazy_static, that is possible, and it uses some unsafe tricks under the hood. However, if you use that, every call will need an extra indirection / dereference, which will make the program a lot slower. Therefore I haven't used lazy_static yet. I'd only use this in non-critical parts of the engine, such as holding global defaults (if const isn't enough for some reason) during engine startup.

[nionita]

In a chess engine, the functional programming style will be much worse than "a little less efficient". It will be terribly slow. In the world of chess engine programming, speed is king. A functional programming style (no in-place mutations of data structures) will kill an engine's strength.

I wrote a chess engine in Haskell, https://github.com/nionita/Barbarossa. It is not a speed monster, but sometimes beats programs written in C

[lojic]

In a chess engine, the functional programming style will be much worse than "a little less efficient". It will be terribly slow. In the world of chess engine programming, speed is king. A functional programming style (no in-place mutations of data structures) will kill an engine's strength.

I wrote a chess engine in Haskell, https://github.com/nionita/Barbarossa. It is not a speed monster, but sometimes beats programs written in C ;-)

That's awesome - impressive rating for a Haskell program! I've written a fair number of smallish Haskell programs, but your Haskell code is a bit advanced for me to easily follow it.