Lessons learned

[hgducharme]

CPPFLAGS are flags that are passed to the C PreProcessor CXXFLAGS are flags that are passed to the C++ compiler

[hgducharme]

Prefer out-of-source builds for compiled projects. It's so much easier when using version control and keeping build artifacts separate from source files

[hgducharme]

Compiling and Linking

Consider the directory tree

.
├── Makefile
├── bin
│   ├── project.out
│   └── tests.out
├── build
│   ├── src
│   │   ├── class1.o
│   │   └── main.o
│   └── test
│       └── test_class1.o
├── src
│   ├── class1.cpp
│   ├── class1.h
│   └── main.cpp
└── test
    └── test_class1.cpp

Suppose:

• main.cpp includes class1.h
• test_class1.cpp includes class1.h

Making the project.out executable

Working backwards:

1. In order to create the bin/project.out executable, we have to link together the build/src/class1.o and build/src/main.o files.
2. To create the class1.o file we have to compile the class1.cpp file
3. To create the main.o file we have to compile the main.cpp file

# Compile class1.cpp
clang++ --compile src/class1.cpp --output build/src/class1.o

# Compile main.cpp
clang++ --compile src/main.cpp --output build/src/main.o

# Link them together to produce an executable
clang++ build/src/class1.o build/src/main.o --output bin/project.out

You can compile implicitly like

clang++ /src/main.cpp /src/class1.cpp --output /bin/project.out

but then you don't get .o files. Not quite sure the cons of this approach.

Making the tests.out executable

Working backwards:

1. In order to create the bin/tests.out executable, we have to link together the build/src/class1.o and build/test/test_class1.o files.
2. To create the class1.o file we have to compile the class1.cpp file
3. To create the test_class1.o file we have to compile the test_class1.cpp file

# Compile class1.cpp
clang++ --compile src/class1.cpp --output build/src/class1.o

# Compile test_class1.cpp
clang++ --compile test/test_class1.cpp --output build/test/test_class1.o

# Link them together to produce an executable
clang++ build/src/class1.o build/test/test_class1.o --output bin/tests.out

[hgducharme]

Helpful stackoverflow post for more

When dealing with binary data and bit patterns in C/C++, people will generally represent these with hexadecimal (e.g. "0xffff0000") or octal numbers. There's a direct mapping between hex/octal numbers and bit patterns that makes the code a bit more readable and understand, which isn't available when you use decimal values (e.g. "4571894638") to represent bit patterns.

Binary literals weren't around in C until C23 and C++ until C++14. We have access to binary literals now but this is why you will see hex/octal numbers floating around. To see how to use binary literals go here.

Tangentially related, a bitmask is just a value that is used with another value to perform certain operations on the bits of the second value. Think of it like a linear operator in linear algebra: you apply the linear operator A to a vector x in order to perform some operation on that matrix and get the resulting vector b (Ax = b).

[hgducharme]

See cppreference on binary arithmetic operators for best practices on overloading bitwise operators

[hgducharme]

If a function definition returns a reference like

X & function()

but you don't specify a reference when calling it, you will not get a reference to the original value. You will copy it maybe?

// Will store the value in a NEW value called var. Any modifications to var will not modify the original value
X var = function();

// Will obviously return a reference to the original value. Any modification to var will modify the original value
X & var = function();

[hgducharme]

Interfaces vs Templates

In other words, run-time polymorphism vs compile-time polymorphism.

When to use an interface vs a template?

Some takeaways:

• Consider templates if runtime performance is at a premium
• If you need to swap out implementations at runtime, use an interface. Otherwise, if you know your implementations at compile time, then consider a template
• Some drawbacks from templates: need to be defined in header files and require recompilation every time the header file changes, cause code bloat, and are often a bit more difficult to understand

What is the performance penalty when using templates over an interface

• I like this quote from the above link: "The extra clarity that you will recieve from using an interface usually makes up for any perceived speed decrease."

[hgducharme]

Bitboard class design

I'm starting to question my use of my Bitboard class that acts as a wrapper for the primitive type uint64_t. I like the syntactic sugar it provides such as

Bitboard blackPawns(DEFAULT_BLACK_PAWN_STRUCTURE);
blackPawns.setBit(3);
blackPawns.numberOfSetBits();
blackPawns.findIndexLSB();

instead of

u64 blackPawns = DEFAULT_BLACK_PAWN_STRUCTURE)
setBit(blackPawns, 3);
numberOfSetBits(blackPawns);
findIndexLSB(blackPawns);

