🚀 go-pugleaf

In article <1990Aug30.1...@nmt.edu> dbr...@nrao.edu (Daniel Briggs)
writes about the difficulty of writing a Go-playing program.

I quote from HAKMEM (MIT AI MEMO 239, February 29, 2972). The section
about "Proposed computer programs, in order of increasing running time
(Schroeppel)". The section begins with Problem 77, and ends with:

    PROBLEM 93: Solve checkers. There are about 10 ** 12 positions.
    (Computing time currently estimated (Scroeppel) at 1 year).

    Programs below this line are considered unfeasible.

    PROBLEM 94: Solve Hex on large boards (11 to 23 an a side);
    though order 7 have been analyzed by hand. There is a
    proof that in games where having an extra move can never
    (repeat: never) hurt you, the worst the first player can
    be forced to is a draw. Thus, with Hex, in which there
    is no draw, the first player can aways win.

    PROBLEM 95: Solve chess. There are about 10 ** 40 possible
    positions; in most of them, one side is hopelessly lost.

    PROBLEM 96: Solve Go. About 10 ** 170 positions.

Good luck, and happy hacking!


-- 
Per Lindberg (The Mad Programmer)   !      __!__
Front Capital Systems, Box 5727,    !  _____(_)_____  Ceci n'est pas une Piper
11487 Stockholm, Sweden. 8-6611510  !     !  !  !

 In article <1990Aug30.1...@nmt.edu> dbr...@nrao.edu (Daniel Briggs)
> writes about the difficulty of writing a Go-playing program.
	Cross-posting to rec.games.go might have some value.
	I know GNUGO is out there.  On a recent plane trip, the guy
	sitting behind me turned out to be a fellow Cornellian
	heading out to Boulder for a Go tournament; he was of the
	opinion that, while computer go was improving, it was still
	nowhere near human abilities, and tended to play random and
	ugly-looking games.  (I'm in no position to say; I stopped
	playing at about 25 kyu, and commented at a recent Usenix
	computer go tournament that one of the contestants obviously
	passed the Turing test - it was playing as badly as I would :-)
 
In article <15...@front.se>, p...@front.se (Per Lindberg) writes:
> I quote from HAKMEM (MIT AI MEMO 239, February 29, 2972). The section

Does anyone know if HAKMEM is available on-line?  I had a copy a few
years back; there were a number of interesting mathematical and
algorithm-related problems, some insight into the state of the art
back then, and (unfortunately) a lot of what purported to be
interesting algorithms written in highly legible PDP-10 assembler.
ARRRGH - as with Knuth, why can't people use ALGOL instead of
preferring low-level languages?  Admittedly, some of the algorithms
were really concerned with "how to make a 36-bit machine do
something useful?"

				Bill
-- 
					Thanks; Bill
# Bill Stewart 908-949-0705 erebus.att.com!wcs AT&T Bell Labs 4M-312 Holmdel NJ

# There'll be a brand new war coming soon to a theatre near you - promise!

In article <1990Sep3.0...@cbnewsh.att.com> w...@cbnewsh.att.com (Bill Stewart 201-949-0705 erebus.att.com!wcs) writes:

>Does anyone know if HAKMEM is available on-line? ...

My copy contains a lot of schematics and graphics and such stuff, so
while there might exist a typed-in version somewhere, the original
wasn't. You might try MIT, they probably have some paper
library/distribution service.

>...interesting algorithms written in highly legible PDP-10 assembler.
>ARRRGH - as with Knuth, why can't people use ALGOL instead of
>preferring low-level languages?  Admittedly, some of the algorithms
>were really concerned with "how to make a 36-bit machine do
>something useful?"

Yes and no. Some of the really beautiful hax in HAKMEM are some
highly bummed (few instructions, who cares about readability) code
pieces in PDP-10 machine code. Love the machine for itself.

-- 
Per Lindberg (The Mad Programmer)   !      __!__
Front Capital Systems, Box 5727,    !  _____(_)_____  Ceci n'est pas une Piper
11487 Stockholm, Sweden. 8-6611510  !     !  !  !

In article <1990Sep3.0...@cbnewsh.att.com> w...@cbnewsh.att.com (Bill Stewart 201-949-0705 erebus.att.com!wcs) writes:
>Does anyone know if HAKMEM is available on-line?
Not a chance.  An attempt was made about 10-12 years ago to create an
online version but it got abandoned.

>(unfortunately) a lot of what purported to be
>interesting algorithms written in highly legible PDP-10 assembler.

Yes, indeed, the assembler was highly legible.  It was, without a
doubt, the easiest assembly language to read and understand; a true
delight to program in.  This was one of the reasons migration from the
PDP-10 was so painful; there was *much* more programmed in assembly
language for that machine than for just about any other platform.

