Slashdot Mirror

Mod parent up +1 informative;

Copying is the sincerest form of flattery. So let me get this straight: 18 years later someone figures out how his 1984 game works and he throws a hissy fit; Braben sounds like a dick. ( http://www.christianpinder.com/games/ )

Thank god for Linus' quote: "Only wimps use tape backup: real men just upload their important stuff on ftp, and let the rest of the world mirror it ;)"

i.e.
http://www.gtoal.com/athome/tailgunner/java/elite/elite-the_new_kind-1.0/

You may joke but when you do static binary translation, finding the COMEFROM's by hand is very time consuming.

http://www.gtoal.com/sbt/
Well, we need to know the flow control of the program and note the destinations of jumps. Those jump destinations are the only opcodes which need to be labelled. To some extent you might be able to work those out statically, by having a slightly smarter disassembler framework which does a tree-walk of the source, starting at the entry point. I.e. whenever it hits a branch or subroutine call, it also goes off to the destination and looks at the code there too. The problem with this is that very few architectures are designed so that you always can determine the jump destination just by looking at the code. Most architectures allow indirect jumps through store or registers, or let you tweak a return address on the stack so that your return from subroutine goes somewhere other than where your subroutine was called from. This is a major pain in the ass and the only practical solution is to profile the execution of the code and mark the jump destinations at run time.

In fact if I were designing a JITable VM, I would definitely have a list of possible jump destinations in the executable format.

You may joke but when you do static binary translation, finding the COMEFROM's by hand is very time consuming.

http://www.gtoal.com/sbt/
Well, we need to know the flow control of the program and note the destinations of jumps. Those jump destinations are the only opcodes which need to be labelled. To some extent you might be able to work those out statically, by having a slightly smarter disassembler framework which does a tree-walk of the source, starting at the entry point. I.e. whenever it hits a branch or subroutine call, it also goes off to the destination and looks at the code there too. The problem with this is that very few architectures are designed so that you always can determine the jump destination just by looking at the code. Most architectures allow indirect jumps through store or registers, or let you tweak a return address on the stack so that your return from subroutine goes somewhere other than where your subroutine was called from. This is a major pain in the ass and the only practical solution is to profile the execution of the code and mark the jump destinations at run time.

In fact if I were designing a JITable VM, I would definitely have a list of possible jump destinations in the executable format.

Sorry to disappoint, folks: the 10-squares in the file you mention above were not discovered by my program - in fact there's a very small word list also in that directory ( http://www.gtoal.com/wordgames/wordsquare/update.1 0.txt ) which contained words known to make 10-squares, which I was using as a Q.A. check for my code. (Hence the filename 'benchmark')

The square mentioned in the Times was discovered quite a few years ago, as you mentioned - however it was indeed discovered by Ted, who is a likeable is somewhat eccentric old buffer with a monomania for word squares.

What you may find interesting is the work we've done since on multi-lingual tensquares - see if you can find any of the articles by Rex Gooch or Ross Eckler. (eg http://findarticles.com/p/articles/mi_hb346/is_200 408/ai_n5540701 )

The privately-produced magazine Wordways has published the more interesting work on the subject.

It's not especially interesting from the computer science point of view, although the size of the problem at 10 or 11 does make it something worth doing on a large distributed system.

Best regards

Graha Toal

And the 10-word squares can be found at http://www.gtoal.com/wordgames/wordsquare/BENCHMAR K

The probable solve:

discu ssing
incan tator
scarl atina
carni tines
unlik eness

state swren
satin weave
itine rates
nones event
grass nests

What's up with slashdots lameness filter? The solution is lame now?

DISCUSSING
INCANTATOR
SCARLATINA
CARNITINES
UN LIKENESS
STATESWREN
SATINWEAVE
ITINERATES
NONE SEVENT
GRASSNESTS
</tt>

There are two others mentioned, one of which contains the word "Orangutang", which is also mentioned in the Times article. Interestingly, this directory listing implies that the BENCHMARK file, which contains the above solution, was created no later than November 1999. Sorry - but I can't stop the ecode tage from inserting spaces into the text.

Apple wrote a great 68K emulator for the PowerPC macs. It was non JIT, and worked like a big jump table. So you took a 16bit 68k instruction, shifted it and jumped to the base of the table + the shifted offset. The code there would essentially be a PowerPC version of the 68K code.

http://www.mactech.com/articles/mactech/Vol.10/10. 09/Emulation/

So you end up doing four instructions to decode the 68K instruction, and then whatever it takes to actually do the operation, typically 2-4.

JIT emulators would profile the code and check which bits were frequently executed. Then they would essentially copy the table entries into a buffer. So in a loop, you'd actually execute native just execute the 2-4 native instructions and skip the table dispatch.
There's another benefit too, you can skip things like condition code updates, if you know that they will be overwritten by another instruction before they are checked. Plus you can do peephole optimisations, constant folding and so on.

There's a wonderful article here -

http://www.gtoal.com/sbt/

I can easily believe that CPU intensive code like image processing can run at a very impressive speed, especially as top of the range x86 chips have better SpecInt perormance than a top of the range PPC.

Incidentally, I read about Apple's second generation 68K emulator being a "dynamic recompiler", so they've been working on this sort of thing for ages.

There's a very clever method of optimising the repeated valid placement calculations, due to Jacobson and Appel, where each square is tagged with the set of valid crossing letters that can be played on it. For example, if your board looked like:

1.2.3
A.N.D
L.O.O
E.W.E

where 1 2 and 3 were empty squares, 1 would be tagged with {bdeghkmprstvwy}, 2 with {aeks} and 3 with {}, so that a word played horizontally would be constrained to have only those letters in the tagged squares. (SOWPODS lexicon)

Combined with this is a refinement of the DAWG called a DAGGAD - in the author's words:

A practical variation is the DAWG for the language L = {REV(x)*y | xy is a word and x is not empty}, where * is just a delimiter. Each word in the lexicon can be generated starting from each letter in that word by placing tiles leftward
upon the board starting at an anchor square while traversing the corresponding arcs in the structure until encountering the *, and then placing tiles rightward from square to the right of the anchor square while still traversing corresponding arcs until acceptance. Being the reverse of the directed acyclic graph for prefixes followed by the directed acyclic graph for suffixes, I called it a GADDAG.

So for example, the word SPACE would be stored as SPACE, PACE*S, ACE*PS, CE*APS and E*CAPS, so that you could search the tree starting from the A, play C in the next square, E next, then jump back to the A, move back a square and play P, then back another square and play S. After the trie compaction, a DAGGAD takes up ~3-5 times the space of the corresponding DAWG, and roughly doubles the search speed.

Check out Graham Toal's wordgame programming page for lots more on scrabble algorithms.

There's a very clever method of optimising the repeated valid placement calculations, due to Jacobson and Appel, where each square is tagged with the set of valid crossing letters that can be played on it. For example, if your board looked like:

1.2.3
A.N.D
L.O.O
E.W.E

where 1 2 and 3 were empty squares, 1 would be tagged with {bdeghkmprstvwy}, 2 with {aeks} and 3 with {}, so that a word played horizontally would be constrained to have only those letters in the tagged squares. (SOWPODS lexicon)

Combined with this is a refinement of the DAWG called a DAGGAD - in the author's words:

A practical variation is the DAWG for the language L = {REV(x)*y | xy is a word and x is not empty}, where * is just a delimiter. Each word in the lexicon can be generated starting from each letter in that word by placing tiles leftward
upon the board starting at an anchor square while traversing the corresponding arcs in the structure until encountering the *, and then placing tiles rightward from square to the right of the anchor square while still traversing corresponding arcs until acceptance. Being the reverse of the directed acyclic graph for prefixes followed by the directed acyclic graph for suffixes, I called it a GADDAG.

So for example, the word SPACE would be stored as SPACE, PACE*S, ACE*PS, CE*APS and E*CAPS, so that you could search the tree starting from the A, play C in the next square, E next, then jump back to the A, move back a square and play P, then back another square and play S. After the trie compaction, a DAGGAD takes up ~3-5 times the space of the corresponding DAWG, and roughly doubles the search speed.

Check out Graham Toal's wordgame programming page for lots more on scrabble algorithms.

two:

quixotic

In fact, quixotic implements a more complex datastructure than a DAWG, called a GADDAG which allows exceedingly fast word building, starting in the middle of the word. This means that if you also have a list of all the anchor squares -- those squares where playing a tile automatically makes a syntactically valid play -- you can generate all possible plays given a rack without ever generating an illegal play.

My 800MHz powerbook finds moves fast enough that it's feasible to do a couple of plys of a form of speculative minmax in order to evaluate the worth of particular board positions.

This article was interesting but short on technical detail. Here are some other links on static recompilation:

http://www.gtoal.com/sbt/
http://groups.yahoo.com/group/staticrecompilers/

It is unclear to me how they deal with more complex situations such as self-modifying code or code that jumps into the middle of an instruction.