11 ms·
Sunfish: A simple but strong chess engine in 111 lines of Python
- WizzleKake 12y agoIf you are interested in this sort of thing, the chess programming wiki is an excellent resource: http://chessprogramming.wikispaces.com/ http://chessprogramming.wikispaces.com/
- grondilu 12y agoTried it. Typed e4. Got this: 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
- WizzleKake 12y agoTry saying e2e4 instead.
- ff_ 12y agoYeah, that's the correct way.
- deleted 12y ago[deleted]
- davidghiz 12y agoThis is because of the way he coded. To move a pawn you have to append with a "P". (I think, I have not tried it yet to be sure)
- edavis 12y ago"class Position(namedtuple('Position', 'board score wc bc ep kp')):" Whoa. I've literally never seen this idiom before. But I immediately like it.
- mikepurvis 12y agoMmmhmm! Just be aware of some fun things to watch out for when it comes to the __init__ and __new__ functions: http://stackoverflow.com/questions/4071765/in-python-how-do-i-call-the-super-class-when-its-a-one-off-namedtuple http://stackoverflow.com/questions/4071765/in-python-how-do-...
- bouk 12y agoIt's kind of a weird idiom because you end up with a class 'Position' inheriting from another class named 'Position'
- veb 12y agoI have not seen half the stuff here -- black magic! Awesome work Thomas!
- Jemaclus 12y agoCorrect me if I'm wrong, but that looks like 388 lines of Python? Still, very cool. I spent awhile trying to write my own and failed miserably. :)
- JonnieCache 12y agoI'm guessing it comes to 111 if you remove the comments.
- nobodysfool 12y agoYes, 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.
- erikb 12y agoIt 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.
- davidghiz 12y agoThe comments and empty lines amount to around 200 lines, OP is not counting those I suppose.
- e12e 12y agoNo: wget 'https://raw.githubusercontent.com/thomasahle/sunfish/master/sunfish.py' egrep -v '^$|^ *#' sunfish.py > sustrip.py wc -l *py 388 sunfish.py 263 sustrip.py (or: equivalently:) egrep -c '^$|^ *#' sunfish.py 125 #Comments, empty lines egrep -c '^$|^ *#' sunfish.py -v 263 #Non-empty lines, non-comment lines I believe the actual chess engine might be 111 lines, though.
- 12y ago
- chengsun 12y agoÓ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. http://www.nanochess.org/chess.html http://www.nanochess.org/chess.html
- tromp 12y agoAmazingly, the Dutch program Micro-Max by Geert Muller http://home.hccnet.nl/h.g.muller/max-src2.html http://home.hccnet.nl/h.g.muller/max-src2.html is even shorter and stronger than Toledo's.
- discohead 12y agoAmazing indeed.
- e12e 12y agoThat's crazy. Does look more like APL than C though...
- thomasahle 12y agoReading 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".
- wldcordeiro 12y agoI was looking at Oscar Toledo's family website (http://www.biyubi.com/eng_principal.html 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?
- staticshock 12y agoTheir OS is virus proof! I'm on board.
- pbreit 12y agoPython is the nicest language to read, right?
- Bootvis 12y agoMy ego is saved by its weak endgame but it plays a pretty decent opening all on its own.
- Isofarro 12y agoI 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.
- thomasahle 12y agoYes, 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 :)
- vishvananda 12y agoPretty 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. [1] https://github.com/vishvananda/ivory https://github.com/vishvananda/ivory [2] https://chessprogramming.wikispaces.com/Bitboards https://chessprogramming.wikispaces.com/Bitboards
- ris 12y agoCython? Numba?
- halfcat 12y agoThe 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.
- fijal 12y agoYou 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 ;-)
- slm_HN 12y agoUnfortunately 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.
- ionforce 12y ago> And yes, I've played enough chess to know an illegal move when I see one. 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. Maybe I'm biased. I'm currently working on a toy chess engine myself.
- slm_HN 12y ago>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.
- Buttons840 12y agoI 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...
- SeanDav 12y agoYou can only capture a pawn En passant and only if the pawn moves 2 squares in 1 go.
- jostmey 12y agoPretty 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.
- dmichulke 12y agoThere are approaches. One is General Game Playing where the rules are given as a set of logic formulas that basically describe a state machine http://en.wikipedia.org/wiki/General_game_playing http://en.wikipedia.org/wiki/General_game_playing http://www.general-game-playing.de/literature.html http://www.general-game-playing.de/literature.html 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.
- Yen 12y agoYou 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. see http://en.wikipedia.org/wiki/General_game_playing http://en.wikipedia.org/wiki/General_game_playing or https://www.coursera.org/course/ggp https://www.coursera.org/course/ggp an example game: http://ggpserver.general-game-playing.de/ggpserver/public/view_game.jsp?name=tictactoe http://ggpserver.general-game-playing.de/ggpserver/public/vi... 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.
- erikb 12y agoI 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.
- knicholes 12y agoI thought I understood "pythonic." Aren't his variable names the exact opposite of what one would expect in pythonic code?
- gaius 12y agoI've a VIC-20 here running chess. 3.5k RAM. And people even got it to run on the ZX-81, with 1k. Now that's impressive.
- LeoPanthera 12y ago1K ZX81 chess: http://users.ox.ac.uk/~uzdm0006/scans/1kchess/ http://users.ox.ac.uk/~uzdm0006/scans/1kchess/
- Joeboy 12y agoThe greatest program ever written [1] [1] https://www.kuro5hin.org/story/2001/8/10/12620/2164 https://www.kuro5hin.org/story/2001/8/10/12620/2164
- toolslive 12y agoI 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.
- Cyph0n 12y agoSorry, but holy shit.
- phkahler 12y agoI 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...
- S4M 12y agoI 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!
- someotheridiot 12y agoCorrect, 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.
- halfcat 12y agoPST 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.
- thomasahle 12y agoExactly! 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 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.
- deleted 12y ago[deleted]
- Isofarro 12y agoYuck, just caught it out with: e2e4 g8f6 e4e5 f6d5 d2d4 b8c6 f2f4 e7e6 c2c4 d8h4? g2g3 f8b4 c1d2 -- 2 pieces en-prise at this point. h4h6 c4d5 e6d5 d2b4 c6b4 a2a3 b4c6 b1c3 c6e7 Just a piece down with very little compensation.
- thomasahle 12y agoAuch, I guess it tried to do too many things at once, given its limited search depth :)
- Alupis 12y agoI'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.
- DanBC 12y ago> 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.
- Alupis 12y agoAh, that does make sense. Like Code Golf. ;)
- Crisco 12y agoThat's exactly what it is. Code Golf is pretty fun to look at, check out the questions here: http://codegolf.stackexchange.com/ http://codegolf.stackexchange.com/ There's some cool techniques different people use to solve some seemingly major problems in just a few characters.
- chipsy 12y agoWhy not offer a specific criticism of how this program leverages Python, though?
- 12y ago
- mightybyte 12y agoHere's a simple but strong suicide chess engine in literally 162 lines of C. http://www0.us.ioccc.org/2001/dgbeards.c http://www0.us.ioccc.org/2001/dgbeards.c
- WoodenChair 12y agoAs 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!
- thomasahle 12y agoYou 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=threads&p=562610 http://www.talkchess.com/forum/viewtopic.php?topic_view=thre... ;) Still it's probably less than 1100 ELO. Maybe 1200 with pypy.
- chatman 12y agoMentioning "strong" without benchmarks seems subjective.