Engine development and blog.

[likeawizard]

IsAttacked can be used both for testing whether a move left its own King in check, as well as for testing whether the move delivers check to the opponent. Both tasks can often be performed faster in a dedicated way. E.g. you can only expose your own King to capture in 3 ways: moving the King to a square that was under attack, moving a piece that was pinned to the King, or failing to resolve an existing check. The 3rd case can only happen when you are in check, and you probably will already know that, and also which piece does check you, and from where. You won't have to bother with it when not in check. Testing whether a piece is pinned usually ends after the simple test for whether it was aligned with the King in the first place. Only when the King itself moves you are much in the dark for what it can be exposed to, and you would need a more general IsAttacked test. But fortunately Kings typically only have very few moves for most of the game, and usually these are no good, and thus will be searched quite late (e.g. after history sorting). So that you often don't get to try those at all.

For delivering check: this can either be done with the moved piece, or (when it was aligned with the enemy King) through a discovered check over the from-square. So you don't have to look in all directions for checks; just in the direction of the from- and the to-square.

I like those ideas. I think I had looked at some code of other engines and often would see methods that do similarly the same thing being duplicated but now I get it!

[brocksav]

My initial stance was - Do everything yourself. Do the code figure out the algorithms. Do not look or read anything chess related.

I think that is the best way to do it. I'm working on an engine myself (which is not yet anywhere near the point I would show it to anyone), just to help me learn C# and WPF, and took a similar approach. There is no better way to learn why most engines do X, than to first do it your own way and see how bad the results are. In my first attempt, I decided to save the board when a move was legal, and create new boards for moves from that point, rather than doing make/unmake moves. Why unmake a move when it was legal? I found out when my program ran hundreds of times slower than most engines, and ground to a halt with memory maxed out after just a few plies.

I look forward to reading your blog, once I feel there's no further point in seeing how poorly my own ideas work.

[lithander]

In my first attempt, I decided to save the board when a move was legal, and create new boards for moves from that point, rather than doing make/unmake moves. Why unmake a move when it was legal? I found out when my program ran hundreds of times slower than most engines, and ground to a halt with memory maxed out after just a few plies.

In a garbage collected language like C# that's not an unreasonable approach. Neither MinimalChess nor Leorik have an Unmake method. If you don't keep references to the old copies the garbage collector will reuse the instances and the amount of "real" board instances in MinimalChess increases by only one for each additional ply.
I was surprised by the efficiency of the .Net runtime and it inspired me to reuse the instances explicitly and my 2nd engine operates on a fixed array of 99 boards. You use the ply as an index into that array and making a move means you copy board[ply] into board[ply+1] and apply the move during that copy-step. This would also work in non-managed languages because it doesn't produce any garbage. And still there's no need to have an unmake. (And yet there's nothing wrong about implementing an unmake method of course)

[brocksav]

In my first attempt, I decided to save the board when a move was legal, and create new boards for moves from that point, rather than doing make/unmake moves.

In a garbage collected language like C# that's not an unreasonable approach. Neither MinimalChess nor Leorik have an Unmake method. If you don't keep references to the old copies the garbage collector will reuse the instances and the amount of "real" board instances in MinimalChess increases by only one for each additional ply.

That sounds like something I should try, but what I actually did was keep the entire tree. Nearly five million boards by the time it did five plies. Every board had a bunch of fields that included lists of all of its descendants and all previous moves, which of course had to be deep copied to pass to the next board created, so you can see why it was so slow and consumed so much memory. I took "don't optimize early" to a whole new level.

[likeawizard]

In my first attempt, I decided to save the board when a move was legal, and create new boards for moves from that point, rather than doing make/unmake moves. Why unmake a move when it was legal? I found out when my program ran hundreds of times slower than most engines, and ground to a halt with memory maxed out after just a few plies.

I look forward to reading your blog, once I feel there's no further point in seeing how poorly my own ideas work.

Yep I did something quite similar in my search routine. I was creating the search tree in memory with all the resulting positions as nodes. And when making a move I would reset the tree root with the best move. It actually had some nice features like extracting the moves and lines from it, move ordering was persistent between different searches. But it would just hog all the memory and after ~1min it would generate trees so big I ran out of all my 16GB of memory.

But the concept was very simple and it let me learn the basics of search which were beneficial when refactoring the search to a search without an actual tree.

[likeawizard]

Posting a small update on my work. Or lack of it. Took a small break from active development only writing a few lines now and then. Was enjoying the last warm days of summer and also working on some other unrelated programming hobby projects.

When I started working on my engine I was of course familiar with the concept of caching. However, I was used to caching monumental tasks like complicated SQL queries or the resources that need to be downloaded while browsing the web. Having looked at some chess engines I realized how common it was to use lookup tables for even the most simple things- like trivial computation of knight and king moves from a given source square. It of course made sense- even a simple task repeated millions of times per second can build compound to a lot of labor.

I really want to write about the use of magic bitboards and transposition tables. To the layman those are quite heavy topics and I feel a more accessible introduction is necessary. Also I need to focus on finally fixing and properly implementing transposition tables in my engine before I can write about it with any expertise.

So I wrote a small introduction on what caching is about in general and where and how it can be used with ease to increase performance in mundane functions in a chess engine as a lead up to the more advanced topic of Magic Bitboards and after that the use of transposition tables.

As usual it can be found on my lichess blog: https://lichess.org/@/likeawizard/blog/ ... s/uySQJskR

[likeawizard]

I have a very simple question about Zobrsit hashing.

Is it ever necessary to set/unset EmptySquareZobrist?

I have seen people offering pseudo code for moving a piece like:

Code: Select all

xor pieceSourceSq (unset piece at square)
xor emptySourceSq (set the square empty)
xor emptyDestSq (unset the empty dest square)
xor pieceDestSq (set piece at dest)

I believe the 2nd and 3rd lines are redundant (ofc in absence of captures)

To my understanding if you don't seed the hash with empty squares and only with occupied squares then there is no need to set/unset empty when updating the hash? This is in essence what the algorithm says on chessprogramming wiki on Zobrist hashing.
On wikipedia https://en.wikipedia.org/wiki/Zobrist_h ... hash_value it states:

'pawn at this square' (XORing out the pawn at this square)
'rook at this square' (XORing in the rook at this square)
'rook at source square' (XORing out the rook at the source square)
'nothing at source square' (XORing in nothing at the source square).

The last line here makes no sense to me...

[dangi12012]

Can confirm it's nonsense. X xor X == 0 so no "hash empty square" needed.

[likeawizard]

Thank you. I didn't do it anyway as it made no logical sense but the conflicting info was bugging me with the thought that I might be missing something.

[likeawizard]

Currently my at the start of my eval function I have checks whether the game is decided: It tests if the king to move is in check and if the side to move has any moves. If check and no moves then it awards +/- Inf, if the king is not in check then I am declaring a stalemate. (It currently lacks insufficent material, threefold and 50-move draw checks, but that's another topic)

Once I removed the checks I saw my engine increase it's performance massively. Determining checks and responses is obviously expensive. So I began to think whether there is a smarter solution. So far the kings had 0 weight in the eval but I am thinking giving the king a very high score. The same score that would be used for alphabeta initial call as +/- inf. (of course keeping int under/overflows in mind)

And let the search algorithm deal with (stale)mates. If the legal move generator returns no moves then perform a isInCheck and determine the result on that? Does this sound reasonable? What are other engines using for mate detection?