Now, what the algorithms *did* was rather obscure, and no programming
language could clarify it further.  At least the assembly language was
precise and unambiguous, unlike certain programming languages.

>ARRRGH - as with Knuth, why can't people use ALGOL instead of
>preferring low-level languages?

Such as which bogus dialect of ALGOL was in vogue at the time?  I can
show you lots of "ALGOL" which is totally unintelligible today, as it
depends upon long-forgotten side-effects or even (shudder!) obsolete
evaluation-order rules...

If written in anything other than PDP-10 assembly language, it would
have been in Lisp.  HAKMEM was an internal document for the MIT AI
Lab.  At the time, they used two programming languages; assembly (for
the systems hackers) and Lisp (for the AI work).

>Admittedly, some of the algorithms
>were really concerned with "how to make a 36-bit machine do
>something useful?"

36-bit machines did quite a bit useful without obscure algorithms.
True, most of the assembly algorithms had to do with exploiting subtle
mathematical relations with surprising results, or would be irrelevant
on other architectures, but in almost all cases the bizarre hack was
more of an intellectual exercise rather than anything useful.

For example, on the PDP-10 a common vector pointer had a negative
length count in the left 18-bit halfword and a positive index in the
right halfword (indexing only used the right halfword in the
traditional address space); this was incremented, tested, and iterated
by the AOBJN (Add One to Both halfwords and Jump if Negative)
instruction.  One HAKMEM hack to load an AOBJN pointer was:

	HRLOI AC,-1(COUNT)	; Halfword Right to Left Immediate, fill Ones
	EQVI AC,ADDR		; EQuiValence Immediate

where AC is a register to receive the pointer, COUNT is a register
containing the positive size of the vector, and ADDR is a constant
address of the origin of the vector.

The calculation of the indexed immediate value results in 9 (I'm
keeping this decimal).  The "right half" of an immediate value is that
value; this goes into the left half of AC.  Ones go into the right
half of AC (the "O" of "HRLOI"), resulting in 9,,-1.  The EQV is a
logical equivalence test, returning bitwise 1's for equivality and 0's
for inequality.  The left half of an immediate value is always zero,
so the equivalence complements the 9.  On a twos complement machine,
the complement of 9 is -10; this goes into the left half.  Since the
right half of AC is -1, equivalence is an identity operation; so the
immediate value goes into the left half.  Result: -10,,ADDR.

This can, of course, be done in a much more straightforward manner
with the series:
	MOVN AC,COUNT		; MOVe Negative
	HRL AC,AC		; Halfword Right to Left
	HRRI AC,ADDR		; Halfword Right to Right Immediate
but of course this lacks the wonderful obscurity (and is one machine
instruction longer!) of the HAKMEM example.  A single machine
instruction was rarely important, even in the (by today's standards)
limited address space on a PDP-10.

Thus is the way of all good hacks.

 _____   | ____ ___|___   /__ Mark ("Gaijin") Crispin  "Gaijin! Gaijin!"
 _|_|_  -|- ||   __|__   /  / R90/6 pilot, DoD #0105   "Gaijin ha doko?"
|_|_|_|  |\-++-  |===|  /  /  Atheist & Proud          "Niichan ha gaijin."
 --|--  /| ||||  |___|    /\  (206) 842-2385/543-5762  "Chigau.  Gaijin ja nai.
  /|\    | |/\| _______  /  \ M...@CAC.Washington.EDU    Omae ha gaijin darou"
 / | \   | |__|  /   \  /    \"Iie, boku ha nihonjin." "Souka. Yappari gaijin!"
Hee, dakedo UNIX nanka wo tsukatte, umaku ikanaku temo shiranai yo.

In article <70...@milton.u.washington.edu> m...@Tomobiki-Cho.CAC.Washington.EDU (Mark Crispin) writes:
>In article <1990Sep3.0...@cbnewsh.att.com> w...@cbnewsh.att.com (Bill Stewart 201-949-0705 erebus.att.com!wcs) writes:
>
>	HRLOI AC,-1(COUNT)	; Halfword Right to Left Immediate, fill Ones
>	EQVI AC,ADDR		; EQuiValence Immediate
>
>right half of AC is -1, equivalence is an identity operation; so the
>immediate value goes into the left half.  Result: -10,,ADDR.
>
		 or

>	MOVN AC,COUNT		; MOVe Negative
>	HRL AC,AC		; Halfword Right to Left
>	HRRI AC,ADDR		; Halfword Right to Right Immediate


Why make things so compilcated. Why not simply

	MOVE AC,[-COUNT,,ADDR]	; Load ac with ....


Ho hum.











 
------------------------------------------------------------------
|  Mail:    1830 22nd street      Email: a...@boulder.colorado.edu|
|           Apt 16                Vmail: Home:   (303) 939-8256  |
|           Boulder, Co 80302            Office: (303) 492-8115  |
------------------------------------------------------------------

In article <25...@boulder.Colorado.EDU> a...@boulder.Colorado.EDU (Alan T. Krantz) writes:
>In article <70...@milton.u.washington.edu> m...@Tomobiki-Cho.CAC.Washington.EDU (Mark Crispin) writes:
>>In article <1990Sep3.0...@cbnewsh.att.com> w...@cbnewsh.att.com (Bill Stewart 201-949-0705 erebus.att.com!wcs) writes:
>>	HRLOI AC,-1(COUNT)	; Halfword Right to Left Immediate, fill Ones
>>	EQVI AC,ADDR		; EQuiValence Immediate
>		 or
>>	MOVN AC,COUNT		; MOVe Negative
>>	HRL AC,AC		; Halfword Right to Left
>>	HRRI AC,ADDR		; Halfword Right to Right Immediate
>Why make things so compilcated. Why not simply
>	MOVE AC,[-COUNT,,ADDR]	; Load ac with ....

How soon we forget!

The MOVE would be fine if COUNT was an immediate value (a compile-time
constant), but in my examples, it's the name of a register.  The whole
point is that if you don't know the szi6xxxx"b3 e of the vector (or the address
of the vector) at compile time, you cannot do a simple move from a
constant.