Concern

I'm concerned about future performance. I'm starting to see that I need to instantiate the class just to represent something as a uint64_tand pass that to something else. I feel like this is unnecessarily using a lot of stack memory which will catch up to me later on by causing speed issues in the engine.

I'm wondering if I should spend the time now to get rid of the class and just use using Bitboard = std::uint64_t, or if using the wrapper class should be fine moving forward.

Research

Here are some good reads:

• C++ class wrapper around fundamental types
  • The wrapper class won't experience any performance overhead as long as the function bodies are short enough to be inlined. Also, there's no real memory concern because the wrapper class isn't polymorphic. If it was polymorphic then it would maintain a virtual table pointer in order to resolve function calls down the inheritance hierarchy. In order to get the wrapper class to behave identical to the primitive type it seems like a LOT of work is needed (overload all of the operators)
• Why you should prefer non-friend non-member functions to member functions
  • This is an argument against the wrapper class. The wrapper class is simply just adding convenience functions (which could be non-friend non-member functions) for the underlying internal primitive type.
• Performance: typedef vs wrapper class for primitive types?
  • There will be a performance hit if the wrapper class member functions can't be evaluated by the compiler. This will be the case if the functions aren't constant expressions
• Someone who made a well designed primitive wrapper class with as little performance hits as possible

Wrapper class consensus

• Apparently, there will be performance loss using a wrapper class if:
  • The wrapper class member functions can't be inlined
    • in order for the member functions to be inlined, they need to be extremely short and also defined in the header (so the compiler can see them). If they're declared in the header and then defined in the source file then the compiler won't be able to see the function definition at compile time. At least, this is true for naive compilers. Modern compilers can optimize this away but sometimes that's expensive and not always supported
  • The wrapper class is polymorphic
  • The wrapper class member functions aren't constant expressions
    • If the functions aren't constant expressions then they have to be evaluated at runtime, which will (to some degree) be worse performance compared to having the compiler evaluate them at compile time
• This class can be made to have better encapsulation if the convenience functions like Bitboard::clearAndReturnMSB() are made to be non-friend non-member functions, or at least friend non-member functions

Conclusion

Although this might be a bad design, I'm going to continue with it for now. Once i get a minimum viable product I can profile the code and see if this is a bottleneck. If so, we will optimize it later, but not now

[hgducharme]

• Strategy pattern: when you need to swap out behavior implementations during runtime (e.g. the payment system needs to pay with paypal, venmo, card, or cash during runtime)
• Template pattern: when you have an algorithm with invariant parts and need to slightly modify parts of the algorithm depending on the strategy being used (e.g. you have a mostly invariant algorithm for setting up a game character, but some characters need a little additional initialization during the creation process)
• Template meta-programming: when an algorithm will work with different variable types, use templates

Side note:

• Keep in mind policy based design. This is also a good book for learning how to write well designed code in c++.
• I liked this answer's part about reminding oneself to not get carried away.

[hgducharme]

Magic bitboards

Process

1. Create the bitmask representing the squares that could block the current piece from moving. Commonly called the relevant occupancy bits, or the relevant occupancy set. For example, for a rook on A1, the relevant occupancy set would be the squares A2-A7 and B1-G1. They is the key to the hash map.
2. Generate the index that will be used to lookup the piece's attack set for a given blocking configuration. To do this, multiply the relevant occupancy bitmask by a "magic number" (see below for finding magic numbers)
3. Hash the index to reduce the size of the tables. To do this, right shift the resulting product by 64 - n bits, where n is the number of bits in the resulting product i.
4. Use the index i generated in step 3 to access a pre-initialized move database

What are "magic numbers"

The goal of a magic number is such that when it is multiplied against an occupancy mask, it maps the scattered placement of occupied bits into a consecutive ordering in the most significant bit positions. This function, which maps the relevant occupancy set to a range of attack-sets per square, is surjective. The equation is:

index = (occupancy set * magic number) >> (64 - number of bits in occupancy set)

For example, consider a bishop on B1:

                                          any consecutive
relevant occupancy                        combination of
for bishop on b1,     magic number        the masked bits
5 bits
. . . . . . . .      . . . . . . . .     . . .[C D E F G]
. . . . . . . .      . 1 . . . . . .     . . . . . . . .
. . . . . . G .      . 1 . . . . . .     . . . . . . . .
. . . . . F . .      . 1 . . . . . .     . . . . . . . .
. . . . E . . .   *  . 1 . . . . . .  =  . . garbage . .   >> (64- 5)
. . . D . . . .      . 1 . . . . . .     . . . . . . . .
. . C . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .      . . . . . . . .     . . . . . . . .

