From: It's me........
Subject: Chess with LISP or FORTH????
Date: 
Message-ID: <364c738c.10719393@news2.ibm.net>
Hello there,

I recently bought a SPHINX Chess computer (model: Madrid).
It's a VERY strong player, so I wanted to open it to see what kind of
hardware is giving me the frustration of loosing 80% on all games that
I have played with it until now.

Well, quite frustrating:

ONE chip

I really wonder WHAT kind of program language has been used to write
the chess game software.

Some friends of mine told be that it must be FORTH.
But now that I'm interesed in LISP, I wonder if LISP is capable of
playing chess (or checkers...).
Anyone that can tell me something about this??

Thanks for your time to read this msg.

Best regards

Robbert J. van Herksen

From: Tord Kallqvist Romstad
Subject: Re: Chess with LISP or FORTH????
Date: 
Message-ID: <slrn7560jj.22h.romstad@janus.uio.no>
In article <·················@news2.ibm.net>, It's me........ wrote:
>Hello there,
>
>I recently bought a SPHINX Chess computer (model: Madrid).
>It's a VERY strong player, so I wanted to open it to see what kind of
>hardware is giving me the frustration of loosing 80% on all games that
>I have played with it until now.
>
>Well, quite frustrating:
>
>ONE chip
>
>I really wonder WHAT kind of program language has been used to write
>the chess game software.

Most chess programs are written in assembler, C, C++ or some combination
of these languages.  I have never heard of any strong chess program developed
in Lisp or Forth.  I do not know much about your SPHINX program, but if
I recall correctly, it is written by the Dutch programmer Frans Morsch
(who is also author of Fritz, one of the strongest and most popular PC
chess programs today).  Frans always programs in pure, hand-optimized
assembly language.  Speed is very important in computer chess.

By the way, your chess computer is actually very weak compared to the
top PC programs.  If you want an opponent which beats you 99.9% of the
time rather than 80%, there are several very strong freeware programs 
around...

I do not see what advantages Lisp would offer compared to C or assembler
in chess programming.  Anyway, I will probably develop a Lisp chess program
some day, just to find out what speed I can achive using this language...

Tord
From: Steve Gonedes
Subject: Re: Chess with LISP or FORTH????
Date: 
Message-ID: <m2r9v04wf5.fsf@KludgeUnix.com>
·······@janus.uio.no (Tord Kallqvist Romstad) writes:

< I do not see what advantages Lisp would offer compared to C or
< assembler in chess programming. Anyway, I will probably develop a
< Lisp chess program some day, just to find out what speed I can
< achive using this language...

With a high level language it may be easier to focus on strategy
rather than wasting energy trying to make the machine search several
billion possibilities per second.
From: Richard Coleman
Subject: Re: Chess with LISP or FORTH????
Date: 
Message-ID: <rck90sh29f.fsf@math.gatech.edu>
Steve Gonedes <········@worldnet.att.net> writes:

> ·······@janus.uio.no (Tord Kallqvist Romstad) writes:
> 
> < I do not see what advantages Lisp would offer compared to C or
> < assembler in chess programming. Anyway, I will probably develop a
> < Lisp chess program some day, just to find out what speed I can
> < achive using this language...
> 
> With a high level language it may be easier to focus on strategy
> rather than wasting energy trying to make the machine search several
> billion possibilities per second.

That's always been a good theory.  But the reality has been that
the best chess/checkers/etc. playing programs are usually written
in C, Fortran, or assembler.

Sometimes, brute force just works.

-- 
Richard Coleman
·······@math.gatech.edu
From: David Steuber "The Interloper
Subject: Re: Chess with LISP or FORTH????
Date: 
Message-ID: <3654db22.80900658@news.newsguy.com>
On 18 Nov 1998 20:58:36 -0500, Richard Coleman
<·······@math.gatech.edu> claimed or asked:

% > With a high level language it may be easier to focus on strategy
% > rather than wasting energy trying to make the machine search several
% > billion possibilities per second.
% 
% That's always been a good theory.  But the reality has been that
% the best chess/checkers/etc. playing programs are usually written
% in C, Fortran, or assembler.
% 
% Sometimes, brute force just works.

While brute force would allow a game like Othello (Reverse) to beat a
human or do no worse than a tie, the game of chess allows for far more
possibilities.  Getting a machine to go through an entire game tree
for each move is not feasible.  Even a depth of six or seven moves
brings you into BFN ranges.

The really good human chess players have a strong middle game compared
to most of the computer programs.  The computer is good with storing a
large number of precomputed book openings.  The computer is also good
with just a few pieces remaining on the board.  In the middle game,
the chess masters have some kind of knack for quickly dismissing bad
moves.

Analyzing chess is a bit beyond me.  I've tried to write a Go move
generator.  Getting the computer to make intelligent choices is very
hard.  I never succeeded, although others have.

