Forty five years ago

[bob]

The machine Kotov used for development was an IBM 7090, first released in 1960. It was the transistorized revision of the earlier and quite popular IBM 709, a vacuum tube machine. Computer time on a 7090 was available at the rate of about US$100 per hour.

A picture: http://www.cozx.com/~dpitts/pix/ibm7090.jpg

The machine's clock rate was about 480 KHz and it had 32,768 word memory of 36 bit words. Kotov could have programmed a bitboard program, but instead he inherited an offset style move generator and used that. (In all, there were seven people who contributed to the program's source.)

That clock rate is misleading. An IBM 360/40 executed about 100K instructions per second and it was _way_ faster than a 7090-series machine... I think the 7090 could do real math-type instructions at maybe 30K per second (multiply/divide). I worked on one for a couple of years. I seem to remember some horrible memory access time (and memory was _not_ very big) of 2usec or more... I have some old manuals around here somewhere and will try to dig up real numbers... but compared to anything of the last 20 years it was just a dog.

[sje]

For basic integer operations the 7090 was fairly quick and the overall processing speed was fast enough for Samuel's checker player. A revision towards the end of its production added an extra four index registers to the default three and so the code became a bit more compact after that.

The AI Gang at MIT executed various hardware hacks on their 7090 including adding a second bank of 32 KW memory along with a real time video input digitizer. In some ways, the state of the hardware was far in advance of the level of software engineering. But that's probably true today as well.

[sje]

Five years after the Kotov report, there's another chess report in the MIT AI memo series: Greenblatt's program MacHack:

ftp://publications.ai.mit.edu/ai-public ... IM-174.pdf

[Carey]

Five years after the Kotov report, there's another chess report in the MIT AI memo series: Greenblatt's program MacHack:

ftp://publications.ai.mit.edu/ai-public ... IM-174.pdf

Yup. That's also listed on my site.

Greenblatt also published a few other memos about MacHack VI, including his later use of CHEOPS hardware. But I don't have a copy of those.

Nor do I have a copy of the source for MacHack VI. I never could get hold of Mr. Greenblatt to ask about it, although from what I hear, the ComputerHistory.org people have been trying for quite a while to talk him into checking for a copy, but he's resisted.

I do have a couple of hacked binaries linked to on my site, but that's all.

[sje]

A while back I prowled through the DECUS (Digital Equipment Corporation User Group) archives and found a binary, at least semi-official in status, of MacHack. I was able to scan all the strings in the executable, but I didn't have a reverse assembler to read the actual code.

MacHack was different from most programs since then as its evaluation was strongly path dependent. As I understand it, the plausibility selection heuristics were also used to score the position. Quite a time saver in spite of some drawbacks.

The old style Shannon Type B programs actually did fairly well. If there was something obvious to do in a position, the program usually found the right move fairly quickly. The big problem was when a non obvious move was needed. The answer according to Paradise (and eventually also to Symbolic) is that a good plausible move needs to be generated as part of a plausible plan, and the generation of such a plan needs efficient and elaborate pattern recognition along with a big plan library.

[Carey]

A while back I prowled through the DECUS (Digital Equipment Corporation User Group) archives and found a binary, at least semi-official in status, of MacHack. I was able to scan all the strings in the executable, but I didn't have a reverse assembler to read the actual code.

Yeah, those are the binaries for MacHack that I'm talking about.

It's uncertain what kind of modifications / hacks were actually done, so it would have been nice to have a copy directly from Mr. Greenblatt.

I don't even have a contact address for Greenblatt, so I can't ask directly. But as I said, from what I gather, the ComputerHistory.org people have been trying a couple years to get him to look for an original copy and he's resisted. If he's not willing to do it for them, there's no chance that he'd do it for me.

MacHack was different from most programs since then as its evaluation was strongly path dependent. As I understand it, the plausibility selection heuristics were also used to score the position. Quite a time saver in spite of some drawbacks.

