Engine development and blog.

[likeawizard]

My first post on the forum after several months of reading various topics linked from the Chess Programming Wiki.

Since around December or November last year I have been developing my own engine. This of course included long dry periods where nothing was being done.

I started coding chess to familiarize myself with the Go programming language as it become more relevant in my career as a Software developer. I remember just sitting in an empty room late winter evening and deciding to code some chess for the sake of coding itself. I had no ambitions of ever making it a fully playing engine initially but line after line and evening after evening my scope expanded.

My initial stance was - Do everything yourself. Do the code figure out the algorithms. Do not look or read anything chess related.
I did need some help from Wiki to deal understand the minmax algorithm and the occasional Stack Overflow thread with general programming issues.
After a few nights I had a program that slowly but surely played moves and not always illegal ones and heck sometimes even reasonable ones. I remember at that time the YouTube algorithm has sniffed what I was doing and I saw some suggestions about chess programming which I avoided to make sure I don't get influenced by other ideas and keep it all original.

About two months ago I wanted to share my creation with others and also I am a believer that to solidify your understanding it helps to explain new ideas to others assuming they have no knowledge of the topic. So I made a small extension to my chess program so it can play directly on lichess as a bot account and also posted a blog about my experience- the new ideas I learnt, the challenges I am facing, bugs encountered and share some games played by the bot.

My engine no longer only contains ideas that I can claim I came up with independently. I have read these forums and the CPW to learn new ideas and implement them in my engine.

Today I wanted to share both my code and my blog with the people who probably have contributed to it massively.
My github repository: https://github.com/likeawizard/chess-go
My bot running on lichess if you are interested playing it: https://lichess.org/@/likeawizard-bot
My blog: https://lichess.org/@/likeawizard/blog

My bot currently relies on an mailbox array[64] board representation with alpha-beta search with iterative deepening and some move ordering with PV, MVV-LVA. There are no book moves nor endgame tables. There are no move ordering or search heuristics. And there is a lot of work to be done. I have currently implemented bitboards but those still need to be optimized and fully tested for release.

In my writing I am trying to talk about various chess programming topics in a way that a layman could read and digest it with some effort. The CPW is great but a lot of the information there is very dense - aimed at people who are already somewhat literate about it. So I am trying to present it in a more accessible way. Probably in many cases too verbose but I do not want to make any of it wishy-washy and handwaving over details. If I put it into writing it should be correct, complete (maybe to a limited scope) and as simple as possible. It is a mix of general computer programming topics or topics concerning my own work exclusively.

I think some of the better entries might be:
Detail explanation of the alpha-beta search: https://lichess.org/@/likeawizard/blog/ ... s/RjCrdOHn
Review of different chessboard representations: https://lichess.org/@/likeawizard/blog/ ... s/S9eQCAWa

I hope you can get some enjoyment from reading. Although I believe the audience here could be too mature for the level of presentation.
Of course feedback on my code and/or writing would be welcome too.

[algerbrex]

Congratulations on the release! Always good to see more Golang engines. And I flipped through a couple of your blog posts too and enjoyed them.

I decided to challenge your engine to a game and actually got a winning position until I panicked because my time was running low and blundered twice. First pinning my queen to my rook, and then just straight up hanging my queen because I hallucinated having a check on f4

[pgn]
[Event "Casual Rapid game"]
[Site "https://lichess.org/liKy3ZfD"]
[Date "2022.08.11"]
[White "algebrex"]
[Black "likeawizard-bot"]
[Result "0-1"]
[UTCDate "2022.08.11"]
[UTCTime "20:06:15"]
[WhiteElo "1262"]
[BlackElo "1658"]
[BlackTitle "BOT"]
[Variant "Standard"]
[TimeControl "300+10"]
[ECO "D00"]
[Opening "Queen's Pawn Game: Accelerated London System"]
[Termination "Normal"]
[Annotator "lichess.org"]

