Re: A86: Chess Engine

To: assembly-86@lists.ticalc.org
Subject: Re: A86: Chess Engine
From: Dan Eble <eble@cis.ohio-state.edu>
Date: Mon, 3 Nov 1997 09:05:02 -0500 (EST)
In-Reply-To: <345AEFA0.3B8@algonet.se>
Reply-To: assembly-86@lists.ticalc.org

On Sat, 1 Nov 1997, Jimmy Mårdell wrote:

> David Piper wrote:
> > 
> > I have decided to make Chess Master 86,  It will have a computer to play
> > against...
> 
> Good luck.
> 

Yeah.  You're getting into more than you know.

> > This is my problem,  how do I effectivily make a good computer apponent
> > without the program being massive....

To make any good AI program, you have to give it a lot of knowledge
(tough because of memory size), or a lot of search capability (tough
because of memory size and processor speed), or a combination of both.

> If you're serious about programming a chessprogram, you really must
> know what you're doing if you want to the computer to beat anyone
> (even a complete beginner). Using brute force in the search algorithm
> will maybe allow the computer to think at most 3 ply (halfmoves) ahead,

In typical chess games, the "branching factor" of the decision tree is
about 35, which means there are about 35 possibilities for legal moves
every turn.  Therefore, a 3-ply brute force algorithm would need to look
at 35^3 board configurations, which would probably not fit into the TI-86
memory.  Deep Blue can look ahead about 13 plies.  (It's a little bit
faster than a TI-86.) 

> There are several hiearchies (sp?) used in modern chess program to
> reduce the size of the enormous tree of moves, and you have to use
> at least SOME of them if you want at least a computer than doesn't
> make blunder moves all the time.

I think the word you want is "heuristics", Jimmy.  :-)

--------
Dan Eble <eble@cis.ohio-state.edu>
         (http://www.cis.ohio-state.edu/~eble)

"Behold, how great a matter a little fire kindleth!" - James 3:5

References:

From: