Slashdot is powered by your submissions, so send in your scoop

 


Forgot your password?
Close
typodupeerror
×
Open Source Programming Games

Computer Chess Created In 487 Bytes, Breaks 32-Year-Old Record 204

Posted by Soulskill from the go-small-or-go-home dept.
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).
This discussion has been archived. No new comments can be posted.

Computer Chess Created In 487 Bytes, Breaks 32-Year-Old Record More

Computer Chess Created In 487 Bytes, Breaks 32-Year-Old Record

Comments Filter:

  • Incredible! (Score:5, Funny)

    by DigitAl56K ( 805623 ) on Wednesday January 28, 2015 @01:20AM (#48921377)

    Next you'll be telling me you can create operating systems in less than 15GB!

    • Re:Incredible! (Score:5, Insightful)

      by Dutch Gun ( 899105 ) on Wednesday January 28, 2015 @01:39AM (#48921441)

      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.

      • Re:Incredible! (Score:5, Interesting)

        by Anonymous Coward on Wednesday January 28, 2015 @02:56AM (#48921699)

        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?

        Hmmm ... Read your history of chess - Modern Chess is a variant called "Mad Queen" - there are more variants of chess than there are of Poker, and just because we have become used to an agreed-upon standard does not invalidate other styles ...

        • Re:Incredible! (Score:5, Insightful)

          by Anonymous Coward on Wednesday January 28, 2015 @05:44AM (#48922179)

          Modern Chess is not now a variant called Mad Queen. It is a standardized game referred to as Chess and understood world-wide.

          Modern chess may have originated in a game that at one time was referred to as "Mad Queen".

          • Re:Incredible! (Score:4, Funny)

            by OakDragon ( 885217 ) on Wednesday January 28, 2015 @09:33AM (#48923261) Journal
            They would have included a disclaimer, but that would have pushed up the byte count.

          • Modern Chess is not now a variant called Mad Queen. It is a standardized game referred to as Chess and understood world-wide.

            Unless you're in China, [wikipedia.org] where it's understood to be something different. Or Japan. [wikipedia.org] Or Korea. [wikipedia.org] Or...

            • I don't understand the point of your post at all? Yes, other nations have games that are similar to Chess (and that are genetically related to Chess--think 4th cousins twice removed) but that are not Chess and are not even called Chess!

              Chess != Shogi != Shatranj != etc...

        • Oh yeah. I play this variant of chess called "One Pawn On One Square." The opening position is a white pawn on a white square. I coded a version of it in 2 bytes. Guess I broke the record for "Smallest Chess Program."

        • Re: (Score:3)

          by obarel ( 670863 )

          I think the point is that you don't win a 100m race by running 90m and then arguing about the exact definition of a metre.

          It's an incredible feat to squeeze any variant of chess into 487 bytes, but if you're going to compare apples to apples and maintain a record, the games should follow the same rules.

      • Re:Incredible! (Score:5, Informative)

        by hcs_$reboot ( 1536101 ) on Wednesday January 28, 2015 @03:27AM (#48921777)
        To be fair, the ZX81 had only 1k of RAM. So they had to cut through the chess rules. Nowadays they could of course implement the whole game including all rules. But would that be interesting provided that it couldn't compare to that 1983 program?

        • Re: (Score:2, Insightful)

          by Dutch Gun ( 899105 )

          I suppose that's legit, if they're purposely reproducing the limitations of that original program, in which case there's a baseline to measure against with similar rule sets. Do you happen to know if that's the case - that the chess rules actually match? I read the articles linked but didn't see that specifically mentioned.

          I still have an issues with the claim of "world's smallest chess program on any platform", though, because it's not a complete chess program as nearly anyone would define it.

        • Comment removed based on user account deletion

          • Atari 2600 cartridges are 4 kB maximum. It's certainly possible the game only used a fraction of that, but highly unlikely.

            The 2600 did only have 128 bytes of RAM, but none of this would be needed for the program itself, which would be accessed directly from cartridge ROM by the CPU. On the ZX, the code would have to fit within the 1kB and the remaining RAM would be available for its execution.

      • Re: (Score:3)

        by reanjr ( 588767 )

        I've tried many cheap versions of electronic chess, and most of them have no support for en passant (a couple don't have support for castling either). Not only that, but playing against other players, most people who play chess for recreation don't seem to know about an passant, anyway. So, let's call it's chess 2.0. Streamlined for the modern audience.

    • Re: (Score:2, Informative)

      by Anonymous Coward

      Depends on what you consider an operating system. Alpine Linux uses 130 MB (http://alpinelinux.org/about), including an usable graphical interface (Xfce).

      A really minimal system, like a virtual machine running a site, can be reduced to far less than that. For instance, Mirage OS (http://www.openmirage.org).

      Windows, OSX, and some Linux distros are not designed to be tweaked like that.

      • Re: (Score:2, Informative)

        by Anonymous Coward

        Don't forget MenuetOS [menuetos.net] and its opensource derivative KolibriOS [kolibrios.org]. They fit on a single floppy.

      • Re: (Score:2)

        by gl4ss ( 559668 )

        or.. you know.. some old ass whatever distro..
        or win95.. fits nicely.

        or dos with win 3.11, fits even nicer...

      • Re: (Score:2)

        by lgw ( 121541 )

        A really minimal system, like a virtual machine running a site, can be reduced to far less than that. For instance, Mirage OS (http://www.openmirage.org).

        We've seen a web server running on a Commodore 64. Wasn't that a 12 kB OS? It's been a while, but IIRC the OS was in memory from D000 to FFFF.

        I've worked on mainframes where the "recovery OS" fit on one tape block - a hard 32 kB constraint (used for disaster recovery - it would load a program that also had to fit in 32 kB which would restore a system from backups). The normal OS wasn't much bigger. Most device drivers weren't memory resident, for example, and shared 4 kB by swapping in and out, which co

    • Next you'll be telling me you can create operating systems in less than 15GB!

      Indeed they can. Unfortunately they decided to let the people responsible for ACPI actually follow through on that, and then decided that it would make a good bootloader.

    • Re:Incredible! (Score:5, Funny)

      by Tablizer ( 95088 ) on Wednesday January 28, 2015 @02:26AM (#48921585) Journal

      Next you'll be telling me you can create operating systems in less than 15GB!

      If you complain, we'll re-write it in Java and make it 30GB

    • Comment removed based on user account deletion
      • But... but... these kids will never learn the joy of fiddling with jumpers, or rearranging their config.sys!

  • "Fully-playable" (Score:4, Interesting)

    by scottbomb ( 1290580 ) on Wednesday January 28, 2015 @01:23AM (#48921383) Journal

    or "play-worthy" ?

    There's a difference.

  • Apple Integer BASIC Chess (Score:5, Interesting)

    by beaverdownunder ( 1822050 ) on Wednesday January 28, 2015 @01:42AM (#48921455)
    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

  • He was right! (Score:4, Funny)

    by Tablizer ( 95088 ) on Wednesday January 28, 2015 @01:47AM (#48921473) Journal

    Toldja, 640 bytes otta be enough for anyone. -Gill Bates

  • Best short programs (Score:4, Interesting)

    by Cafe Alpha ( 891670 ) on Wednesday January 28, 2015 @01:51AM (#48921491) Journal

    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.

    • Also lua which is actually pretty close to self in power. Or smalltalk.

    • 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.

      To make things fair, I think you'd have to define the valid set of languages as general purpose languages. I could see coming up with a chess-specific language that would be super-efficient in that the language would already have known chess properties as built-in elements.

      Yaz

      • Well I think part of what makes a higher level language is the potential for writing powerful special purpose languages in it easily.
        Scheme and prolog both have macros and both have the ability to compile code at run time as well. Prolog also has the ability to define new operators. And it's awfully good at parsing, building and walking trees.

        • Back in the day I learned Lua by programming 254-byte (I think) macros. As far as I know, the one-letter globals didn’t do any harm and it was good fun. Once I worked out how to write add-ons of unlimited size, my programming skills and code legibility improved greatly.

    • Re: (Score:2, Informative)

      by Anonymous Coward

      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.

      The game discussed here is written in x86 asm. The source code is certainly having more bytes than 487b, but the compiled result is just 487b. If you would write it in any of the languages you mentioned, the compiled result would be bigger.

      • Well I said "best" short programs. I suspect that that tiny program isn't "good", ie plays a crumby game.

        Prolog is very good at encoding rules very succinctly and does depth first searches automatically (it's a bit harder to get more advanced search strategies, but it can be done.) Scheme has continuations so one could probably encode more kinds of search more succinctly than even prolog. Haskell has normal order lazy evaluation, so it's succinct to separate search strategies from state generation, though

        • You're missing the point, it's the size of the binary image on disk that is remarkable, not the size of the source text. Short source text can easily be achieved by putting "chess.exe" in a cmd file.

        • What you're saying doesn't matter. The point is that the measured result has to include the runtime environment. Because of that, even "Hello World" in Prolog, Scheme, or Haskell is probably* going to be bigger than 487 bytes.

          (* I haven't actually looked up the runtime size of those languages.)

      • Re: (Score:2)

        by tibit ( 1762298 )

        Probably if they allowed themselves to use the full 512 bytes, it could enforce all the rules. Alas, I wonder what would come out with APL :)

    • Re: (Score:2)

      by aralin ( 107264 )

      If you think in terms of as much stuff done in as little characters as possible, there is no competition for PERL.

      I think this particular competition though is counting bytes of machine code. I thought I was pretty good myself with reducing a printer driver into 136 bytes, but Chess in 500 that is really something.

    • Zipped Scheme would be pretty small, once the right parentheses are compressed.

    • Re: (Score:2)

      by gnupun ( 752725 )

      If you want small, forth is probably the best... better than assembly. Java uses it to convert source to forth-like intermediate language (jvm) opcodes.

    • Perl would win hands down no contest.

      I've never figured out how this one works:
      http://www.99-bottles-of-beer.... [99-bottles-of-beer.net]
      (not that I've tried too hard - its just a work of art)

    • Could anyone do it in one line of APL [cloud9.net]?

  • Missing chess rules (Score:3)

    by Sigma 7 ( 266129 ) on Wednesday January 28, 2015 @02:17AM (#48921567)

    From the readme:

    -you don't get under-promotion ;
        -you don't get "en passant" pawn capture ;
        -you don't get castling (queen or king side) ;

    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 cou

  • 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.

    • Re: (Score:2)

      by PhilHibbs ( 4537 )

      That's what mathematicians refer to as "trivial", which is one of the most derogatory terms in mathematics.

      • Which is exactly his point. Even 16-bit x86 processors have more general-purpose register space than z80, so there should be fewer memory calls required. x86 has a more sophisticated instruction set (z80 has no multiplication instruction), so program the exact same algorithm in the two assemblers and you will get a smaller program in x86 than in z80.

    • 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.

      One whole byte! You slacker. You could implement this as one bit - have it be the only instruction.

  • 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.

    • Specialized chess hardware has been very high profile.

      Deep Blue used specialize circuitry :(
      Before that there was Hi Tech

  • I want a showdown! (Score:4, Interesting)

    by ockegheim ( 808089 ) on Wednesday January 28, 2015 @05:26AM (#48922119)

    BootChess vs1K ZX Chess

    Probably a bit like watching snails race, but snail-races can get interesting.

  • Its even more impressive... (Score:5, Interesting)

    by Viol8 ( 599362 ) on Wednesday January 28, 2015 @06:10AM (#48922287) Homepage

    ... 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.

    • ... 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 do you say that?

      My understanding (and if I'm wrong feel free to correct) is that the Z-80 is a bastard clone of an 8080. So, byte-for-byte there should be no difference between the two (if you keep the x86 in real mode). BIOS calls and the need to implement the boot sector code add some guff to the x86, of course, which makes RSI's achievement that much more impressive.

    • Only if you do a one-for-one mapping of instructions. The x86 can take advantage of more sophisticated opcodes (eg MULT) to cut down on the number of instructions and its general purpose registers to reduce Load and Store calls (with the associated address bytes). I'd expect x86 to be shorter, if programmed correctly....
  • I'd rather see them take out the graphics and add the missing rules instead.
  • Why do the comments in the file make me think that I am reading the rants on a bottle of Dr. Bronner's Soap???

  • Here's a chess playing program in 14 bytes, written in BBC Basic.

    1 P."I Resign"

Slashdot Top Deals

HELP!!!! I'm being held prisoner in /usr/games/lib!

Close