Óscar Toledo G. has notably written various tiny, strong and highly obfuscated chess engines in C (winning the IOCCC twice) and JavaScript (2nd place in the first JS1k). He's even written a 170 page book to serve as a reference to the 1326-byte "Nanochess" program, his strongest small chess engine.
Reading through Micro-Max takes a while, but the ideas in there are great! Like Sunfish it also doesn't do underpromotion: "which I considered a dull input problem".
I was looking at Oscar Toledo's family website (http://www.biyubi.com/eng_principal.html) and it's rather interesting, apparently they assemble their own PC's have their own OS and Browser. Has anyone here tried any of these out?
Pretty neat stuff. Looks like the move generator is missing a few features like underpromotion but it is very concise. I wrote a rudimentary engine + move generator[1] using bitboards[2] a couple of years ago. Unfortunately python poorly suited for bitmath optimizations because it doesn't support fixed width integers. Once I saw how slow my movegen went compared to a c version, I gave up on finishing up the minimax search to complete the engine. It does run quite a bit faster in pypy but still no easy way to force 64 bit integers.
You can either use numpy ints in pypy (I think they're nicely optimized) or there is __pypy__.intop module that does something. Come to #pypy on freenode we'll sort you out ;-)
The problem with Cython, in this case, is that in order to get close to C/C++ speed, you end up having to write code that looks an awful lot like C/C++. All of the Python black magic that let's you write this in 111 lines goes away.
Yes, that is 388 lines, however, the title makes reference to the chess engine itself. The rest of the code, such as setting up the board, handling moves, and ui, are not specific to the sunfish implementation, they can be used without the engine.
It would be much easier to read if the 111 lines where separated into their own file, though. Otherwise it's hard to discuss what is really important for the engine and what isn't.
Sidenote: independent from the discussions about the lines I consider it an awesome piece of work. Even in 388 lines it's still much better than what I could deliver.
I haven't played it yet, but I am curious, the variable pst seems to give the score of a piece given the square it is, independently of the position? How it that possible, am I missing something? (You only use pst to calculate the score of a move, if there is no check, checkmates or capture).
Having said that, the code is very neat and readable. Thank you for showing it here!
Correct, that's what it is doing. It is a very fast and surprisingly strong way of evaluating the position. Of course stronger engines do a hell of a lot more than this and gives weightings based on the positions of other pieces, but most of them have something like this as a baseline.
Exactly! Indeed some engines (the Micro-Max engine) just tries to move all pieces towards the center, and it still works pretty well! (http://home.hccnet.nl/h.g.muller/pcsqr.html) I wanted to add the table though, as I thought it made the games more interesting, and gave a nice handle on tweaking the engine.
PST stand for piece-square-table. You keep the static evaluation simple and fast, and let the search hash out the dynamic details. The search is surprising effective at its job, and trying to evaluate a position statically is surprisingly difficult.
Unfortunately this program doesn't play legal chess. When I played the program it did not move its king out of attack when checked. And yes, I've played enough chess to know an illegal move when I see one.
As an experienced chess player, there are some situations in which people who know the rules still might get tripped up on. For example, consider the situation:
K R r
_ _ _
k _ _
Can `k` move to the right? Someone who isn't familiar with this situation might think so, because `R` is pinned to `K` by `r`, but it turns out that even though `R` can't move to the square right of `k`, `R` can still give check to it, so the move would be illegal.
Then you also get people who don't know about rules regarding castling through check, etc.
Basically what I'm getting at is, there are moves that even people who casually play chess might misunderstand, so OP was implying that they were not one of these people.
I learned the rules of chess from a children's book in third grade, but have never played a full game as far as I can remember. Yet this situation seems extremely obvious to me. One of the most fundamental rules from my children's book was that you cannot make a move that puts yourself in check. Moving k to the right would clearly do that. And it's pretty obvious when you think through what would happen if k moved to the right. R would capture k, which would not put R in check, because the game would be over.
It only trips people up because the R can't actually move to that square. So if the k were say, a queen, the queen would be safe on that square. The opposing rook would not be allowed to capture it, because they would be putting their own king in check.
If one thinks about chess as if the goal were to capture the opponent's king before one's own king is captured, this makes perfect sense. But sometimes the concept of checkmate muddles peoples' intuitions.
It would only trip people up if they memorize the rule: "You can't make a move that exposes your king to check" but then, for some strange reason, forget that it applies to the other guy too.
I use that example specifically because it came up on /r/chess the other day, and I've had newer players ask me once or twice. I agree that an experienced player should know, but casual players may not.
>It's not like Chess is some weird, esoteric game where there is a gray area of whether or not moves are legal or not.
Actually it is exactly like that.
If you play tournament chess, like USCF tournaments, then there's no doubt what the rules are. However if you play casual chess, like with some random guy in the park, then be prepared for some misunderstandings.
Some things casual players think are rules:
Pawns move two squares only on the first move of the *game* not the first move of the pawn
You can't promote a pawn the move after it arrives on the 7th rank, you have to wait a move
Perpetual check is illegal (somewhat like the Ko rule in go)
Capturing En Passant is generally not known
So when I'm playing a stranger I always ask if they've played any tournaments, not to gauge how strong they are, but to see if they'll know the rules of chess.
I don't know if I would consider people being blatantly ignorant of the rules evidence that the rules are a "grey area." I learned how pieces move and capture from a children's book in third grade, and I distinctly remember it covering those rules, except for the third, which I have never heard of.
As far as I know, these rules are extremely standardized in most or all areas of the world where chess is known. I have heard about some special rules for competitions that can differ, like timing limitations and end-game rules. I'm also aware of many variations of chess, but those are always clearly discussed as variants.
I haven't played in any chess tournaments, but I started doing this myself after my cousin captured my bishop with an en passant. The game was ruined by the ensuing argument...
Yeah, my cousin thought if his pawn was on the 5th row he could capture any piece next to it by performing an "en passant". Of course, it wasn't a proper en passant, but the way he moved his pawn was the same, it's just he was capturing a bishop instead of another pawn.
> Pawns move two squares only on the first move of the game not the first move of the pawn
Can you elaborate on this? I've never seen any claim to this effect, only that a pawn on its starting rank has the option of moving two squares (but cannot use that to jump over or capture a piece) (e.g. as stated http://en.wikipedia.org/wiki/Pawn_(chess)). Are these different claims or am I misunderstanding?
> You can't promote a pawn the move after it arrives on the 7th rank, you have to wait a move
Yeah, but it isn't a grey area, the rules are well defined and actually pretty easy to understand. I've had people not know the rules before, but they wouldn't call themselves experienced.
En passant is a bit funny in that, once you learn it, it's tempting to use it when it would actually be better not to.
When I played tournaments in high school, most players knew about it, but most players were still quite amateur, so one could offer up a position in which the opponent could perform an en passant, but the en passant was actually fairly detrimental, and more often than not the opponent will take it, because "hey cool I can do that weird pawn move".
Author here. I'm sorry things are not working out. I'd be very interested if you could open a report with the position involved. Sunfish move generation is tested pretty thoroughly, generating tens of millions of positions and comparing with other engines. But of course it's still young and glitches may happen :)
No. While in check, the only legal moves are those that take you out of check. It is checkmate (and you lose) if and only if there is no legal move that would take you out of check.
Also, a move that would place yourself in check is never legal.
Pretty cool. I once wrote a C++ program to play me in chess. It was ~5000 lines of code! I can appreciation this script.
I think a more interesting problem now is to create computer algorithms that can be "taught" the rules of a board game --- a problem that falls squarely in the domain of supervised learning. In the studies I've found, the algorithms were provided with a lot of prior knowledge about the specific board game, so there may be a lot of room for progress.
GGP is then about deriving knowledge about the game and its state evaluation using a) the rules directly, b) the represented state tree or c) past matches in that very game.
The other one I know of is a mechanism where you use reinforcement learning and assume one state in the beginning.
With more info, you start splitting the state into several states using decision tree split criteria, such as cross entropy, and you end up obtaining a game state tree together with the knowledge to play reasonably well. Problem: I don't remember how it's called.
You might be interested in 'General Game Playing'. The idea is that players are presented with a machine-readable description of game rules (in a prolog-like locigal language), and they then play the game.
Since you can't use human-tuned heuristics for every game, you have to use more general meta-heuristics. There's also a lot of room for logically parsing the game, and trying to separate out individual components, obviously meaningless moves, etc.
it basically defines an initial game state, the moves each player can make and how they alter the game state, and the end-conditions and goals of the game.
I found it quite weak in the opening, well, just about as bad as any chess engine without an opening book to go on. 1. e2e4 g8f6 2. e4e5 f6d5 3. c2c4 d5f4 (weird), 4. d2d4 f4d6. This is probably some opening like the Snake, or the Vulture or something. but beat it quite solidly opening up the f-file and hitting f7 with the queen and rook.
Second game I decided to avoid opening theory and head into a King's Indian Attack. Black's opening moves were sensible, knight and bishops to the right squares, pawns on e5 and d5, but it really wasn't taking my queenside pawn expansion seriously enough, giving up a knight for a pawn. But it's quite resourceful, it's managed to win an exchange, although it's in a desperate position. Currently it's hanging on this position.. oh. No, it's finally crashed. This is the position it died on:
r . . . r . . .
. . . . . . k p
. b q . . . p .
. R p . p . . .
P . Q p P . . .
B N . P . . P B
. . . . . P . P
. . . . . . K .
White's last move: f5h3. Took about 10 minutes and made the move h8g7, and then crashed with
Your move: Traceback (most recent call last):
File "sunfish.py", line 388, in <module>
main()
File "sunfish.py", line 365, in main
move = parse(crdn[0:2]), parse(crdn[2:4])
File "sunfish.py", line 345, in parse
fil, rank = ord(c[0]) - ord('a'), int(c[1]) -1
ValueError: invalid literal for int() with base 10: ''
So, not strong, but surprisingly strong for the size of the code. Remarkable.
Yes, endgame knowledge is hard to encode succinctly. Clearly having separate piece tables for start- and end game would help a lot, piece tables too, but apart from that I'd be interested in ideas :)
I don't care that much for chess engines, but the code looks really pythonic. I learned a lot from reading it! I already started to believe that real pythonic projects don't exist.
Traceback (most recent call last):
File "sunfish.py", line 388, in <module>
main()
File "sunfish.py", line 365, in main
move = parse(crdn[0:2]), parse(crdn[2:4])
File "sunfish.py", line 345, in parse
fil, rank = ord(c[0]) - ord('a'), int(c[1]) - 1
IndexError: string index out of range
As a fellow chess coder I find this very cool, but we should be careful with the use of the word "strong." What ELO (for the non-chess people, rating) does this play at? I very much doubt it's truly what most would consider "strong" nowadays. In fact I doubt it plays above even 1500 - that's not strong. Great example of a simple chess engine in Python though? Surely!
You are right of course :) Sunfish is nowhere the level of 'real' engines. It is only strong compared to fellow Python engines, which I get from Ruxy Sylwyka who 'promoted' it to play in the 'Java league' http://www.talkchess.com/forum/viewtopic.php?topic_view=thre... ;) Still it's probably less than 1100 ELO. Maybe 1200 with pypy.
I had a ZX-81 and it was not poorly documented. Also, the Z80 assembly language was quite advanced compared to others from the same era (fe 6502). It had 16 some bit registers and 2 register sets (with at that time plenty of registers) that could be swapped.
The machine had a Basic interpreter that used bytecodes (to save memory), so programmers regularly mixed adopted a mixed style : basic + asm .
Anyway, to write a chess program for that machine is however rather impressive.
I wrote a chess game on a PIC16c-something. It had 176 bytes of RAM and only a 8 level return stack. I implemented recursive minimax by managing my own data stack since the compiler claimed to not support recursion. Code size was IIRC around 2K. You could play it on a battery charge controller we were making via UART in a terminal program, it printed the board and accepted key strokes. It declared checkmate when it was a certainty but before it actually happened...
I've noticed the odd trend of people bragging about how few lines it took to do X. Seems like people are trying to equate less loc == better code, which is not usually the case (better/more robust error handing and correcting, more complicated AI logic, etc).
It just means you are using a more abstracted version of whatever.
In reality, a 111 lines of Python program is likely thousands of lines if you were to count all of the standard Python libraries and/or any 3rd party libraries used.
What if I took this program, wrapped it in say, 5 lines of Python, then said I implemented chess in 5 lines of Python? Did I really? Of course not... but it makes for a good attention grabber.
> Seems like people are trying to equate less loc == better code
No. It's a tradition that goes back a long way. When it started it was about making code better - more efficient; faster; smaller. Part of that was the limited hardware available.
Now, when huge computing power is available to almost anyone, it's about the fun of finding that shortcut or that weird trick to remove a few lines of code.
The best code is the code you don't have to write. I like these short cuts and I played and lost a game against this beauty after reading the code. He did not use any chess-specific libs. Just pure and simple python.
I am proud to not contribute much to LOC counts on most of the teams I worked as I clean up a lot after my colleagues to keep code duplications low and pointless code out. Less code is normally easier to maintain as long as you follow some other coding practices and don't go and inline everything.
You are of course right that less is not better. Indeed Sunfish often takes a more lengthy approach than say Micro-Max, because Sunfish is also meant to teach chess programming. Examples include:
- Using an actual text representation of the board, rather than a binary.
- Having separate functions for move generation, search and evaluation.
- Using a python hashmap rather than a simple zobrist hash.
- Using a direct piece square table rather than some compressed/generated nonsense.
I do however also think, that trying to shorten the move generation of some programs, which can be hundreds or thousands of lines, to something like this, is a good exercise in finding patterns, and has a certain beauty ;)
"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger." -- Dijkstra (https://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/E...)
Clearly there's a line beyond which the code is no longer readable, but that is not to say that more lines is better, or that there is no elegance in implementing things more concisely.
I wasn't attempting to criticize this code - but merely comment on the trend I was noticing... however as DanBC pointed out, this is really more of a Code Golf exercise, which now makes more sense!
http://www.nanochess.org/chess.html