ADDR could also be a register (or memory location) by changing the
EQVI to EQV or the HRRI to HRR in the above examples.

If you want another shot, here's a "simple" one.  Put a PUSH in
register 0, and start the CPU at 0.  What happens?  No fair trying it
on a real PDP-10.  You can assume the CPU is a bare machine, but this
will work OK under timesharing on Tenex, TOPS-20, or ITS systems.

 _____   | ____ ___|___   /__ Mark ("Gaijin") Crispin  "Gaijin! Gaijin!"
 _|_|_  -|- ||   __|__   /  / R90/6 pilot, DoD #0105   "Gaijin ha doko?"
|_|_|_|  |\-++-  |===|  /  /  Atheist & Proud          "Niichan ha gaijin."
 --|--  /| ||||  |___|    /\  (206) 842-2385/543-5762  "Chigau.  Gaijin ja nai.
  /|\    | |/\| _______  /  \ M...@CAC.Washington.EDU    Omae ha gaijin darou"
 / | \   | |__|  /   \  /    \"Iie, boku ha nihonjin." "Souka. Yappari gaijin!"
Hee, dakedo UNIX nanka wo tsukatte, umaku ikanaku temo shiranai yo.

>
>If you want another shot, here's a "simple" one.  Put a PUSH in
>register 0, and start the CPU at 0.  What happens?  No fair trying it
>on a real PDP-10.  You can assume the CPU is a bare machine, but this
>will work OK under timesharing on Tenex, TOPS-20, or ITS systems.


That's an easy one - if I understand the question correctly. The Dec-10
(tops-10) had a linear address space (including the registers) so if the
pc was 0 - it executed the data in register 0 as an instruction. The
only catch is that there are a few addresses in the job data area
(something like 20-134) that you shouldn't mess with. Of course one
common falicy I made a couple of times was:

	move	reg,x(0)


Going back to your original posting - bleh. No actually I liked PDP-10
assembly language a lot. A lot more then 8088/68000 - and I liked DDT
a whole lot more than dbx.... Ho hum. 

This is a simple trivia question - but what does the following code do:

	move	1,[movei 1,@1]
	jrst	1

....




 
------------------------------------------------------------------
|  Mail:    1830 22nd street      Email: a...@boulder.colorado.edu|
|           Apt 16                Vmail: Home:   (303) 939-8256  |
|           Boulder, Co 80302            Office: (303) 492-8115  |
------------------------------------------------------------------

In article <25...@boulder.Colorado.EDU> a...@boulder.Colorado.EDU (Alan T. Krantz) writes:
>>If you want another shot, here's a "simple" one.  Put a PUSH in
>>register 0, and start the CPU at 0.  What happens?
>
>That's an easy one - if I understand the question correctly.

If so, then solve it.  I specifically stated that it was either a bare
machine or a user program on an operating system with no funny OS
stuff in the address space (such as TOPS-10 JOBDAT).  Under Tenex or
TOPS-20, the only special address space location was the LUUO handler
at location 40 and 41.

