Current world's smallest chess program

[amanjpro]

It doesn't translate from whitespace language to C++ unless I'm missing something

It translates from "binary whitespace" (tab / space) to machine code and runs it. This example is just "mov al, 100; ret;" but we can put any code there. The final code then becomes something like:

Code: Select all

n;main(){char s[]="	 		     		  	  		    		";
while(s[n])s[n++/8]+=s[n/8]+s[n]%2;((int(*)())(void*)s)();}

This is 79 non-whitespace characters.

I shall call this program Emanuelito -- The World's by Far Tiniest Chess Engine.

By slapping Stockfish in there we obtain ELO rating 3550, in 79 characters of C code. ¡Wow!

You are kidding right? You still need to encode SFin your binary format, and this becomes a massive codebase... And in this case ws matters, because they are part of the language, in C like languages it doesn't matter, because they are not

[j.t.]

It doesn't translate from whitespace language to C++ unless I'm missing something

It translates from "binary whitespace" (tab / space) to machine code and runs it. This example is just "mov al, 100; ret;" but we can put any code there. The final code then becomes something like:

Code: Select all

n;main(){char s[]="	 		     		  	  		    		";
while(s[n])s[n++/8]+=s[n/8]+s[n]%2;((int(*)())(void*)s)();}

This is 79 non-whitespace characters.

I shall call this program Emanuelito -- The World's by Far Tiniest Chess Engine.

By slapping Stockfish in there we obtain ELO rating 3550, in 79 characters of C code. ¡Wow!

That is actually a very nice idea (IOCCC for example, ecourages creative abuse of rules "When ';', '{' or '}' are within a C string, they may still not be counted by the IOCCC size tool. This is a feature, not a bug!", "Legal rule abuse is encouraged to help promote creativity. Rule abuse entries, regardless of if they receive an award, result in changes to the next year's rules and guidelines.").

It doesn't work like this though, as most operating systems don't allow execution of memory. There may be some workaround, though.

[j.t.]

Here is the "smallest" chess playing program ever. Somehow it is very similar to the engine Nalwald, that I am currently working on ...
WhitespaceChess

Probably only works on Linux.
The solution, how to execute machine code from memory, is rather uninspiring. But unfortunately, it is really hard to dynamically execute code from memory. The reason is mostly that the whole thing with the ELF header and absolute vs relative addresses is not easily solvable (i.e. it would require enormous amount of work and knowledge). A solution could be to write the chess engine directly in assembly such that it fits in the calling program. But again, this would require lots of work.
A final note: This program would not actually qualify for IOCCC, as the maximum size for entries regardless of whitespaces must be below 4096 bytes.

[lithander]

Here is the "smallest" chess playing program ever. Somehow it is very similar to the engine Nalwald, that I am currently working on ...
WhitespaceChess

You're my hero of the day! (but my texteditor doesn't even manage to load the file and render it properly)

[klx]

That is actually a very nice idea

Thanks!

Here is the "smallest" chess playing program ever.

Nice! Yeah that's the "easy" approach -- just encode the executable as binary, write it to a file, and run it. Your code is still very verbose though, and has one bug First the bug:

- Your "len" should be (strlen(data)+7)/8, unless you've taken care during construction that the data size is always a multiple of 8

Now four tricks to reduce size:

- You don't need the memset if you're using the approach I did (essentially shifting the junk out of the bytes)
- You also don't need the malloc and new array if you overwrite the data array
- By overwriting the data array, you also don't need the "strlen", since at the end you can use "i" to determine the length
- "(data[n] == ' ')" can be written as "data[n]%2"

You're my hero of the day!

Thanks! I knew you'd change your mind eventually!

[j.t.]

- Your "len" should be (strlen(data)+7)/8, unless you've taken care during construction that the data size is always a multiple of 8

I generate the string using this program, so it is always made sure that the data string is an exact representation of a binary.

You're right, it's not really optimized for minimal number of characters. I didn't want the code to be actually obfuscated, and I thought it is more readable like this.

I also just tried to replace my solution with what you wrote, however it segfaults. Not sure what the problem is, but feel free to experiment yourself (maybe I just missed something obvious).

[hgm]

Well, since the rule for counting the length of chess programs is that everything that cannot be deleted must be counted, Whitespace Chess doesn't score very well on this count. What you can get away with in IOCCC is't really relevant.

[maksimKorzh]

Hi guys, I'd like to post my deobfuscation effort on Oscar's work (from his permission).
I've been working with this JS version:

Code: Select all

<html>
<head>
<title>1K Javascript Tiny Chess by Óscar Toledo G. ©2010</title>
</head>
<body>
<script>
for(B=i=y=u=b=i=5-5,x=10,I=[],l=[];B++<304;I[B-1]=B%x?B/x%x<2|B%x<2?7:B/x&4?0:l[i++]="ECDFBDCEAAAAAAAAIIIIIIIIMKLNJLKM@G@TSb~?A6J57IKJT576,+-48HLSUmgukgg OJNMLK  IDHGFE".charCodeAt(y++)-64:7);function X(c,h,e,s){c^=8;for(var o,S,C,A,R,T,G,d=e&&X(c,0)>1e4,n,N=-1e8,O=20,K=78-h<<9;++O<99;)if((o=I[T=O])&&(G=o^c)<7){A=G--&2?8:4;C=o-9?l[61+G]:49;do if(!(R=I[T+=l[C]])&&!!G|A<3||(R+1^c)>9&&G|A>2){if(!(R-2&7))return K;n=G|(c?T>29:T<91)?o:6^c;S=(R&&l[R&7|32]*2-h-G)+(n-o?110:!G&&(A<2)+1);if(e>h||1<e&e==h&&S>2|d){I[T]=n;I[O]=0;S-=X(c,h+1,e,S-N);if(!(h||e-1|B-O|T-b|S<-1e4))return W(),c&&setTimeout("X(8,0,2),X(8,0,1)",75);I[O]=o;I[T]=R}if(S>N||!h&S==N&&Math.random()<.5)if(N=S,e>1)if(h?s-S<0:(B=O,b=T,0))break}while(!R&G>2||(T=O,(G||A>2|(c?O>78:O<41)&!R)&&++C*--A))}return-K+768<N|d&&N}function W(){i="<table>";for(u=18;u<99;document.body.innerHTML=i+=++u%x-9?"<th width=60 height=60 onclick='I[b="+u+"]>8?W():X(0,0,1)'style='font-size:50px'bgcolor=#"+(u-B?u*.9&1||9:"d")+"0f0e0>&#"+(I[u]?9808+l[67+I[u]]:160):u++&&"<tr>")B=b}W()
</script>
</body>
</html>

Which can be played here: https://nanochess.org/archive/tiny_chess_1.html

Now here's the deobfuscated version with meaningful variable names and detailed comments (adding comments is still in progress):
https://github.com/maksimKorzh/toledo-c ... cated.html

And obviously it's playable:
https://maksimkorzh.github.io/toledo-ch ... cated.html
(open dev tools to see debugging info)

Also I made a series of live streams demonstrating the deobfuscation process from scratch:


P.S. Oscar, what do you think of it? How precise the deobfuscation is? Could you please give me a feedback?