How can I improve my engine’s speed?

[pedrojdm2021]

I've struggled with this before ( trust me, i even had nightmares with this, discussion with people about that in this forum ( i think i even made some people here get mad on me lol ) )

At the end what i learned is, use pre-calculated data as much as you can, skip as much nodes as you can, "prune" as much branches on your tree as much as you can,

having a good and optimized move generator is also a key to success on this, try to generate only legal moves, or generate few illegal moves ( and validate them in makemove(move) ) the more illegal moves you generate, the more time it will cost you

Check chessprogramming wiki topics on Pruning,
also look some other engines for reference, for example:
Demolito: https://github.com/lucasart/Demolito
Cosette: https://github.com/Tearth/Cosette

These two are VERY good with an amazing speed, and also their source code is pretty clean compared to others ( i know, they are not javascript engines, but the algorithms can be translated to any language )
so is good to learn from them

Good luck

[KhepriChess]

It looks like you're using bigints for your bitboards. The important thing here to realize, is that JS's implementation of arbitrary-precision arithmetic is INSANELY slow compared to it's regular (32-bit) integers. That's something that is immediately working against you.

In your `play` (and various piece's play) functions, you do a lot of loops. And in a number of them you have many conditional blocks. It's a little hard for me to understand what exactly is being done because I'm not familiar with the variable names, but with bitboards you shouldn't need to be doing loops or that many conditionals to move a piece. It's just a matter of removing the bit (clearing the "from" square) and adding the bit (the "to" square).

Remember that calling methods has overhead, so calling a method four times to move a single piece adds up.

Also, since you're using bigints, you might run into issues where you need to do some sort of operation using a number but you've passed in or have a bigint. You can convert between bigints and numbers, but realize that doing so is very slow so try to not do that as much as possible.

Because BigInts are arbitrary length, and not just 64-bit integers, sometimes doing an operation on two 64-bit bigints can give a non-64-bit result. Sometimes those results can completely mess up the engine, so you have to clamp them (with `.asUintN(64, [bigint])`. But remember that also introduces overhead.

Pruning and reductions are also your friend. Because JS is rather slow, searching nodes is costly and adds up quickly. You have to find that medium between pruning/reducing nodes so that you can actually search at a reasonable depth, but also not prune too many so you miss better moves. What pruning you have and how it's implemented is a slow learning process that entirely depends on your engine. Make one tweak, then test it. Repeat forever.

Also, as the previous comment mentioned: per-calculated data is your friend. Calculating stuff on-the-fly is fast for compiled languages. Not always the case with JS.

[zamfofex]

Hello, everyone! I wanted to say that, although I’m still quite a newbie at this, I actually learned a lot since last time! (Or at least it feels like a lot to me.)

I feel like I should respond to the message I received in this thread, however I will share some more information and updates on my bot’s thread, if that is okay.

In your `play` (and various piece's play) functions, you do a lot of loops. And in a number of them you have many conditional blocks. It's a little hard for me to understand what exactly is being done because I'm not familiar with the variable names, but with bitboards you shouldn't need to be doing loops or that many conditionals to move a piece. It's just a matter of removing the bit (clearing the "from" square) and adding the bit (the "to" square).

I suppose the confusion is that those loops are also generating moves, not only playing then on the board. In the version you looked at, the move generation is intertwined with the move playing as well as with the evaluation and even the search. (In newer versions, I changed it so that all of those are separate, which facilitates understanding by a lot.)

Remember that calling methods has overhead, so calling a method four times to move a single piece adds up.

That is fair, I was relying on the runtime inlining those functions, though I suppose I shouldn’t assume it will.

Also, since you're using bigints, you might run into issues where you need to do some sort of operation using a number but you've passed in or have a bigint. You can convert between bigints and numbers, but realize that doing so is very slow so try to not do that as much as possible.

Thankfully, that just simply doesn’t happen. I limit bigints to represent 64‐bit integerr for the purposes of bitboards exclusively, nowhere else are they used across the project, so the need to conve them simply doesn’t arrive.

Because BigInts are arbitrary length, and not just 64-bit integers, sometimes doing an operation on two 64-bit bigints can give a non-64-bit result. Sometimes those results can completely mess up the engine, so you have to clamp them (with `.asUintN(64, [bigint])`. But remember that also introduces overhead.

I’m not sure whether that was actually an issue before, but I have switched to using a ‘BigUint64Array’, so if it were an issue, it isn’t anymore.

Pruning and reductions are also your friend. Because JS is rather slow, searching nodes is costly and adds up quickly. You have to find that medium between pruning/reducing nodes so that you can actually search at a reasonable depth, but also not prune too many so you miss better moves. What pruning you have and how it's implemented is a slow learning process that entirely depends on your engine. Make one tweak, then test it. Repeat forever.

I have great news regarding this, but I’ll leave it for my other thread!

[JohnWoe]

I started improving speed of Havoc since it was too slow. Havoc is a 10x8 Gothic engine. No bitboards. make + unmake for moves, not copy-make.
I managed to get Havoc 2.5x faster by using following tricks:

- piecelists. I used to scan the whole board
- Checks flowing from king
- Keeping track of kings
- Hashing evaluation
- Lots of smaller things

I kept this as summary: 1.28 MNPS -> 2.9 MNPS

Code: Select all

/*
Nodes: 19286352
Time:  15011
NPS:   1284729

Nodes: 26272540
Time:  15013
NPS:   1749869

Nodes: 25441737
Time:  15010
NPS:   1694872

Nodes: 30033154
Time:  15013
NPS:   2000343

Nodes: 32422552
Time:  15012
NPS:   2159631

Nodes: 33647561
Time:  15011
NPS:   2241377

Nodes: 33892786
Time:  15015
NPS:   2257111

Nodes: 40695402
Time:  15011
NPS:   2710858

Nodes: 42897153
Time:  15013
NPS:   2857143

Nodes: 43850317
Time:  15014
NPS:   2920434
*/