[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: AI Chess program: a project suggestion
Alexander 'Sasha' Chislenko (sasha1@netcom.com) wrote:
: I would like to suggest a chess programming project using
: AI and Alife techniques, that should, in my opinion,
: considerably advance computer chess, without much
: expense to the developers.
: ---------------------------------------------------------
: Current chess-playing algorithms combine programming of
: chess-specific knowledge (details of evaluation functions,
: libraries of games and search-tree trimming techniques)
: with brute-force search for a few (5 to 15) moves ahead.
: Both parts of this approach are expensive (ad-hoc coding
: - for people, and brute-force search - for computers),
: and their results are of little utility for problems
: unrelated to chess.
: A suggestion that could be of greater use, would be to
: build a program that would "understand" chess by learning
: from other games and its own experience.
: On utility of "understanding":
: There are many situations in the game that do not necessarily
: translate into the checkmate in the next 10 moves, and so are
: impossible to detect in the limited-depth search. The simplest
: example may be a small material advantage. Simple things like
: that may, of course, be programmed into the evaluation function.
: However, there are numerous other patterns that do not soon
: translate either to a checkmate or a material advantage, such as
: doubled pawns, trapped pieces, etc. Good chessplayers identify
: hundreds to thousands of such situations, and put considerations
: of their development into the strategy of the game (that machines
: do not seem to have at this point).
: This understanding of the game may be programmed directly into
: the chess program's evaluation function. However, this approach
: has a number of disadvantages:
: - this knowledge is largely intuitive and extracting and
: formalizing it is quite difficult.
: - human computational costs are different from the computers':
: we may easily spend a trillion operations recognizing some
: visual pattern on the board, but would find 100 arithmetic
: operations prohibitively difficult. For the computer it's
: the other way round. So the set of useful heuristics may
: be somewhat different.
: - simple addition of recognized patterns, with some weights, to
: the evaluation function is insufficient, because it doesn't
: take into account the scenarious of these patterns affecting
: the play, as some of them can be utilized only if others are
: not, some may not have time to develop, etc. So we would also
: need to program flexible strategies here.
: - even if all of the above is directly programmed into the machine,
: we get not an AI chess program, but a programmed intelligence.
: The difference is that for any new kind of game we would have to
: figure out things and program them into the machine from scratch.
: The approach I would like to suggest is to program the rules and
: goals of the game, and write an algorithm that would try to find
: patterns and determine their utility. That is, it may build some
: "temporal logic" out of them: e.g. "if you have a lot fewer
: pieces, you usually lose", "trapped rooks do not get back into
: game without some sacrifice", or "winners don't double pawns".
: Then it may generalize the patterns, compare their utility to
: computational costs, combine them, etc.
: The resulting algorithms may be less computationally expensive
: than positional knowledge extracted from human masters, and the
: whole project would be much more generic and useful for the
: development of the discipline than the brute force mechanism
: specifically tuned for chess.
: Many of such patterns may be not that difficult to find.
: The problem is, these observations cannot be made from computer-
: generated games, exactly because the computer doesn't know them,
: so it doesn't create them or loses them once they appear.
: Neither can they be found in the games of good masters, as any
: little regularities a beginner (computer or human) may detect,
: are kept in the masters' minds, but in their pure form never
: appear in the game.
: The solution here may be to collect a large library of *bad*
: games played by inexperienced players against each other and
: mediocre computer programs, where such simple situations may
: actually be observed. Fortunately for this approach, this is
: exactly the kind of games people usually play. :-)
: Such approach may not be the best to defeat Kasparov before the
: year 2000. However, if the developers accept the "hill-climbing"
: strategy they have been teaching to machines, and drop the idea
: of taking down the biggest opponent in the next move, but instead
: figure out where they actually want to get, and take a few steps
: back, then they may actually achieve something seriously useful,
: and not only in chess. Still, it may be the fastest way to build
: a machine with ELI rating equivalent of 10,000.
: The components for such a project may be:
: - a freeware chess program with clean source code that can accept
: "genetic hooks". (can be found on the Net)
: - Lots of mediocre chess players (available on and off-line)
: - A bit of infrastructure to extract and store games.
: (very little Net-work)
: - A few chess/alife/AI enthusiasts
: - A good enough machine to run the project on.
: (The last two may be found for free in any university)
: All of the above, except the bad players, appeared only in the
: last few years. So now looks like a good time to start...
: Anybody interested in working on this?
:
: --------------------------------------------------
: Alexander Chislenko <sasha1@netcom.com>
: Home page: http://www.lucifer.com/~sasha/home.html
--
**********begin r.s. response************
not sure now...
but think ideas like this are
old...
alternatively...
in a unix os supporting the
spawning of processes
and
multiprocess operation
start with one program, playing itself,
and learning from its mistakes...
(two programs...adam and eve?)
with randomizing tie breakers...
and progeny...
leave to fight it out for, oh,
half a year...
and see what evolves...
**********end r.s. response**************
Ralph Silverman
z007400b@bcfreenet.seflin.lib.fl.us