An example

Consider a rook on A1, then the relevant occupancy mask, or the potential blocker squares are:

0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0

Finding magic numbers

Resources

• Chess programming wiki
• This blog post
• A second blog post

[hgducharme]

Question: What is the performance difference between k for loops all with simple instructions versus one for loop with all instructions inside it, and all for loops have the same amount of iteration loops?

Research

• Stack exchange
• Stack exchange 2

Consensus Apparently k multiples of a for loop can theoretically be faster than one for loop with a lot of complex instructions. Both situations are obviously O(n), but there might be slight optimizations that can be made. I suppose it really depends on the context and this is kind of considered a micro optimization, which shouldn't be done unless you profiled the code and have evidence that one is a bottleneck compared to the other.

Decision I personally sort of like the idea of multiple for loops with simple instructions in them because it allows me to write functions with good encapsulation and naming, and therefore aiding in readability and maintainability. I suppose I will go ahead with that route and can profile the code if this is slow and I need it to be faster.

[hgducharme]

Apparently you can't initialize C++ arrays (in shorthand) with a value other than zero. That is, the following would not behave as you expect

int myArray[10][10] = { {50} };

The first element would be 50 but all other elements would be zero. You can use std::fill to set all elements to 50. For a concise answer on why, see this stackoverflow answer.

[hgducharme]

Cool video on psuedo random number generation in c++ and why rand() is harmful

[hgducharme]

constexpr functions require a return type that is considered a literal type.

[hgducharme]

• Profiling: analyzing a program to see how long certain parts of the program take to execute. The result of a code profile might be a table of the functions that are being executed and how much time each function took to execute
• Benchmarking: analyzes how fast some operation takes to run. The result of a benchmark should be a singular value
• Microbenchmarking: measuring the performance of one super specific task, in isolation from anything else.

https://stackoverflow.com/questions/34801622/difference-between-benchmarking-and-profiling

[hgducharme]

Static keyword

On class member functions and variables: defining a class member function or variable as static means it belongs to the class and not any particular instance of the class

On non-member functions and variables: defining a non-member function or variable as static means it only has internal linkage and will not be used outside of its translation unit. This use of static has been replaced by anonymous namespaces, but they both do exactly the same thing. The benefit of using static is that it's clear by function definition alone that it has internal linkage, and there's no need to scroll up or down to see if it's contained in an anonymous namespace.

[hgducharme]

Have learned a lot about docker implementing this CI pipeline. There's some super niche quirks when integrating with Github Actions.

One thing that was tripping me up was that I was defining a non-root user in my docker containers but this doesn't work on Github Action servers, as detailed in this article.

[hgducharme]

Namespaces

Ok wow just had to detangle the biggest mess with an unnamed namespace nested within a named namespace and split between the interface file .h and the implementation file .cpp

What I had before:

// .h

namespace xyz {
   void a();

   namespace {
      void b();
      void c();
   }
}

// .cpp

namespace xyz {
   void a() { b(); }

   namespace {
      void b() { c(); }
      void c() { ... }
   }
}

Technically this will compile and work just fine but you will get the error in the header file for b() saying it was declared static but never defined, and therefore it's an unused function.

Ultimately you're not supposed to put anonymous namespaces in header files, so I went ahead and removed the anonymous namespace from the header file, but then in the source file you will get the error that b() is not defined in the scope of a(), and therefore a() can't call b(). The issue here is that now our function definitions simultaneously become declarations also, and since c++ presumably parses the file from the top down, then it hasn't seen the declaration for b() when it parses a(). Therefore, you need to move the anonymous namespace to the top of the named namespace. However, you will still have the function ordering problem within the unnamed namespace. You must also keep the unnamed namespace inside the named namespace for a() to see b().

TLDR: The following is what works

// .h

namespace xyz {
   void a();
}

// .cpp

namespace xyz {

   namespace {
      void c() { ... }
      void b() { c(); }
   }

   void a() { b(); }
}

[hgducharme]

Array of structs vs array of pointers to structs

Cool discussions on array of structs vs array of pointers to structs:

• 1
• 2

Ran into this question when considering how I should manage BISHOP_HASHING_PARAMETERS_LOOKUP and ROOK_HASHING_PARAMETERS_LOOKUP. Right now they are arrays of structs, and I will just keep it like that until I profile the code and see where bottlenecks are

