6 ms·

133-line chess engine with annotated source

91 points by starpilot 16y ago

starpilot 16y ago
According to the developer, Micro-Max has an Elo rating of about 2,000 (http://code.msdn.microsoft.com/huochess http://code.msdn.microsoft.com/huochess). A 2,000 Elo rating corresponds to "expert" per the USCF, or about the top 1% of players (http://en.wikipedia.org/wiki/Chess_expert http://en.wikipedia.org/wiki/Chess_expert). I've played at least a hundred games against it and lost every one. :P
- hsmyers 16y ago
  Without attempting to read the obscured code, the reason for the middling high Elo lies in the algorithms implemented. One of the AI discoveries is the sad fact that chess does not need intelligence, just horse power and a good per move check list. The algorithms listed provide both...assuming a decent implementation--- I can't tell because I'm not about to translate the code :)
  - deleted 16y ago
    [deleted]
  - Xk 16y ago
    Would you tell me how to enter my moves so that I can play it? I've been trying to figure out the correct format but can't seem to get it.
    - starpilot 16y ago
      I played it in Windows via Winboard (http://www.open-aurec.com/wbforum/viewtopic.php?f=19&t=50387 http://www.open-aurec.com/wbforum/viewtopic.php?f=19&t=5...), which has Micro-Max set as the default engine.
    - yhager 16y ago
      just enter source and dest, e.g.: d2d4 to move the pawn at d2 to d4.
jhonnycano 16y ago
The article says the source code measures 1433 characters !
benjoffe 16y ago
The article states the goal to be under 2000 characters, to state it in terms of lines of code (as the submitter has) is kinda misleading when the following is considered to be one line: if(*c-10){K=c[0]-16*c[1]+C;L=c[2]-16*c[3]+C;}else /* parse entered move */ edit: can't see a way to escape asterisk characters, so this outputs slightly wrong (edit2: fixed)
- mathgladiator 16y ago
  very true. It would be way more impressive to be in 1000 expressions.
- Groxx 16y ago
  I don't think there is (without what follows)... I've tried a couple experiments, but without adding spaces I don't think it works. (though if you have one * on its own, followed immediately by a space, it keeps the * there). The correct way, though: add two spaces to the front. Then you get mono-spaced font, reproduced verbatim. Kinda like this: **************
  - benjoffe 16y ago
    Ah thanks, fixed.
- gcb 16y ago
  use to find that way of thinking mostly in perl hackers. A pity that people choose to sacrifice a lot of readability just to save a few characters in the source... it's not even justifiable in a interpreted language... in a language that you have to compile it's criminal
  - rayval 16y ago
    The source is not intended to be readable. The glory is in the 1433 characters total (or 133 lines, if you prefer that metric). Everyone knows that it is artificial, but it does not matter. The spirit is similar to the 10K Javascript contest (see http://10k.aneventapart.com/ http://10k.aneventapart.com/ ) If you want to try to understand the chess code, the author provides an expanded version with comments that is more readable: http://home.hccnet.nl/h.g.muller/maximax.txt http://home.hccnet.nl/h.g.muller/maximax.txt In order to read the code, it is helpful to understand the basic algorithm (recursive negamax search). Here is a good explanation of minimax, negamax and alphabeta: http://www.hamedahmadi.com/gametree/ http://www.hamedahmadi.com/gametree/
pnathan 16y ago
Code golf for chess. Sir, you are a hacker.
gcb 16y ago
i'm finding the documentation extremely interesting... but wonder how much it would be improved with properly named variables :)
- brewin 16y ago
  http://home.hccnet.nl/h.g.muller/maximax.txt http://home.hccnet.nl/h.g.muller/maximax.txt
KevBurnsJr 16y ago
This is what I assumed all code looked like before I started programming.
- sambeau 16y ago
  This is what all code looked like when I started programming.
parenthesis 16y ago
I am reminded of 1K ZX Chess: http://en.wikipedia.org/wiki/1K_ZX_Chess http://en.wikipedia.org/wiki/1K_ZX_Chess
pella 16y ago
ZX81 - chess ...only 672 bytes. source code: http://users.ox.ac.uk/~uzdm0006/scans/1kchess/ http://users.ox.ac.uk/~uzdm0006/scans/1kchess/ Micro-Chess, from 1976, which ran on a KIM-1 (6502) machine and used 1.1K of RAM. http://users.telenet.be/kim1-6502/microchess/microchess.html http://users.telenet.be/kim1-6502/microchess/microchess.html Toledo Javascript Chess Game http://nanochess.110mb.com/chess4.html http://nanochess.110mb.com/chess4.html + TOLEDO JS1K orking demo: http://js1k.com/2010-first/demo/699 http://js1k.com/2010-first/demo/699

91 points by starpilot 16y ago

According to the developer, Micro-Max has an Elo rating of about 2,000 (http://code.msdn.microsoft.com/huochess http://code.msdn.microsoft.com/huochess). A 2,000 Elo rating corresponds to "expert" per the USCF, or about the top 1% of players (http://en.wikipedia.org/wiki/Chess_expert http://en.wikipedia.org/wiki/Chess_expert). I've played at least a hundred games against it and lost every one. :P

hsmyers 16y ago
Without attempting to read the obscured code, the reason for the middling high Elo lies in the algorithms implemented. One of the AI discoveries is the sad fact that chess does not need intelligence, just horse power and a good per move check list. The algorithms listed provide both...assuming a decent implementation--- I can't tell because I'm not about to translate the code :)
- deleted 16y ago
  [deleted]
- Xk 16y ago
  Would you tell me how to enter my moves so that I can play it? I've been trying to figure out the correct format but can't seem to get it.
  - starpilot 16y ago
    I played it in Windows via Winboard (http://www.open-aurec.com/wbforum/viewtopic.php?f=19&t=50387 http://www.open-aurec.com/wbforum/viewtopic.php?f=19&t=5...), which has Micro-Max set as the default engine.
  - yhager 16y ago
    just enter source and dest, e.g.: d2d4 to move the pawn at d2 to d4.

jhonnycano 16y ago

The article says the source code measures 1433 characters !

benjoffe 16y ago

The article states the goal to be under 2000 characters, to state it in terms of lines of code (as the submitter has) is kinda misleading when the following is considered to be one line: if(*c-10){K=c[0]-16*c[1]+C;L=c[2]-16*c[3]+C;}else /* parse entered move */ edit: can't see a way to escape asterisk characters, so this outputs slightly wrong (edit2: fixed)

mathgladiator 16y ago
very true. It would be way more impressive to be in 1000 expressions.
Groxx 16y ago
I don't think there is (without what follows)... I've tried a couple experiments, but without adding spaces I don't think it works. (though if you have one * on its own, followed immediately by a space, it keeps the * there). The correct way, though: add two spaces to the front. Then you get mono-spaced font, reproduced verbatim. Kinda like this: **************
- benjoffe 16y ago
  Ah thanks, fixed.
gcb 16y ago
use to find that way of thinking mostly in perl hackers. A pity that people choose to sacrifice a lot of readability just to save a few characters in the source... it's not even justifiable in a interpreted language... in a language that you have to compile it's criminal
- rayval 16y ago
  The source is not intended to be readable. The glory is in the 1433 characters total (or 133 lines, if you prefer that metric). Everyone knows that it is artificial, but it does not matter. The spirit is similar to the 10K Javascript contest (see http://10k.aneventapart.com/ http://10k.aneventapart.com/ ) If you want to try to understand the chess code, the author provides an expanded version with comments that is more readable: http://home.hccnet.nl/h.g.muller/maximax.txt http://home.hccnet.nl/h.g.muller/maximax.txt In order to read the code, it is helpful to understand the basic algorithm (recursive negamax search). Here is a good explanation of minimax, negamax and alphabeta: http://www.hamedahmadi.com/gametree/ http://www.hamedahmadi.com/gametree/

pnathan 16y ago

Code golf for chess. Sir, you are a hacker.

gcb 16y ago

i'm finding the documentation extremely interesting... but wonder how much it would be improved with properly named variables :)

brewin 16y ago
http://home.hccnet.nl/h.g.muller/maximax.txt http://home.hccnet.nl/h.g.muller/maximax.txt

KevBurnsJr 16y ago

This is what I assumed all code looked like before I started programming.

sambeau 16y ago
This is what all code looked like when I started programming.

parenthesis 16y ago

I am reminded of 1K ZX Chess: http://en.wikipedia.org/wiki/1K_ZX_Chess http://en.wikipedia.org/wiki/1K_ZX_Chess

pella 16y ago

ZX81 - chess ...only 672 bytes. source code: http://users.ox.ac.uk/~uzdm0006/scans/1kchess/ http://users.ox.ac.uk/~uzdm0006/scans/1kchess/ Micro-Chess, from 1976, which ran on a KIM-1 (6502) machine and used 1.1K of RAM. http://users.telenet.be/kim1-6502/microchess/microchess.html http://users.telenet.be/kim1-6502/microchess/microchess.html Toledo Javascript Chess Game http://nanochess.110mb.com/chess4.html http://nanochess.110mb.com/chess4.html + TOLEDO JS1K orking demo: http://js1k.com/2010-first/demo/699 http://js1k.com/2010-first/demo/699