The old style Shannon Type B programs actually did fairly well. If there was something obvious to do in a position, the program usually found the right move fairly quickly. The big problem was when a non obvious move was needed. The answer according to Paradise (and eventually also to Symbolic) is that a good plausible move needs to be generated as part of a plausible plan, and the generation of such a plan needs efficient and elaborate pattern recognition along with a big plan library.

I'd guess that CHAOS was probably the best real selective search program around, and even they moved away from pure to hybrid.

The Slate / Atkin / Gorlen Chess 3.6 was abandoned in favor of pure brute force.

I don't really know how well the classic selective search programs (CHAOS & AWIT) would run on modern hardware. It'd be interesting to find out, though.


Development of plans is a bit outside of my discussion ability, other than to say that I don't know of any program that was actually sucessful with making 'plans'.

[sje]

The old style Type B selective search proponents did have two good motivations: psychological realism (or at least mimicry) and time savings. But a quick, single ply plausibility analysis isn't sufficient, and most Type B programs weren't even doing that; they were just using a static evaluator and picking the first N moves by rank.

And honestly speaking, a traditional A/B searcher with many different extensions and reductions isn't all that much different from an old style Type B program except that it has selective depth instead of width. In both cases there's a collection of rather simple (but fast) heuristics that determine which moves (or positions) are worthy of further analysis. Importantly, in both cases the search tree is used for only one purpose: discovery.

Using a tree only for discovery makes for a big difference with nearly every other search in AI; most of these are goal oriented and the state space search is chock full of interesting techniques for locating the goal. Goal oriented searchers know in advance what they're seeking and are fairly smart with adding nodes to the tree (or other kind of graph), almost human like in fashion.

Plans and patterns programs use a search tree, but are similar to goal searchers in the sense that the tree is used not so much for discovery, but for verification. The program has some kind of idea about what it's looking for, and uses this information to decide which nodes to create.

Paradise used a search tree strictly for verification purposes. It did planning via pattern recognition, and it did this only at the root node and at nodes where a goal in a root plan needed further elaboration of a terminal goal. Multiple plans at a node were ranked according to forcing likelihood and then by material gain. If the first plan at a node worked well enough, any secondary plans were skipped.

Like Paradise, Symbolic uses a search tree for verification in the sense that it will never create a node unless there is an explicit reason to do so. The program will always have some idea or plan in mind and will be able to measure the local search result against the originating reason for the node creation for a progress check. Like Paradise, Symbolic may visit the same node more than once, but with a different plan each time. Unlike Paradise, Symbolic is not restricted to a sequence depth first searches, and so has much more freedom to hop around the tree and retrying earlier plans with extra effort as time allows.

[Aleks Peshkov]

The same article, but readable version:
http://www.kotok.org/AI_Memo_41.html

[sje]

I wonder what papers or programs being written today will be of any interest four or five decades from now.

Will there even be any chess programmers in the second half of this century? Maybe people will switch to go.

--------

In my files I have some notes and code for "pot-chess" (power of two chess) where the board and men of regular chess are scaled up in size and number by integral powers of two. Example: pot-chess 8 is played on a 256 by 256 board with (at least) 512 men per side. Some rules are changed to make it easier to program: no pawns, no castling, any new piece types move symmetrically, etc. One motivating idea is to make the move choice state space arbitrarily large to evade simplistic treatment using traditional A/B techniques.

Some experiments so far show that pot-chess 6 is about as large as it can get and still have the board be legible on a typical monitor.

Pawns are replaced with single step infantry pieces evenly divided over four kinds: orthogonal steppers, diagonal steppers (both colors), and eight way steppers (i.e., like a king). Borrowing some near conventional piece types from heterodox chess (e.g., combining knight moves with non knight men) adds a bit of flavor.

I should probably write this up along with a notation and interface specification and maybe a few adventurous coders might get interested.

[Aleks Peshkov]

I wonder what papers or programs being written today will be of any interest four or five decades from now.

IMHO selective search was forbidden between centuries. Computers goes quicker and quicker but frontier nodes costs relatively more and more.