1. d4 d5 2. Bf4 { D00 Queen's Pawn Game: Accelerated London System } c6 3. Nf3 g6 4. e3 Nf6 5. Nbd2 Nh5 6. Bg3 Nxg3 7. hxg3 Bg7 8. Bd3 h5 9. c3 a5 10. O-O Nd7 11. e4 a4 12. exd5 cxd5 13. Re1 Qc7 14. Rc1 Qc6 15. Qc2 b5 16. Ng5 e6 17. Bxg6 Ne5 18. dxe5 Ra7 19. Nxf7 Rxf7 20. Bxf7+ Kxf7 21. Nf3 Bb7 22. Nd4 Qc5 23. Qd2 Bh6 24. Qf4+ { White resigns. } 0-1
[/pgn]

It was a fun game, though, and it was nice playing an engine I actually had a chance of beating. I think a good set of piece square tables will definitely help with your engine strength a lot.

I'm probably going to give it another go and hopefully this time not hang my queen!

[likeawizard]

The opening is certainly the toughest part for it. I have seen it maneuver the opening beautifully and convert to a win but it can also still implode due to self-inflicted weaknesses in a fast and catastrophic manner. I would say its play is very weak and the wins come almost exclusively from exploiting a mistake and then never letting the foot of the gas after.

I am glad you had fun playing it feeling you have a chance but I am working hard to ruin that for you.

I am right now working on refactoring the whole thing to bitboards, however, my movegen and perft test currently can barely break even with my previous 1D array mailbox representation.

The two biggest challenges I have are:
Legal move generation. My first implementations usually have the move generator produce pseudo-legal moves and then prune all the ones that leave your king in check after moving. This seems very inefficient so I tried to base move legality on pins and checks.
I am using checks vectors to generate legal destination squares for my pieces - they either have to block it or capture the piece.
I am using pins to identify if a piece is pinned to the king. In that case the pinned piece's moves are limited to moving along the pinned direction including the capture of the pinner. I think my code there could be quite ugly and subject to a lot of optimization. And I straight up gave up on validating en passant moves in this manner due to many weird configurations this can result in. So in enpassant moves I still just run move-notIncheck-unmove routine for validation.

I am struggling with my move and unmove logic. In its most basic form the MakeMove function returns a closure that contains a copy of the board state to reinstate the previous state. In more advanced implementations the closure contained a smaller instruction set on how to undo those changes and only contained full information where information would be lost - like castling rights and en passant square. This had significant performance improvement despite the additional complexity. I still feel very uneasy about it and feel there could be much and maybe simple improvements there.

For reference I have a perft test that runs all the six positions in this wiki https://www.chessprogramming.org/Perft_Results to a given depth.
My 1D mailbox array can do that in ~2.5s at depth 4
My current magic bitboard implementation hovers around 3.2s at depth 4. There are certain optimizations I have in mind that could knock it down to near 1s but I was hoping to find more performance there.

[Ras]

Legal move generation.

I kept that because later on, you will have a beta cut-off on the first move in many cases, i.e. when the move sorting is there. There's no point investing time in figuring out the legality of moves that will never be tried anyway.

[likeawizard]

Are you suggesting not doing any move verification in the move generator itself? And only verifying them when playing them in certain contexts to potentially benefiting from not doing the validation upfront on moves that will never be played? I like that idea.

How and when do you verify them then? Does your MakeMove function throw an error on illegal moves being played and immediately take it back?

[Ras]

Are you suggesting not doing any move verification in the move generator itself? And only verifying them when playing them in certain contexts to potentially benefiting from not doing the validation upfront on moves that will never be played?

Yes, that's the reason why pseudo-legal move generators are common.

How and when do you verify them then? Does your MakeMove function throw an error on illegal moves being played and immediately take it back?

In my new version, I have added an "is move safe" checker before I even make the move. That's for figuring out whether the piece is pinned to the king. If in check, if it's a king move, or en passant, I instead perform the move and verify whether the king is in check afterwards. Takes a bit longer with my mailbox, but that's not for many moves.

Alternatively, you can also just not do any verification and return a higher-than-any-mate value if you can capture the king in the next depth level. That works well with MVV-LVA sorting because a king capture would be the first one being examined.

[hgm]

It depends on how efficient your test for being in check is. In some of my engines I just detect capture of a King during move generation (which is a very cheap test) and return an 'infinite' score immediately when such a move is found. This means that in the caller the move that exposed the King to capture gets infinite negative score, and will thus automatically be ignored.

The point is that most pseudo-legal moves will be legal, and a legality test performed on those would be wated time. That can hurt more than discovering that a move was illegal in a somewhat later stage (the work having done before that being wasted), because the latter only rarely happens.

An exception is when you are already in check before the move; in that case most moves will be illegal. The best way to handle that is to have a dedicated move generator for such positions, however, which selectively generates moves that evade the existing check.

[algerbrex]

Since I notice you’re writing your engine in Golang too, a little advice on optimizing morgen.

First, always prefer storing moves as 16/32-bit numbers. My performance tanked when I tried to use structs due to Go’s garbage collection needing to work on millions of move objects being created. Really object creation in general should be avoided when possible, as you probably already know, but this was a big one.

Second, for your isAttacked method or whatever it it’s called for you, try to use short circuiting logic. So instead of generating every possible piece move from the king square, start with checking the with the pieces whose moves are quick and easy to generate, kings, knight, and pawns. Then check the heavy piece moves.

Third, try to avoid branching logic where possible. Not really go specific but it was still often a very big performance hit that I wasn’t really considering at first. There are some clever ways to do things I found from browsing this forum to do things like update the castling rights.

Fourth, this was an idea I stumbled on from the Koivisto team, not sure if they got it from somewhere else. But basically from profiling I found it faster to treat the position hash as irreversible and store is and just restore it later. I got something like. 10-15% speed up from this if I remember. Of course this won’t apply until you added Zobrist hashing but still.

[hgm]

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.

[likeawizard]

Good stuff there!

As I mentioned before I am rewriting most of it at the moment to replace the mailbox array with bitboards.

I already am encoding moves as integers I simply use a type alias as in: type Move int, and have some associated utility methods associated with my type.
I think memory allocation should not differ in this case from using a type alias from using the native type. Correct?
https://github.com/likeawizard/chess-go ... ove.go#L42

This is the isAttacked method: https://github.com/likeawizard/chess-go ... on.go#L748
And it has some attempt to detect the "cheapest" attacks first.

Yes I noticed also the branching being a big issue. I noticed that I can gain impressive performance improvements by making my code more universal with less if-else branching. I was just revisiting older code that did exactly what it was supposed to do but written in somewhat contrived fashion due to bad understanding at the time. I did basic clean up and refactoring, really minor stuff nothing that would change anything in the O(n) complexity and I regularly noticed that cleaner code resulted in faster execution. So I think my older and uglier code might be a gold mine for performance.

For your fourth point. I actually "discovered" this by myself. I have zobrist hashes but I am not using them at the moment since my TT integration with my search behaved strange at points. But due to my laziness I first just saved the zobrist hash without trying to reverse it. It obviously worked. Then I tried to omit it and reverse it via the same XOR operations in unmake and it was buggy and slower and I gave up. I am glad to hear that my laziness was hidden genius.

I think most of those points I was already aware of but this certainly confirms my existing beliefs and also serves as a small ego stroke

I will certainly keep all those points in mind when refactoring. I have all my move gen converted to bitboards already. It works alright. And now I will rewrite my eval to bitboards and start cleaning up the new code and clean up the rest of my code.