Slashdot Mirror
Computer Chess Created In 487 Bytes, Breaks 32-Year-Old Record
An anonymous reader writes: The record for smallest computer implementation of chess on any platform was held by 1K ZX Chess, which saw a release back in 1983 for the Sinclair ZX81. It uses just 672 bytes of memory, and includes most chess rules as well as a computer component to play against. The 32-year-old record has been beaten this week by the demoscene group Red Sector Inc. They have implemented a fully-playable version of chess called BootChess in just 487 bytes (readme file including source code).
Next you'll be telling me you can create operating systems in less than 15GB!
or "play-worthy" ?
There's a difference.
That doesn't sound like real chess.
Mark it as number of bits. Assuming everything else is in order. And that the effort isn't all down the crapper by tomorrow. Reminds me of a person who did the best assembler ever, he so claimed. He died before anyone else got to use it. Back then, powerful assemblers were sought after like whatever comes before willows. Compilers, especially for micros, where not good at all. Ah, but no one here gets that. I will re-enter the man-cave.
Jesus, I remember getting cracked games from them in, like, 1991. Are they beating their previous record?
Reading from the source code
No under promotion
No en passant pawn capture
No castling
This may be a game but it is not chess.
0 GOSUB 10000
1 INPUT "DO YOU WANT INSTRUCTIONS (Y OR N)?",A$: IF A$#"Y" AND A$#"N" THEN 1: IF A$="Y" THEN GOSUB 30000
2 REF=5: CALL -936
3 INPUT "COMPUTER TO PLAY WHITE(0) OR BLACK(1)",WHO
4 IST=0
5 DIM WC(99),BC(99)
6 DIM V(6),P(26),C(3)
7 DIM KING(16)
8 DIM A(70)
10 DIM M(120),W(120),B(120),I(6)
11 DIM G(100)
12 FOR X=1 TO 120:M(X)=0: NEXT X
14 FOR X=1 TO 99:W(X)=0:B(X)=0: NEXT X
15 FOR X=2 TO 9:X1=10*X:X2=X1+1:M(X1)=7:M(X2)=7: NEXT X
16 DIM STR$(10),FILE$(8),RANK$(8)
17 FILE$(1)="A":FILE$(2)="B":FILE$(3)="C":FILE$(4)="D":FILE$(5)="E":FILE$(6)="F":FILE$(7)="G":FILE$(8)="H"
18 RANK$="12345678"
20 FOR K=1 TO 21:K2=K+99:M(K)=7:M(K2)=7: NEXT K
22 FOR K=32 TO 39:K2=K+50:M(K)=1:M(K2)=-1: NEXT K
23 M(22)=4:M(23)=2:M(24)=3:M(25)=5:M(26)=6:M(27)=3:M(28)=2:M(29)=4
25 FOR K=22 TO 29:K2=K+70:M(K2)=-M(K): NEXT K
30 I(1)=12:I(2)=15:I(3)=10:I(4)=1:I(5)=6:I(6)=6
35 V(1)=1:V(2)=3:V(3)=3:V(4)=5:V(5)=9:V(6)=10
40 P(1)=-1:P(2)=1:P(3)=10:P(4)=-10:P(5)=0:P(6)=1:P(7)=-1
45 P(8)=10:P(9)=-10:P(10)=-9:P(11)=-11:P(12)=9:P(13)=11:P(14)=0
50 P(15)=8:P(16)=-8:P(17)=12:P(18)=-12:P(19)=19:P(20)=-19
55 P(21)=21:P(22)=-21:P(23)=0:P(24)=10:P(25)=20:P(26)=0
60 C(1)=8:C(2)=0:C(3)=3
80 IF WHO=1 THEN 90
85 M(25)=6:M(26)=5:M(95)=-6:M(96)=-5
90 GOSUB 5000
93 FOR II=1 TO 120:W(II)=0:B(II)=0: NEXT II
95 IF WHO=1 THEN 100:T2=0: GOTO 1000
100 REM MAKE MOVE
101 GOSUB 4000
105 Z9=0
110 GOSUB 4200
115 GOSUB 5000: IF WHO=0 THEN 1000
116 M9=M9+1: IF M9>REF THEN 120
117 IF T2>4 THEN 120: IF IST=1 THEN GOTO 120
118 F2=9-F2:T2=9-T2: GOSUB 4200: GOSUB 5000: GOTO 100
120 REM FILL CONTROL ARRAYS
122 N8=0:IST=1
125 FOR X1=22 TO 99:WC(X1)=0:BC(X1)=0: IF M(X1)=6 THEN BKING=X1: IF M(X1)=-6 THEN WKING=X1: NEXT X1
130 FOR X=22 TO 99: IF M(X)<1 THEN 170: IF M(X)=7 THEN 170: GOSUB 8000: IF N9=0 THEN 170
150 FOR X1=1 TO N9:TO=G(X1)-G(X1)/100*100: IF M(TO)>0 THEN 168
164 N8=N8+1:A(N8)=G(X1)
168 BC(TO)=BC(TO)+1
169 NEXT X1
170 NEXT X
172 FOR X=22 TO 99: IF M(X)>-1 THEN 180: GOSUB 8000
173 IF N9=0 THEN 180
174 FOR X1=1 TO N9:TO=G(X1)-G(X1)/100*100:WC(TO)=WC(TO)+1
176 NEXT X1
180 NEXT X
181 GOTO 3000: REM CASTLE LOGIC
182 REM FILL KING CONTROL ARRAY
184 KING(1)=BKING+1:KING(2)=BKING-1:KING(3)=BKING+10:KING(4)=BKING-10
185 KING(5)=BKING+11:KING(6)=BKING-11:KING(7)=BKING+9:KING(8)=BKING-9
186 KING(9)=WKING+1:KING(10)=WKING-1:KING(11)=WKING+10:KING(12)=WKING-10
187 KING(13)=WKING+11:KING(14)=WKING-11:KING(15)=WKING+9:KING(16)=WKING-9
190 V9=-10000:I9=0: FOR X4=1 TO N8:N4=0:F4=A(X4)/100
210 T4=A(X4)-F4*100:F5=M(F4):T5=M(T4)
212 REM FIND MOVES OFPIECE IN PRESENT POSTION.
214 X=F4: GOSUB 8000
225 M(T4)=M(F4):M(F4)=0
235 GOSUB 9000: IF N4<=V9 THEN 255
245 V9=N4:F9=F4:T9=T4
255 M(F4)=F5:M(T4)=T5:
256 Z9=Z9+1: IF Z9>20 THEN Z9=1: TAB 26: VTAB Z9: PRINT F4;" : ";T4;" V= ";N4
259 NEXT X4
270 F1=F9:T1=T9:M(T1)=M(F1):M(F1)=0:F6=F1-F1/10*10-1:F7=10-F1/10:T6=T1-T1/10*10-1:T7=10-T1/10
280 IF WHO=1 AND F1=22 THEN QROOK=1
281 IF WHO=1 AND F1=29 THEN KROOK=1
282 IF M(T1)=6 THEN MKING=1
283 IF WHO=0 AND F1=22 THEN QROOK=1
284 IF WHO=0 AND F1=29 THEN KROOK=1
310 PRINT "FROM ";F6;F7
Toldja, 640 bytes otta be enough for anyone. -Gill Bates
Table-ized A.I.
It would be cool to see which programming languages could have the best short chess programs.
I'd nominate Haskell, scheme and prolog to try it in.
From the readme:
Underpromotion may be understandable, maybe en-passant since it doesn't come up that oftean, but castling makes a ton of games unplayable.
Also, purists consider anything that implements these three rules to be a better record than something that omits three rules.
I never before heard a claim that the ZX-81 held a record, and I don't believe that it did. Back in the 70's (1975 or 1976) I received a copy of a chess program from Fairchild for their F8 computer prototype board, It fit in 1K of 8 bit memory (sorry, I don't remember how many bytes were left over, if any). I don't remember if it could under-promote, but I'm pretty sure that it could castle and allowed en-peasant moves. This was a novel and interesting microcomputer (the CPU didn't even have a program counter - but the memory management chip did!) and it certainly wasn't popular with hobbyists (although it was used in the Fairchild Channel F video game that came to market before the Atari 2600), but they did sell some $100 prototype boards and I bought one, mainly because I was so impressed by the 1K chess program.
I'm an American. I love this country and the freedoms that we used to have.
Surely the record depends on the expressiveness of the instruction set of the chip you are programming for. With a suitably advanced chip I could implement chess in 1 byte. It would be an instruction that looks like this:
JMP CHESS.
and an instruction that implements chess.
What do you mean by short? Small executable size? Small LoC count? (or chars, or any way to measure the source code?) Can you use libraries? Make a chess library and #import playchess.py ?
What's the point of setting a record if the program is not working correctly? This chess program does not implement full chess rules. For example, it does not understand castling, moves the king into check (illegal move), does not test to various draws (e.g. stalemate, 50 moves rule), does not understand en-passant, etc.
To be clear, I am not complaining that this is not a good chess program; what I say is that this is NOT a chess program!
I implemented a chess game in pygame and python, didnt have all the rules either and i stopped developing it because it used all of my 4 Gb of memory to run in. Probably the most bloated game of chess ever invented, do I get a prize too.
Just build a CPU that includes Chess rules, and voilà. The assembly code would be merely a call to the CPU chess, or maybe a loop. A few bytes at most.
Slashdot, fix the reply notifications... You won't get away with it...
There are many rules that only come up in a very small number of games. For example, the fifty-move rule which states that the game ends in a draw if you play 50 moves without any pawns moved or any captures made (or 100 moves in certain special board states). I can see why such a rule needs to exist... but at the same time I'm willing to call this proof of concept as chess even if it doesn't fully implement that.
purists of what?
what you can be sure though is that red sector has a better theme than the others.. https://www.youtube.com/watch?...
world was created 5 seconds before this post as it is.
I think you mean "which was released", computer programs can't 'see' anything...
Does anyone else remember the hacked version of Great Giana Sisters from Red Sector. I assume it's the same people.
Anyway, completely awesome achievement...It would probably take me ages to write something similiar in a high-level language. Amazing.
I don't think that means what you think it means...
BootChess vs1K ZX Chess
Probably a bit like watching snails race, but snail-races can get interesting.
I’m old enough to remember 16K of memory being described as “whopping”
The guy who wrote the game in 487 bytes is truly a master of coding and deserves all the respect. And the amount of work that has gone into the game and the readme.txt must be quite awesome. I bet the people who complain the small omissions in chess rules could not code themselves out of wet paperback.
... when you consider the ZX81 chess was written in Z80 assembler whereas this is in x86 asm and although both have variable sized instructions the x86 will on average be larger.
Why can't people like you just appreciate the technical accomplishment instead of nit picking.
Tell you what - why not go away and try and write any type of chess program then get back to us?
As someone who has written a chess program which even after some code optimisation still came out at ~3000 lines of C, I can tell you this is damn impressive.
Would that be called "Mad Larry"?
Uh, oh. Back to work.
I'd rather see them take out the graphics and add the missing rules instead.
Support the First Amendment. Read at -1
Does the processor have a hardware multiply? Does it have indexing? ... Does it have chess built in?
Given the right processor I can write a full featured chess that can beat grand masters, in 1 bit.
If the first bit of new process is on, the hardware instruction set implements a complete "play chess" inside the processor. If it is off, then the other bits of the process form a complete machine language implementation like x86 for instance.
It only makes sense that eventually that record would be broken just as this will be. Why? As more processor instructions become available fewer are needed.
Genie: Phenomenal cosmic powers! [shrinks down inside the lamp].
Genie: Itty bitty living space!
I'd like to see their implementation of Tic Tac Toe. Lets have it in the standard 3x3 matrix. Go...
Why do the comments in the file make me think that I am reading the rants on a bottle of Dr. Bronner's Soap???
My source states that a checkerboard has 64 squares, like a chessboard.
Here's a chess playing program in 14 bytes, written in BBC Basic.
1 P."I Resign"
A pizza of radius z and thickness a has a volume of pi z z a
I've noticed that they take a fairly liberal definition of "chess", as they simply discard certain rules, such as en passant pawn capture or castling moves, which are pretty important chess moves. It's a bit hard to argue that this is really "chess" if they just decide to leave out inconvenient rules ("chess lite?"). I probably wouldn't complain about other ommissions such as the 3-repetition rule, but castling?
Even so, a very cool accomplishment in micro-optimization techniques.
The game is also a cheat by performing illegal moves. This is not something that counts as a chess program. Queen takes pawn, K moves next to queen - that's a fail.
..n.....6
..b.....5
........4
......PP3
..n.....6
..b.....5
........4
.....KqP3
abcdefgh9
r.b.kr..8
ppq...pp7
PPPPK..R2
R.BQ....1
c7g3????
results in:
abcdefgh9
r.b.kr..8
pp....pp7
PPPP...R2
R.BQ....1
????????
Great, let's just redefine "chess program" to mean "any program that anyone on earth could consider a game." There, now we have all possible chess variants covered you annoying pedant.
Well, the real question is if this program was replicating the same rules as the one that was previously accepted and supposedly beat?
You say your program plays chess But it's just chessette. I've been to France So let's just dance.
Yes, it is indeed terrible how people such as myself have to ruin everything. The nit picky truth is such a pain in the fundament. And we were all having such fun too. Obviously I have never written a chess program myself, because if I had, I would surely stand in mute awe at this impressive achievement. And it is impressive; testing out hundreds of versions of code to find the one with the smallest footprint. I would never have the patience to do that. I just agree with Sigma 7 that the record for a program that plays real chess would be of greater interest to me. I don't mind losing 3-time repetition or the 50-move rule. Apparently the vast majority don't mind several other rules trimmed away as well. To each their own.
It's pretty clear that the developer put more interest in making a small chess program that in making a good chess program. Not a bad effort, though!
Great achievement. Congratulations.
But the comparison with 1K ZX81 Chess is ludicrous because:
1.) Original 1K ZX81 Chess wasn't even optimized for code size. It was simply optimized to fit as much logic as possible within 1K (including code size, data area, execution stack and even display video memory) since that's all the memory the original ZX81 had available for everything. For instance, the original had extra code to make display video memory smaller than usual.
2.) It makes no sense to compare programs using different instruction sets. The 80x86 assembly (used in new implementation) is a lot more powerful than Z80 assembly (used in original 1K ZX81 Chess). 80x86 has more registers (thus reducing the need to store intermediate results in memory) and it can perform complex operations (even "multiply" in a single instruction"), etc. So it's no surprise that a 80x86 version would be smaller.
3.) The claim about "32 year-old record" is bulls**t. This new implementation is almost 200 bytes shorter than original 1K ZX81 Chess, but guess what? Here's an optimized version of original 1K ZX81 Chess from last year, in Z80 assembly, that was also almost 200 bytes shorter:
http://www.sinclairzxworld.com/viewtopic.php?f=4&t=1476
awesome - it's the year 2015 and some headline a bygone tech site brings up memories of TRSI.
Another one in 481 bytes that seems to play better and doesn't make illegal movements Toledo Atomchess http://nanochess.org/chess6.html
it is an impressive feat to contain a chess programme in such a small size (although it doesnt implement MiniMax).
although smaller — it would be interesting to see the result of a game of ZX81 1K Chess vs BootChess — which engine would win??
2cents
j
I can do it in under _ten_ bytes if I'm allowed to arbitrarily ignore whatever rules of Chess I want to.