Minimalism in chess programming

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
maksimKorzh
Posts: 771
Joined: Sat Sep 08, 2018 5:37 pm
Location: Ukraine
Full name: Maksim Korzh

Minimalism in chess programming

Post by maksimKorzh »

I'm close to complete my minimalist engine. After implementing alpha beta prunning and the most basic move ordering stuff I've finally reached the point of satisfaction. My original aim was to masrter 0x88 board representation( previously I tried mail box 120 and plain magic bitboards believe it or not, but those stopped at perft testing) as well as alpha beta search to get the bare minimum featured engine at the end. The second aim was to beat Oscar Toledo's tiny chess which I couldn't do with pure negamax for toledo is pretty strong in it's class so I solved this issue via using alpha beta and move ordering which I believe is a bit unfair.

My questions are as follows - in minimalist chess - where to stop and how to proceed?
zullil
Posts: 6442
Joined: Tue Jan 09, 2007 12:31 am
Location: PA USA
Full name: Louis Zulli

Re: Minimalism in chess programming

Post by zullil »

maksimKorzh wrote: Sun Sep 16, 2018 11:46 am I'm close to complete my minimalist engine. After implementing alpha beta prunning and the most basic move ordering stuff I've finally reached the point of satisfaction. My original aim was to masrter 0x88 board representation( previously I tried mail box 120 and plain magic bitboards believe it or not, but those stopped at perft testing) as well as alpha beta search to get the bare minimum featured engine at the end. The second aim was to beat Oscar Toledo's tiny chess which I couldn't do with pure negamax for toledo is pretty strong in it's class so I solved this issue via using alpha beta and move ordering which I believe is a bit unfair.

My questions are as follows - in minimalist chess - where to stop and how to proceed?
Your evaluation is what? Material only? Material + position (piece square tables)?

Move ordering done how?

Hash table next, perhaps?
User avatar
maksimKorzh
Posts: 771
Joined: Sat Sep 08, 2018 5:37 pm
Location: Ukraine
Full name: Maksim Korzh

Re: Minimalism in chess programming

Post by maksimKorzh »

zullil wrote: Sun Sep 16, 2018 1:34 pm
maksimKorzh wrote: Sun Sep 16, 2018 11:46 am I'm close to complete my minimalist engine. After implementing alpha beta prunning and the most basic move ordering stuff I've finally reached the point of satisfaction. My original aim was to masrter 0x88 board representation( previously I tried mail box 120 and plain magic bitboards believe it or not, but those stopped at perft testing) as well as alpha beta search to get the bare minimum featured engine at the end. The second aim was to beat Oscar Toledo's tiny chess which I couldn't do with pure negamax for toledo is pretty strong in it's class so I solved this issue via using alpha beta and move ordering which I believe is a bit unfair.

My questions are as follows - in minimalist chess - where to stop and how to proceed?
Your evaluation is what? Material only? Material + position (piece square tables)?

Move ordering done how?

Hash table next, perhaps?
Evaluation: material + piece square tables
Move ordering: follow PV, MVV_LVA, search history, killers

I'm really wondering about what guides people to create such an awesome stuff like micro-Max chess where every function but alpha-beta search are inlined? I find such cute little programs to be a true and pure expression of minimalism and would like to make my own engine much smaller in code, but the problem is that tiny programs are much more complicated from the algorithmic perspective. So I need some guidance of where to start in transforming my 1500+ lines engine into size like micro-Max or Toledo chess. And let's assume this has been done, so for such tiny sized program - where to stop and how to proceed. And does anybody know whether micro-Max development has been abandoned or not?

-----------------------------------------------------------------------------------
Maksim Korzh
Chenglite

https://github.com/maksimKorzh/Chenglite
User avatar
maksimKorzh
Posts: 771
Joined: Sat Sep 08, 2018 5:37 pm
Location: Ukraine
Full name: Maksim Korzh

Re: Minimalism in chess programming

Post by maksimKorzh »

I'm trying to find my path in chess engine development. My first aim was to write a bug free move generator which took me 3 years... I didn't even know how to code at that time. Now I have a program that plays chess, but it's size is much bigger than it's strength :D , so as far as I'm pretty satisfied with the strength and speed for now the only question arising is to make the code as small as possible. I don't mean to use macros to short the loop keywords or one letter variables, I mean to get the same result but in less code with probably changing the design or even rewriting the program from scratch. I have a strange desire to keep rewriting my engine from scratch again and again until it would be a size close to micro-Max or Toledo chess. Could you please kindly share your thoughts at this point for the community opinion is very important for me.
elcabesa
Posts: 855
Joined: Sun May 23, 2010 1:32 pm

Re: Minimalism in chess programming

Post by elcabesa »

my thoughts:
1) I really admire the work and ability of HGM in creating micromax
2) to do such a great work one need to be a greath programmer and know very well how to write a chess engine.
3) I don't like such minimalism :)

I think that to write a full functional so small and obfuscated code you need to be a really good programmer.

don't hate me, but at the moment you don't seems to master chess programming to such level.

my suggestion is to write a not so much minimalist engine ( like tscp ) understanding very well all the subltes of negamax, pvs and so on bugfree.

then you'll be able to create a minimalist engine without wasting energy and time.