Assuming brute force is not within reach, as in chess and go, the real
trick is pruning the game tree down to a manageable size.

--
David Steuber (ver 1.31.2a)
http://www.david-steuber.com
To reply by e-mail, replace trashcan with david.

"Ignore reality there's nothing you can do about it..."
-- Natalie Imbruglia "Don't you think?"
From: Richard Coleman
Subject: Re: Chess with LISP or FORTH????
Date: 
Message-ID: <rcu2zuwsl1.fsf@math10.math.gatech.edu>
········@david-steuber.com (David Steuber "The Interloper") writes:

> % > With a high level language it may be easier to focus on strategy
> % > rather than wasting energy trying to make the machine search several
> % > billion possibilities per second.
> % 
> % That's always been a good theory.  But the reality has been that
> % the best chess/checkers/etc. playing programs are usually written
> % in C, Fortran, or assembler.
> % 
> % Sometimes, brute force just works.
> 
> While brute force would allow a game like Othello (Reverse) to beat a
> human or do no worse than a tie, the game of chess allows for far more
> possibilities.  Getting a machine to go through an entire game tree
> for each move is not feasible.  Even a depth of six or seven moves
> brings you into BFN ranges.

The results do not bear this out.  All of the best computer chess programs
use essentially brute force search (with tons of heuristics to speed this
up).  Where as the brute force programs at playing close to Grandmaster level,
I've never heard of a chess program that uses selective search (attempting
to be "intelligent") that plays anywhere close to that level.

Go hang out in rec.games.chess.computers for a while.  There are some very
knowledgeable computer types over there.

> The really good human chess players have a strong middle game compared
> to most of the computer programs.  The computer is good with storing a
> large number of precomputed book openings.  The computer is also good
> with just a few pieces remaining on the board.

> In the middle game,
> the chess masters have some kind of knack for quickly dismissing bad
> moves.

Yes, that's how humans do it.  But that doesn't make it a good strategy
for chess programs.  It's been tried many times.

> Analyzing chess is a bit beyond me.  I've tried to write a Go move
> generator.  Getting the computer to make intelligent choices is very
> hard.  I never succeeded, although others have.
> 
> Assuming brute force is not within reach, as in chess and go, the real
> trick is pruning the game tree down to a manageable size.

Yes, but no one has figured out how to do this effectively.  Not that I've
ever heard of, anyway.

-- 
Richard Coleman
·······@math.gatech.edu
From: Christopher Barry
Subject: Re: Chess with LISP or FORTH????
Date: 
Message-ID: <36565070.1A81AFCF@2xtreme.net>
The game of Go is rather interesting in that if you had an ultra, ultra
powerful computer it is no more interesting than a game of tic-tac-toe.
In other words, the person that makes the first move is guaranteed to
win if they play *perfectly*. A computer with sufficient disk and time
would be unbeatable if allowed the first move.

With chess, AFAIK it's not known whether if God or an infinitely
powerful computer is guaranteed the win if allowed the first move and
playing perfectly.

These are weird things to think about, far more wacky than P and NP.

Christopher

David Steuber The Interloper wrote:
> 
> On 18 Nov 1998 20:58:36 -0500, Richard Coleman
> <·······@math.gatech.edu> claimed or asked:
> 
> % > With a high level language it may be easier to focus on strategy
> % > rather than wasting energy trying to make the machine search several
> % > billion possibilities per second.
> %
> % That's always been a good theory.  But the reality has been that
> % the best chess/checkers/etc. playing programs are usually written
> % in C, Fortran, or assembler.
> %
> % Sometimes, brute force just works.
> 
> While brute force would allow a game like Othello (Reverse) to beat a
> human or do no worse than a tie, the game of chess allows for far more
> possibilities.  Getting a machine to go through an entire game tree
> for each move is not feasible.  Even a depth of six or seven moves
> brings you into BFN ranges.
> 
> The really good human chess players have a strong middle game compared
> to most of the computer programs.  The computer is good with storing a
> large number of precomputed book openings.  The computer is also good
> with just a few pieces remaining on the board.  In the middle game,
> the chess masters have some kind of knack for quickly dismissing bad
> moves.
> 
> Analyzing chess is a bit beyond me.  I've tried to write a Go move
> generator.  Getting the computer to make intelligent choices is very
> hard.  I never succeeded, although others have.
> 
> Assuming brute force is not within reach, as in chess and go, the real
> trick is pruning the game tree down to a manageable size.
> 
> --
> David Steuber (ver 1.31.2a)
> http://www.david-steuber.com
> To reply by e-mail, replace trashcan with david.
> 
> "Ignore reality there's nothing you can do about it..."
> -- Natalie Imbruglia "Don't you think?"
From: Bill Newman
Subject: Re: Chess with LISP or FORTH????
Date: 
Message-ID: <wnewmanF2s20n.Bvy@netcom.com>
Christopher Barry (······@2xtreme.net) wrote:
: The game of Go is rather interesting in that if you had an ultra, ultra
: powerful computer it is no more interesting than a game of tic-tac-toe.
: In other words, the person that makes the first move is guaranteed to
: win if they play *perfectly*. A computer with sufficient disk and time
: would be unbeatable if allowed the first move.

