Interview: Douglas Bagnall on 5K Chess - WebReference Update - 020703
((((((((((((((((( WEBREFERENCE UPDATE NEWSLETTER ))))))))))))))))) July 3, 2002
___________________________ Sponsors ________________________________ This newsletter sponsored by: Instant Messaging Planet Fall 2002 Conference & Expo Search Engine Strategies - Coming to San Jose! _____________________________________________________________________
This week we interview Douglas Bagnall, the author of a 5K chess game entered in this year's 5K contest. There have been previous 5K chess entries, but none as elegant or cross-platform. We asked Bagnall why he did it, and how he crammed a decent chess player into only 5K of JavaScript.
https://www.webreference.com *- link to us today https://www.webreference.com/new/ *- newsletter home https://www.webreference.com/new/submit.html *- submit article
New this week on WebReference.com and the Web:
1. INTERVIEW: Douglas Bagnall on 5K Chess
Like what you see? Get our front page e-mailed to you every business day with our HTML newsletter. Just send an e-mail to:
or for this text newsletter:
Spread the word! Feel free to send a copy of this newsletter to your friends and colleagues, and while you're at it, snap a link to WebReference.com.
/-------------------------------------------------------------------\ Don't miss Instant Messaging Planet Fall 2002 Conference & Expo coming to San Francisco on Sept 9-10. The first focused event of its kind, Instant Messaging Planet is the only industry forum that will bring together IM experts and professionals in order to exchange "IM in the Enterprise" ideas, strategies and IM success stories. For more information and to register today, visit https://www.intmediaevents.com/im/fall02.
\--------------------------------------------------------------adv.-/
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1. INTERVIEW: Douglas Bagnall on 5K Chess
The 2002 edition of the 5K contest has begun, and the first "anything goes" entries are in. One entry in particular caught my eye, a sub-5K chess game. The author, Douglas Bagnall, has crammed a brash 1000-1200 rated player into a fast fun experiment into human behavior. There have been previous chess entries, but not as cross-browser or elegant at this version. I talked to Bagnall about his entry, how the game works, and how he crunched 30K of code down to less than 5K.
https://www.the5k.org/description.asp/entry_id=719
WEBREF: Can you tell me what inspired you to do this?
BAGNALL: Well, it seemed like a challenge. After writing a space invaders clone in the 2000 5K (https://www.the5k.org/description.asp/entry_id=113), I wanted to do something more computationally intense with less fiddly cross- browser DHTML. Chess fit.
There was a legendary 1K chess program written for the Sinclair ZX-81, but it didn't do the tricky things like castling, queening and en passant. I reasoned that that stuff would fit in 3K, allowing 1K for UI, and that modern JavaScript wouldn't be very much slower than Z80 machine code. So I started.
I like the tension between optimizing for speed and for size, and the contemplative coding and design that goes into making small things slowly. That's why I didn't stop. My development code got up to about 30K, including proper variable names, indentation, comments, and extra features which I only reduced down to 4.4K on the eve of the deadline.
WR: How did you optimize the code down to 4.4K?
DB: By hand. I have a Python script that would do most of it, but that would have left the code in a state I couldn't understand, making further tuning difficult.
Always save your files in UNIX or Mac format. A line break takes two characters in DOS, and one in other operation systems, which gives you an immediate saving of hundreds of bytes. Or you can replace them with semi-colons, as many people do.
But the main secret to a 6:1 reduction ratio is to put lots of redundant information in the original. There was test code, comments, and full indentation. It made the development easier, and the squeezing out process more satisfying. For my 2000 entry I tried to keep it small throughout the process, and it ended up in a bit of a mess.
WR: How does it work strategy-wise?
DB: It has no sense of the whole board while evaluating moves, but looks at each in isolation, judging on material taken and (decreasingly through the game) whether a move vector is centralizing. Pawns are simply encouraged onwards, except at the start when they aim for the middle. My theory was that the computer's best chance was in getting lots of stuff out and busy early on. If a game is even after 25 moves, you've won - it has no end game knowledge.
There is an injunction against moving the queen too soon, and random encouragement for the middle pawns to get out immediately. After the first 3, all moves are deterministic, although MSIE and Mozilla diverge in their lines of play - owing, I think, to differing algorithms in Array.sort(). Castling is mindlessly encouraged, in part because checking for it is costly to overall speed.
It assumes you'll be thinking along the same lines, and subtracts the value of your replies from the value of each its moves. That is all it does.
In the end I used a principle variation search, which is an optimized version of alpha-beta. A plain alpha-beta search would probably be more appropriate (smaller) for the final 5K version, because it is only ever looking 3 half-moves ahead. These search algorithms are massively documented on the Web (search for "chess programming"), and are only a few lines of code.
I followed the semi-apologetic premise that there is no longer any point making chess programs play well - that has been proven - the challenge now is to make them play interestingly, and sometimes to lose to their audience. Making computers play perfect chess would be like making them play perfect Pacman - the ghosts would just get you - but who would enjoy that?
WR: How does it rank as a chess player?
DB: There has been some talk about this on the comments page (https://www.the5k.org/description.asp/entry_id=719). People are guessing 1000-1200. I don't really know how those numbers work, but I know the game is not really very good. It fools people into simultaneously underestimating it (because it's just a web page) and overestimating it, attributing plans and conceptual ability where none exist. Its speed is another trap. By not taking long over any move, it encourages people to also move fast. While the computer can't possibly miss the best move according to its limited view, people make huge oversights when they're playing quickly - especially people who don't often play chess and just happened across it. It tends to be very brash, which might put people off if they're used to playing properly. If you have played much chess, you can beat it by slowing down, watching your defense and waiting for it to crumble.
WR: How did you create those graphics?
They're 5x8 GIFs, blown up to 25x40 in the HTML. 5x8 was the smallest size I could found that allowed good shapes. They add up to 679 bytes, which could've been a bit less without the horses' eyes or bishops' crosses. The board is just a table of blank GIFs, and moves are by src swapping. The 5K version would probably work in Netscape 3, but for the use of array literals (z=[] vs z=new Array). That's how un-DHTML it is.
WR: If you had 10K, what else would you do?
DB: I have a ~6K version with multiple levels, undo, a swap sides button, game record, and sliding pieces that stick to your mouse while you're moving them. People can see that at https://halo.gen.nz/chess/6k/x.html There might be bugs though.
Beyond that, I think I'd focus on speeding up the parsing routine, moving more of the calculations out of the inner loop into look-up tables constructed at the beginning of the game or move. For instance, there could be a 64 position array of the knight and king moves from each square, rather than calculating these afresh several hundred times per move. This shouldn't add many bytes at all.
Another improvement may lie in having the computer remember its results, so it doesn't repeat itself if two branches of the tree merge, or if the expected line of play is followed. I don't know though - these things might confuse me beyond their value.
I might also fiddle with its evaluation heuristic. I've paid very little attention to this - so long as it has been making decisions I've been happy to leave it. Real chess programs look after stuff like pawn structure, possibly at a speed cost.
I'd modify it to work in Netscape 3, whose JavaScript flies.
Then to fill out the 10k, I'd add in a draughts/checkers game.
A more intriguing question would be whether I could reduce it to 4K or less, by removing some speed optimizations and perhaps slightly de-structuring the code.
Ultimately the restriction is as much of time as of bytes.
WR: How suited is JavaScript to this kind of thing?
DB: It's alright, if you accept the pace. Rather than using slow objects, I stored attributes for each piece as bits in an integer. As a result, most of the program consists of the simple operations (AND, OR, shift, add, XOR, etc) you'd find in assembly language. These all take the same time - essentially JavaScript's minimum execution unit. I did a lot of testing, but mostly forgot the results.
Array sorting is really slow and, annoyingly, defaults to lexical sort. That means if you're sorting integers, they all get converted into strings, then get sorted alphabetically (so "11" comes before "2"), before being returned to integer form. To get them to sort properly, you can add a large number to each integer (e.g., 10000+11 becomes "10011" which comes after 10000+2 or "10002"), or you can provide your own JavaScript comparison function, which gets run umpteen times in place of the native lexical comparison. The first method was quicker in MSIE, but incredibly slow in the Mozilla of that time. So I went with the comparison. JavaScript (especially JScript) arrays are fairly miserable cousins of their equivalents in other scripting languages.
The most infuriating feature is the "Scripts are making this page slow" message, which occurs if the search is set too deep. The chess game could be much cleverer if browsers would just let it spend 10 or 20 seconds looking a level deeper.
WR: Tell us about yourself and what you do?
DB: I'm 31, live in Porirua, New Zealand, and work part-time for a web company (https://katipo.co.nz/) as a programmer/developer, but my life is really more focused on arts than IT. I was an experimental filmmaker for several years, and I still do that a bit. I'm quite fascinated by simple computer games, and am trying to find my way in the programming medium. Chess - and my 2000 entry - are practice for that, but not quite meeting the artistic level I'm aiming for. The computer is a medium exceeding everything since writing in importance, and the game is the natural expression of it, but nobody (including myself) quite knows what to do with it. So I'm just copying the classics for now. I don't play large commercial games, in case I never emerge. I hardly ever play chess, preferring go, an oriental game of great complexity. I can be reached at: [email protected].
https://www.the5k.org/description.asp/entry_id=719 - 5K chess entry https://halo.gen.nz/chess/6k/x.html - 6K chess version
/-------------------------------------------------------------------\ The definitive event for online marketers hits San Jose August 12-14. Register today and you'll learn from world renowned search engine expert Danny Sullivan. By attending you'll gain an understanding how search engines work and how to leverage their power! It features presentations and panel discussions that cover all aspects of search engine-related promotion. You'll learn how search engines interact with your Web site & ways to improve your listings. https://www.intmediaevents.com/sew/summer02
\--------------------------------------------------------------adv.-/
That's it for this Wednesday, see you next week.
Andrew King Newsletter Editor, WebReference.com aking at internet dot com
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
DEDICATED EMAIL LIST SERVERS! Get the speed, control, and responsiveness you need for your out-sourced Email Newsletters at an AFFORDABLE price! 100% UPTIME GUARANTEED! Sign-up by July 15th and the set-up is FREE for your DEDICATED solution just for mentioning this ad. Free Quote: mailto:[email protected] or surf the website: https://SparkLIST.com/ or direct: 920.490.5901, x1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Advertising: If you are interested in advertising in our newsletters, call Claudia at 1-203-662-2863 or send email to mailto:[email protected] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ For contact information on sales offices worldwide visit https://www.internet.com/mediakit/salescontacts.html ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ For details on becoming a Commerce Partner, contact David Arganbright on 1-203-662-2858 or mailto:[email protected] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ To learn about other free newsletters offered by internet.com or to change your subscription visit https://e-newsletters.internet.com ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ internet.com's network of more than 160 Web sites is organized into 16 channels: Internet Technology https://internet.com/it E-Commerce/Marketing https://internet.com/marketing Web Developer https://internet.com/webdev Windows Internet Technology https://internet.com/win Linux/Open Source https://internet.com/linux Internet Resources https://internet.com/resources ISP Resources https://internet.com/isp Internet Lists https://internet.com/lists Download https://internet.com/downloads International https://internet.com/international Internet News https://internet.com/news Internet Investing https://internet.com/stocks ASP Resources https://internet.com/asp Wireless Internet https://internet.com/wireless Career Resources https://internet.com/careers EarthWeb https://www.earthweb.com ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ To find an answer - https://search.internet.com ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Looking for a job? Filling an opening? - https://jobs.internet.com ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This newsletter is published by Jupitermedia Corp https://internet.com - The Internet & IT Network Copyright (c) 2002 Jupitermedia Corp. All rights reserved. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ For information on reprinting or linking to internet.com content: https://internet.com/corporate/permissions.html ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Find a programming school near you