it will be very difficult to write/debug a minimalistic if you aren't very good at minmax, move generation , pv extraction and so on.

but in the end it's your time and your entertainment and you can do whatherev you want :)
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Minimalism in chess programming

Post by Sven »

elcabesa wrote: Mon Sep 17, 2018 10:47 pm my thoughts:
1) I really admire the work and ability of HGM in creating micromax
2) to do such a great work one need to be a greath programmer and know very well how to write a chess engine.
3) I don't like such minimalism :)

I think that to write a full functional so small and obfuscated code you need to be a really good programmer.

don't hate me, but at the moment you don't seems to master chess programming to such level.

my suggestion is to write a not so much minimalist engine ( like tscp ) understanding very well all the subltes of negamax, pvs and so on bugfree.

then you'll be able to create a minimalist engine without wasting energy and time.

it will be very difficult to write/debug a minimalistic if you aren't very good at minmax, move generation , pv extraction and so on.

but in the end it's your time and your entertainment and you can do whatherev you want :)
I fully agree to all of these points.

And if I had the choice between
a) reducing the code size while keeping the same strength, and
b) keeping or increasing the code size while increasing the strength,
I would always choose b) :-)
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)
PK
Posts: 893
Joined: Mon Jan 15, 2007 11:23 am
Location: Warsza

Re: Minimalism in chess programming

Post by PK »

A good intermediate goal would be to code an engine whose elo is greater than its number of lines (not chars, like in these little marvels). You can go pretty far with that. I have a 2400 line program that plays at 2700 Elo, CCRL scale.
User avatar
maksimKorzh
Posts: 771
Joined: Sat Sep 08, 2018 5:37 pm
Location: Ukraine
Full name: Maksim Korzh

Re: Minimalism in chess programming

Post by maksimKorzh »

Thank you guys for sharing your thoughts, but I'm still wondering about H.G.Muller's opinion at this point and the other question - is there somebody but H.G.Muller or Oscar Toledo to get close to 2kb sized engine? I mean why people don't try to write minimalistic program's? Why most choose to increase the strength rather than keep it and reduce the code size?
User avatar
Fabio Gobbato
Posts: 217
Joined: Fri Apr 11, 2014 10:45 am
Full name: Fabio Gobbato

Re: Minimalism in chess programming

Post by Fabio Gobbato »

I have written a didactic engine that have less than 1200 line of code but is quite weak. You can find it here https://drive.google.com/open?id=1ec9kM ... dGEmLdLgP9
User avatar
hgm
Posts: 27772
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Minimalism in chess programming

Post by hgm »

My interest in small code size stems from my Chess programming in the late seventies, when I had only 2KB of RAM available for program + data. And I was wondering wheter one could reach a similar density for the information on the essence of Chess in source code. I used character count as a metric rather than line count, because the latter is rather arbitrary: you can always write a C program as a single line. So you would need additional rules for what is considered a line. The disadvantage of using character count is that it drives you to one-letter variables, reducing the readability of the code for no good reason. Perhaps it would be best to use the number of 'lexical units' from the C-syntax as a metric. Then identifiers (or keywords) would just count as 1 unit, no matter how long they are.

Reducing code size is not always at odds with program speed, and hence strength. Nothing can be faster than the things you don't do at all. Even code with many alternative paths, each short, can hurt the speed. Because the paths occupy cache space or memory bandwidth to reload them in cache, and to select the path requires (often poorly predictable) branches. So part of the trick is to combine as many similar tasks as possible into one stretch of code, and let the differences be determined by data, rather than code.

E.g. for move generation one often sees a design where one first figures out what piece one is dealing with, and then use separate pieces of code to generate the moves for each piece. While on a deeper level of abstraction almost all Chess pieces (even unorthodox ones) are doing the same thing: they step in a number of directions until they hit a piece or board edge, or until their range expires. The only difference is in the list of allowed step vectors and the corresponding ranges. But those lists can be put in a data as a table, fed to a 'universal' move-generation code: an outer loop over directions (which steps through the applicable list of step vectors), and then an inner loop that repeats the step until an obstacle is reached, or the range counter (from another list) expires. In orthodox Chess there is no need to keep separate ranges per direction, as all moves of a given piece have the same range, which can only be 1 or infinite. So you can list it per piece type rather than per (piece-specific) direction. Or not even get it from a table but deduce it directly from the piece-type encoding. And to choose between a range of 1 or infinite, there is no need to actually count the number of steps you have already done, but you can just break out of the loop after the first iteration if the piece is a leaper.

That takes care of everything but the special rules for Pawn movement and castling. The Pawn double-push and castling are again two of a kind, in that they are possible only with virgin pieces, be it Pawn or King, and that they both suffer a form of e.p. capture (which in the case of the King translates to that you are not allowed to castle through check). So the code required to check whether these are possible can be combined for a large part as well.

For the search there isn't much difference between what QS and the full-width search does. In QS you can stand pat, but that can be treated as an extra move only allowed at d=0. (And then of course you prune all non-captures there.) And when you use Internal Iterative Deepening, there also isn't much difference between what the full-width search does compared to what you do in the root. So those can be combined as well, slipping in some conditional code executed only in the root. (Such as printing the PV whenever you get a better one.)