But in Go, white is given a few points "komi" to make up for black's
advantage, and no one knows what the fair amount is. (5.5 points is
the most common value, but others have been tried.)  So Go as played
in practice has the same "who knows who wins?" problem as chess.

  Bill
From: Gareth McCaughan
Subject: Re: Chess with LISP or FORTH????
Date: 
Message-ID: <8690h2o83p.fsf@g.pet.cam.ac.uk>
Christopher Barry wrote:

> The game of Go is rather interesting in that if you had an ultra, ultra
> powerful computer it is no more interesting than a game of tic-tac-toe.
> In other words, the person that makes the first move is guaranteed to
> win if they play *perfectly*. A computer with sufficient disk and time
> would be unbeatable if allowed the first move.

I don't believe this is known. (It's probably *true* if you ignore
komi, but that's another matter.)

Are you thinking of the "strategy-stealing" argument that can be
used to prove that some games (e.g. Hex) are first-player wins?
If so, note that it doesn't work for go because adding a stone
to the board doesn't always improve the position of the player
whose stone it is. Compare

 # # # # # # #         # # # # # # #
 # O O # O O #         # O O # O O #
 # O . O . O #  with   # O O O . O #
 # O O O O O #         # O O O O O #
 # # # # # # #         # # # # # # #

for a simple example.

Anyway, it might be worth mentioning that "ultra, ultra powerful"
means "considerably more powerful than the laws of physics appear
to allow"...

-- 
Gareth McCaughan       Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk  Cambridge University, England.
From: David Steuber "The Interloper
Subject: Re: Chess with LISP or FORTH????
Date: 
Message-ID: <36576478.1336892@news.newsguy.com>
On Sat, 21 Nov 1998 05:32:05 GMT, Christopher Barry
<······@2xtreme.net> claimed or asked:

% The game of Go is rather interesting in that if you had an ultra, ultra
% powerful computer it is no more interesting than a game of tic-tac-toe.
% In other words, the person that makes the first move is guaranteed to
% win if they play *perfectly*. A computer with sufficient disk and time
% would be unbeatable if allowed the first move.

So _that_ explains why the computer always beats me when it gets the
first move! ;-)

I thought someone did prove that white should win in chess.  Perhaps
that was just a conjecture?

--
David Steuber (ver 1.31.3a)
http://www.david-steuber.com
To reply by e-mail, replace trashcan with david.

May the source be with you...
From: Tord Kallqvist Romstad
Subject: Re: Chess with LISP or FORTH????
Date: 
Message-ID: <slrn75immi.iou.romstad@janus.uio.no>
In article <················@news.newsguy.com>, David Steuber "The Interloper" 
wrote:
>On Sat, 21 Nov 1998 05:32:05 GMT, Christopher Barry
><······@2xtreme.net> claimed or asked:
>
>% The game of Go is rather interesting in that if you had an ultra, ultra
>% powerful computer it is no more interesting than a game of tic-tac-toe.
>% In other words, the person that makes the first move is guaranteed to
>% win if they play *perfectly*. A computer with sufficient disk and time
>% would be unbeatable if allowed the first move.
>
>So _that_ explains why the computer always beats me when it gets the
>first move! ;-)
>
>I thought someone did prove that white should win in chess.  Perhaps
>that was just a conjecture?

I think all strong chess players would agree that the game is almost 
certainly a draw with optimal play.  Actually, go is much more interesting
in this respect; it is extremely hard to guess the result of a 
game-theoretically perfect game (remember that komi is always used in
serious games).

Tord
From: Tord Kallqvist Romstad
Subject: Re: Chess with LISP or FORTH????
Date: 
Message-ID: <slrn758mv6.9ss.romstad@janus.uio.no>
In article <··············@KludgeUnix.com>, Steve Gonedes wrote:
>
>·······@janus.uio.no (Tord Kallqvist Romstad) writes:
>
>< I do not see what advantages Lisp would offer compared to C or
>< assembler in chess programming. Anyway, I will probably develop a
>< Lisp chess program some day, just to find out what speed I can
>< achive using this language...
>
>With a high level language it may be easier to focus on strategy
>rather than wasting energy trying to make the machine search several
>billion possibilities per second.

Easy to say, extremely hard to do.  There have been several attempts to
make "intelligent" chess programs, but nobody has been successful.  The
brute force approach to computer chess works extremely well; while the
AI approach still hasn't produced any program of decent strength.  Of 
course, this does not prove that it is impossible to make a strong AI
based chess program, but it is clearly very very hard.  There are _lots_
of very bright people in the chess programming community.

Tord