>This is a simple trivia question - but what does the following code do:
>
>	move	1,[movei 1,@1]
>	jrst	1

After executing the JRST (an absolute jump to a memory location, in
this case register 1), the processor will hang in an indirect address
loop trying to resolve @1 until such time as it is stopped or an
interrupt occurs.  @X says "take the contents of memory location X and
do a new address calculation on it."  Since the address calculation
can involve a new indirect (you could chain indirects on a PDP-10),
you have a circular chain.  The MOVEI is never executed since an
address calculation is always resolved first before any instruction
decoding or execution.  The effect would have been the same if you had
stored an invalid op-code instead of a MOVEI.

Once, a professor (who shall remain nameless) insisted that the PDP-10
at Stevens Institute of Technology was broken, and demanded that it be
repaired.  For some bizarre reason, he had a program which had an
indirect address chain that was about ten thousand references long.
As the operating system was guaranteed to get a clock interrupt every
1/60 of a second (every 17 microseconds) and the memory was relatively
slow (I think it was 2 millisecond memory), there was no way that the
CPU could resolve the address before the clock ticked.  It did not
store the intermediate results of an address calculation, so when the
program was resumed it would start the calculation from the beginning!

 _____   | ____ ___|___   /__ Mark ("Gaijin") Crispin  "Gaijin! Gaijin!"
 _|_|_  -|- ||   __|__   /  / R90/6 pilot, DoD #0105   "Gaijin ha doko?"
|_|_|_|  |\-++-  |===|  /  /  Atheist & Proud          "Niichan ha gaijin."
 --|--  /| ||||  |___|    /\  (206) 842-2385/543-5762  "Chigau.  Gaijin ja nai.
  /|\    | |/\| _______  /  \ M...@CAC.Washington.EDU    Omae ha gaijin darou"
 / | \   | |__|  /   \  /    \"Iie, boku ha nihonjin." "Souka. Yappari gaijin!"
Hee, dakedo UNIX nanka wo tsukatte, umaku ikanaku temo shiranai yo.

In article <70...@milton.u.washington.edu> m...@Tomobiki-Cho.CAC.Washington.EDU (Mark Crispin) writes:
|In article <1990Sep3.0...@cbnewsh.att.com> w...@cbnewsh.att.com (Bill Stewart 201-949-0705 erebus.att.com!wcs) writes:
|>(unfortunately) a lot of what purported to be
|>interesting algorithms written in highly legible PDP-10 assembler.
|
|Yes, indeed, the assembler was highly legible.  It was, without a
|doubt, the easiest assembly language to read and understand; a true
|delight to program in.  This was one of the reasons migration from the
|PDP-10 was so painful; there was *much* more programmed in assembly
|language for that machine than for just about any other platform.

The language was a little tricky to learn to program with: (1) the available
operations were so rich it was often hard to pick the right one and
(2) it's really surprising to learn that JUMP and SKIP are always
no-ops.  :-)

I agree with everything else you said.

	/JBL
=
Nets: le...@bbn.com  | "How does a mouse let me move the cursor anywhere 
 or {...}!bbn!levin  |  I want?"  "What are address busses?"  "How do 
pots: (617)873-3463  |  icons work?"              --Time-Life Books

In article <25...@boulder.Colorado.EDU> a...@boulder.Colorado.EDU (Alan T. Krantz) writes:
|In article <70...@milton.u.washington.edu> m...@Tomobiki-Cho.CAC.Washington.EDU (Mark Crispin) writes:
|>In article <1990Sep3.0...@cbnewsh.att.com> w...@cbnewsh.att.com (Bill Stewart 201-949-0705 erebus.att.com!wcs) writes:
|>
|>	HRLOI AC,-1(COUNT)	; Halfword Right to Left Immediate, fill Ones
|>	EQVI AC,ADDR		; EQuiValence Immediate
|
|		 or
|
|>	MOVN AC,COUNT		; MOVe Negative
|>	HRL AC,AC		; Halfword Right to Left
|>	HRRI AC,ADDR		; Halfword Right to Right Immediate
|
|Why make things so compilcated. Why not simply
|
|	MOVE AC,[-COUNT,,ADDR]	; Load ac with ....
|Ho hum.

Maybe because COUNT is a variable (an accumulator) holding a computed
value, so it can't be known at assembly time?

Ho ho hum.

	/JBL
=


Nets: le...@bbn.com  | "How does a mouse let me move the cursor anywhere 
 or {...}!bbn!levin  |  I want?"  "What are address busses?"  "How do 
pots: (617)873-3463  |  icons work?"              --Time-Life Books