[hgducharme]

Interfaces vs Abstract Base Classes (ABC) in C++

• Abstract base class (ABC; also called abstract class): a c++ class that contains a pure virtual function
• Interface (also called a pure abstract class): a c++ class that contains only pure virtual functions and a virtual destructor (doesn't have to be pure virtual)
• Virtual function: a member function that declared in a base class that can be overridden
• Pure virtual function: a member function declared in a base class that has no definition, and must be overridden by a child class

class Abstract
{
   Abstract();
   ~Abstract();
   void functionWithADefinition { does stuff... };
   virtual void virtualFunctionWithDefinition { does stuff... };
   virtual void pureVirtual()  = 0;

   // Abstract classes can contain member variables
   int memberVariable = 0;
}

class Interface
{
   virtual ~Interface() = 0; // or virtual ~Interface() {};
   virtual void pureVirtual1() = 0;
   virtual int pureVirtual2()  = 0;
}

Both abstract classes and interfaces define the concept of an interface (or API) to clients that use them, the only difference is that abstract classes have pre-packaged functionality that is shared between implementations. Use an interface if there is no shared functionality. Use an abstract class if there isn't one.

All interfaces (pure abstract classes) are abstract classes, but not all abstract classes are interfaces. Before using either, make sure the implementations has an is-a relationship with the parent class.

Using abstract classes in client code

Consider the abstract class Animal with two implementations Dog and Cat. To instantiate an implementation but specify the base type Animal, you must dynamically initialize it (as opposed to statically).

int main()
{
   // Static initialization with automatic storage duration; this will not work
   Animal dog();
   Animal dog = Dog();

   // Dynamic initialization with dynamic storage duration; this will work
   Animal * dog = new Dog();
   delete dog;

   return 0;
}

To use a base class as a parameter type to a function, the object must by reference or pointer

void function(Base * derivedObject); // works
void function(Base & derivedObject); // works
void function(Base derivedObject); // will not work

The cleanest way to only use the interface type in client code seems to be by using a factory, as shown in this answer

// position_evaluator.h

namespace interfaces { class PositionEvaluator { ... }; }
enum class EvaluatorImplementation { NeuralNetwork, Minimax };
class NeuralNetwork : public interfaces::PositionEvaluator { ... };
class Minimax : public interfaces::PositionEvaluator { ... };
interface::PositionEvaluator * createPositionEvaluator(EvaluatorImplementation implementation) { ... };

// search_algorithm.h

namespace interfaces { class SearchAlgorithm { ... }; }
enum class SearchImplementation { MonteCarloTreeSearch, MonteCarloGraphSearch};
class MonteCarloTreeSearch : public interfaces::SearchAlgorithm { ... };
class MonteCarloGraphSearch : public interfaces::SearchAlgorithm { ... };

// A search algorithm requires a PositionEvaluator & to be passed to the constructor
// Technically a factory should abstract away all details about creating dependencies for the object it's going to create,
// but it's not horrendous to pass in a dependency
interface::SearchAlgorithm * createSearchAlgorithm(SearchImplementation implementation, PositionEvaluator & evaluator) { ... };

// main.cpp
#include "search_algorithm.h"
#include "position_evaluator.h"

int main()
{
   // These could probably even return references
   // If using pointers, the most responsible thing to do would be to return an std::unique_pointer<PositionEvaluator> and std::unique_pointer<SearchAlgorithm>
   PositionEvaluator * neuralNetwork = createPositionEvaluator(EvaluatorImplementation::NeuralNetwork);
   SearchAlgorithm * monteCarloTreeSearch = createSearchAlgorithm(Implementations::MonteCarloTreeSearch, (*neuralNetwork) );

   return 0;
}

But this has gotten absolutely insane for something that's known at compile time. It does massively improve readability and modularity, however

[hgducharme]

Software architecture vs software design

• Architecture: defines what is being built. This can include requirements, the abstractions/modules that need to be present, what components are interacting with other components, what programming language is being used, and doesn't define the specifics of a component really at all etc. (see: architectural patterns
• Design: defines the specifics of how a module/component is going to be implemented (see: design patterns and SOLID)

When this is ultimately turned into a technical presentation, the lessons learned should be formatted by categories:

1. System architecture lessons (e.g. how the different modules of the system interact with each other)
2. System design lessons (e.g. the design patterns used within just one module)
3. Programming lessons (e.g. compiler things, programming language things, C++ specific things)
4. Math theory lessons (e.g. machine learning, algorithms)
5. Chess specific