Don't knights need at least a 12x12 board? You can overlap the 0th column with the 10th column of the previous line and go down to 10x12, but 10x10 would cause out of bounds accesses.

10x12 (10 columns, 12 rows) is sufficient, because of wraparound.

You are 100% right.

I am skeptical about the idea of starting with king, bishop and knight versus king. Winning this endgame from an arbitrary start position requires something like 25 moves / 50 ply. Brute force minimax plus alpha beta will struggle to do that in a reasonable amount of time without sophisticated pruning. And you can't progress gently to the goal starting with simple 2 or 3 ply calculations because mate is the only point of the calculation here, normal material and positional factors are irrelevant. It makes more sense to first make sure your engine can win material with a simple knight fork say, and build from there to multi move material winning combinations. Followed by pursuit of positional goals when material gain is impossible (control the centre, seek scope for the pieces etc.). The elementary mates are actually a problem area for engines because they require a rather atypical strategical approach, cutting off the king, bringing your king around, shrinking the box, eventually forcing mate.

I meant that example as the end stage of when the training wheels can come off. Before that, of course, you start with even simpler examples, king + knight vs king would be the best starting point.

I don't understand your point. King plus knight v King is completely pointless, no move for either side is any better than any other. In fact the game should simply be declared a draw and no more moves should be played. What possible value does it have? Test the ability to generate legal moves maybe?

I guess the GP meant queen, not knight.

Hadn't thought of that. Amusingly the classic chess algorithms even fail to mate with Q+K v K for reasons I discuss up thread. Eg Sargon 1978 version can't do it. It's basically a terrible idea however you slice it because these mates are a special skill, almost like a different game with different ideas to the rest of chess.

>- A 10x10 board with an unreachable edge has some advantages when laid out as a linear array because it allows for much easier memory management (premature optimizations and all that...). On an 8x8 board laid out linearly the edges have no way of limiting piece movement

But with an 8x8 board you can store all free fields in a single 64-bit integer

That could be fast, would it not?

There's quite a few tricks on that front: https://www.chessprogramming.org/Magic_Bitboards

That's worth benchmarking. 10x12 as mentioned above would require two of those.

- A simpler but much faster engine will beat a more complex engine any time because the advantage of another ply easily outweighs the advantage of some clever algo.

Tell that to AlphaZero

There is a bit of a difference between the likes of AlphaZero and what your average hobbyist programmer is going to cook up. Once your toolbox includes bits like 'custom hardware' the equations change. Also: that was still a wicked fast machine in terms of the number of positions evaluated by any normal standard.

Certainly AlphaZero was run on very fast hardware and lots of it. Nevertheless, I think it shows that the days of "speed is all that matters" is over. It did substantially fewer evals than stockfish and still crushed it. LC0 is the same way. Neural network chess proved that a higher quality, much more expensive, eval (with a very high quantity baseline, to be sure) is a viable strategy for a chess engine.

It still would lose to brute Force with minimax

That’s simply not true for the same amount of hardware, or else that would be all that chess engines do

Tell that to Stockfish NNUE :P. A simpler neural network running at Stockfish speeds, all on CPU, crushes Lc0 (Lc0 is probably stronger than AlphaZero IMO).

NNUE is slower than the classic evaluation function though, and much better.

But alphazero is still using some kind of min-max, right? It's not a net that you input a board into and get a move out, but a net you input a board into and get a score out. So in a stockfish context it's mostly replacing the heuristic/scoring function?

> It's not a net that you input a board into and get a move out, but a net you input a board into and get a score out.

It's both actually. The former helps guide the search (MCTS, not an Alpha-Beta minmax), and the latter helps truncate the search before an end state.

For what it's worth, there is a pretty solid conventional wisdom in this space.

> - A simpler but much faster engine will beat a more complex engine any time because the advantage of another ply easily outweighs the advantage of some clever algo.

Depends a lot on what you call "simple". Stockfish's search and evaluation subroutines are pretty complex and distinctly clever:

https://github.com/official-stockfish/Stockfish/blob/master/...

https://github.com/official-stockfish/Stockfish/blob/master/...

But I agree that early on, simple is the way to go. It's much easier to optimize a simple engine.

> - A 10x10 board with an unreachable edge has some advantages [...]

Maybe in theory, but FWIW I don't know of any modern engine that does this. A more popular variant of the 10x10 or 10x12 idea was, back in the day, the 0x88 layout:

https://www.chessprogramming.org/0x88

If you're going to be writing an engine today from scratch, use the bitboard representation. It's easy to implement and has the most resources out there if you need help.

(Bitboards is just the idea of representing the game state as a bunch of 64-bit ints, with one u64 per white/black type of piece.)

Your example use-case, of knight posisitions, is usually solved with bitboards using an 64-element array mapping squares to a bitboard of all the places a knight on that square can go. Here's where Stockfish does that:

https://github.com/official-stockfish/Stockfish/blob/b06ef36...

Other commenters have noted that you can do a slightly fancier version of this lookup table technique to solve for the sliding pieces (bishops and rooks (queens are a bitwise OR of bishops and rooks)), because the raw data is low entropy, so finding a perfect hash function ("magic bitboard", in the lingo) is fast enough to do on startup:

https://github.com/official-stockfish/Stockfish/blob/b06ef36...

It's existing techniques like this that make bitboards a good choice for beginners; if you get stuck, you can find resources online.

> - Optimization of engine code is much harder than optimization of the yield function.

Big +1 there! The yield function is also much easier to A/B test.

> - It is much better to not generate 'bad' moves than it is to prune them away after a lot of extra work has been done. Colin Wrights' law: 'You can't make computers faster, you can only make them do less work' clearly applies here.

Yes, but it's pretty hard to reliably get your move generator to generate good moves first. The other side of making mixmax search fast is quickly throwing out branches that aren't relevant.

For instance, delta pruning and null-move pruning do this by trying to detect if one of the sides has thrown the game with their last move; since minmax is about assuming optimal play on both sides, branches where someone makes a blunder aren't worth looking into.

> - memoization can bring insane speed gains.

Yup! Also, a lot of engines have optimized routines that let you undo a move quickly, without having to keep a redundant stack of every position's state, which would involve a lot of memcpy-ing.

Have fun! I had to stop doing chess engines, they were becoming too much of a distraction for me. I'm kind of glad ML-AI is starting to beat human-crafted AI in chess, that way the space can go back to being a fun little hacker cottage industry.

Edit: Oh! When making a chess engine, start by implementing "perft":

https://www.chessprogramming.org/Perft

That way you can compare how many legal moves your engine thinks there is in a position, versus how many Stockfish or some other known-good engine thinks there is. It's the closest thing there is to unit tests in the space.

Instructions unclear; I just built a table-base instead of an engine with your advice! At least it solves any endgame with few enough pieces...