Toyfish: chess engine in Python for absolute beginners

[maksimKorzh]

Hey what's up guys, Code Monkey King's here.
I'd like to announce the beginning of a new tutorial series on my chess programming YouTube channel.
It's dedicated to absolute beginners who want to write their very first chess engine from scratch quickly and with fun)
I've considered Python programming language as a weapon of choice and came up with exactly 100 lines of source code!
The engine turned out to be extremely simple so I decided to call "Toyfish" as something completely opposed to Stockfish)

SOURCE CODE:
https://github.com/maksimKorzh/toyfish

YOUTUBE SERIES (Just starting...):


See you on the other side)
Cheers!

[KLc]

Nice, I like Python engines. Can't you make this quickly into a UCI engine using the https://github.com/niklasf/python-chess module? Then one could actually play against it. Also, maybe you can try to remove all of the limitations even if you get some more lines of code because these are quite severe.

[hgm]

Nice! So you use pure minimax and no QS.

This won't be very strong. But I am sure you already know that. And it doesn't matter much; it seems that for playing against human non-club-players 1 ply + QS is already too strong. And at that depth the advantage of alpha-beta over minimax is not yet overwhelming.

One suggestion: use a recapture extension. Don't always call search recursively with depth-1, but only decrement the depth if the to-square is unequal to the to-square of the previous ply. That should lead to far less idiotic play, especially at the very low depths you will be able to reach with minimax.

[Edit] I guess you would have to not immediately return the evaluation when depth<=0, but always do the loop over moves, but decide on a per-move basis whether you want to actually search it (for recaptures or when depth > 0), or score it as the current evaluation (remembered in a variable).

[maksimKorzh]

Nice, I like Python engines. Can't you make this quickly into a UCI engine using the https://github.com/niklasf/python-chess module? Then one could actually play against it. Also, maybe you can try to remove all of the limitations even if you get some more lines of code because these are quite severe.

Of course I can but it makes no sense because it's a toy engine (hence the name).
Btw as far as I'm aware python-chess allows to interact with existing UCI engines
only, does it have a built in UCI implementation? I didn't see it in the docs...

This engine is intended for absolute beginners as a very first chess programming experience
just to get familiar with the stuff. I have many more "normal" engines:
https://www.chessprogramming.org/Maksim_Korzh

[maksimKorzh]

Nice! So you use pure minimax and no QS.

This won't be very strong. But I am sure you already know that. And it doesn't matter much; it seems that for playing against human non-club-players 1 ply + QS is already too strong. And at that depth the advantage of alpha-beta over minimax is not yet overwhelming.

One suggestion: use a recapture extension. Don't always call search recursively with depth-1, but only decrement the depth if the to-square is unequal to the to-square of the previous ply. That should lead to far less idiotic play, especially at the very low depths you will be able to reach with minimax.

[Edit] I guess you would have to not immediately return the evaluation when depth<=0, but always do the loop over moves, but decide on a per-move basis whether you want to actually search it (for recaptures or when depth > 0), or score it as the current evaluation (remembered in a variable).

This won't be very strong. But I am sure you already know that.

haha) sounds really ironic))))

re: recaptures
- it's really good idea, but it might no longer be exactly 100 lines of code)
it's critical because the tutorial promo on youtube mentions that
"we'll write exactly 100 lines of python code")))
But even if it would fit still it's already a complication and for this
program I want to keep things as simple as possible for you know like
when the newcomers on youtube are starting with my 95 video series on
bitboard chess engine in C it gets a bit overwhelming))) There were requests
like "where should I get started?" - so this engine is the answer)
I already made 2 tutorials, I guess it would take 4 more videos to complete
the series.
Earlier I used my BMCP (ugly little brother of micro-Max) for these purposes
but it's not very didactic to have everything bundled into a single function
so I decided to make this split version.

I also have some plans on implementing toy variants like shatranj, makruk, xiangqi, jangi and other.

[maksimKorzh]

Here's the main tutorial within the series - coding move generator:

[maksimKorzh]

Nice! So you use pure minimax and no QS.

This won't be very strong. But I am sure you already know that. And it doesn't matter much; it seems that for playing against human non-club-players 1 ply + QS is already too strong. And at that depth the advantage of alpha-beta over minimax is not yet overwhelming.

One suggestion: use a recapture extension. Don't always call search recursively with depth-1, but only decrement the depth if the to-square is unequal to the to-square of the previous ply. That should lead to far less idiotic play, especially at the very low depths you will be able to reach with minimax.

[Edit] I guess you would have to not immediately return the evaluation when depth<=0, but always do the loop over moves, but decide on a per-move basis whether you want to actually search it (for recaptures or when depth > 0), or score it as the current evaluation (remembered in a variable).

Mr. Muller I was wondering about the following experiment: one line engine
I know it's weird and the first thing to consider is to drop recursive calls...
So is it possible to:
- do 3 nested loops
- make move
- statically evaluate the position
- take back

and here's my question - we should leave the best move on board untouched as far is there's no function to return best score right?
Is that possible? Could you please give me a clue on how to achieve that if so?

[hgm]

Sorry, I don't understand what you are asking here at all. But perhaps that is because I don't know Python. In C newlines are just optional white space, so it is always possible to write a program as a single line.

About the recapture, again it might depend on the program layout that Python requires. Passing an extra argument last_target to search() doesn't require any extra lines. So the issue is the extra if statement in the move loop. I don't know if this is valid Python, but I was thinking about something like

Code: Select all

if depth <= 0 and move['target'] != last_target: score = current_eval
else:
  self.make_move(move)
  score = -self.search(depth-1, move['target'])
  self.take_back(move)

That would be two extra lines (assuming the line "if depth == 0: return self.evaluate();" will be replaced by "current_eval = self.evaluate()"). But perhaps you can save those elsewhere. E.g. why do you keep track of best_source and best_target separately, rather than just having a single best_move?

[Edit] It also doesn't seem necessary to initialize best_move / best_source / best_target (and initializing to an invalid value would not help in any case).

[maksimKorzh]

Thanks!
The idea was to avoid having a function call but never mind)

[hgm]

It is certainly possible to implement recursion 'by hand'. I.e. making an iterative search, rather than a recursive one. In languages that do not support recursion (such as Fortran) you had to do that anyway. The trick is just to keep everything that would be a local variable as an array element indexed by the ply level. To mimic the recursive call you just increment 'ply', and jump back to the beginning of the code that normally is in Search(). To mimic a return you decrement 'ply', and jump to just behind where a normal return should go (i.e. just behind the mimicked call). Except when ply == 0 (the root), where you just continue with the main loop (which would print and execute the move).