In article <59...@bbn.BBN.COM> le...@BBN.COM (Joel B Levin) writes:
>[PDP-10 assembly language] was a little tricky to learn to program with:
>(1) the available
>operations were so rich it was often hard to pick the right one and

Fortunately, it rarely mattered which one you picked.  You could have
your own religion on whether 'twas better to do MOVSI or HRLZI [two
instructions that do the exact same thing].

>(2) it's really surprising to learn that JUMP and SKIP are always
>no-ops.  :-)

Ah, a well-beloved feature.  The PDP-10 had gonzo symmetry; JUMP
(branch to memory location based on register comparison with zero) and
SKIP (load register if non-zero with contents of memory location, skip
next instruction based on memory location comparison with zero) were
logical operations which took suffixes indicating under what result of
a comparision with zero the action was to be taken.  Those suffixes
were <blank> (never), A (always), E (equal), LE, GE, L, G, and N (not
equal).

JUMP (jump never) was a true no-op; the later microcoded processors
didn't even do the register comparison.  SKIP, however, was *not* a
no-op.  If the register argument was non-zero, SKIP was equivalent to
a MOVE.  In any case, SKIP always referenced memory, even if the
register argument was zero (register zero was never loaded by an form
of SKIP).  It was therefore the preferred instruction to use to force
a page fault (and possible swap in) of a memory page prior to entering
critical (either time-critical or swap-disallowed) code.  Since the
normal response to a "no map for page" fault (what Unix people would
call "segmentation violation") was to create the page, SKIP could also
be used to create pages in memory and, if mapped to a non-existant
file page, file pages as well!

 _____   | ____ ___|___   /__ Mark ("Gaijin") Crispin  "Gaijin! Gaijin!"
 _|_|_  -|- ||   __|__   /  / R90/6 pilot, DoD #0105   "Gaijin ha doko?"
|_|_|_|  |\-++-  |===|  /  /  Atheist & Proud          "Niichan ha gaijin."
 --|--  /| ||||  |___|    /\  (206) 842-2385/543-5762  "Chigau.  Gaijin ja nai.
  /|\    | |/\| _______  /  \ M...@CAC.Washington.EDU    Omae ha gaijin darou"
 / | \   | |__|  /   \  /    \"Iie, boku ha nihonjin." "Souka. Yappari gaijin!"
Hee, dakedo UNIX nanka wo tsukatte, umaku ikanaku temo shiranai yo.

In article <25...@boulder.Colorado.EDU> a...@boulder.Colorado.EDU (Alan T. Krantz) writes:
>>
>>If you want another shot, here's a "simple" one.  Put a PUSH in
>>register 0, and start the CPU at 0.  What happens?  No fair trying it
>>on a real PDP-10.  You can assume the CPU is a bare machine, but this
>>will work OK under timesharing on Tenex, TOPS-20, or ITS systems.
>
>
>That's an easy one - if I understand the question correctly. The Dec-10
>(tops-10) had a linear address space (including the registers) so if the
>pc was 0 - it executed the data in register 0 as an instruction.

Good - you got the first instruction.  Don't forget the overflow from
the index register field into the indirect bit at pc 17.
>This is a simple trivia question - but what does the following code do:
>
>	move	1,[movei 1,@1]
>	jrst	1

I much preferred:

	movsi	0,20		;That's octal 20 - loads the indirect bit
	jrst	0

Because address evaluation had to be complete before instruction decoding
and PC incrementing, and because the -10 had indefinite indirection, this
would turn off most of the console's lights.  The PC display would be 0,
the instruction display would be off except for the indirect bit glowing
at about half brightness, and the data lights (if the console address switches
were set to 0) would have just the indirect bit.

Pretty dull, actually.  A multiport diagnostic I wrote that beat on memory
from processor, disk (RP02) and drum (RM10B) was really neat with the
computer room lights turned off.


As for alorithms in Algol - if you want that, read CACM.  If you want folklore,
then you may have to deal with assembler.  Besides, how can you cleanly
describe in Algol-60 (sorry, that's the only one I know (knew?)) the rotate
instructions?  Or ILDB/IDPB?  Or TRCE?  Criticizing assembly code when us
old fogies start rhapsodizing about our all-time favorite machine is living
dangerously

As for DDT, I'm please to say that DDT lives!  Thanks to several old PDP-10
hackers at Alliant, our OS debugger is near a relative to PDP-10 DDT.  It's
main shortcoming is the lack of the builtin assembler.  Never did understand
that code on the -10.
-- 

| A pride of lions              | Eric J Werme                   |
| A gaggle of geese             | uucp: mit-eddie!alliant!werme  |
| An odd lot of programmers     | Phone: 508-486-1214            |