| |
Main
Date: 14 Apr 2007 12:47:54
From: Buller
Subject: genetic algorithms for chess
|
Is anyone aware of any interesting research on developing strong
chess-playing engines using genetic algorithms? According to Wikipedia,
this has been done for checkers, resulting in a fairly strong program (but
not as strong as the best, Chinook). The internet mentions some efforts at
doing so for chess, but I haven't heard of any huge achievement. GA are
quite fascinating; the resulting problem solvers (for biological research,
electronic design, financial kets analysis, etc.) often end up being
something the human designer doesn't even understand, yet perform better
than what the human would have produced. For chess, it seems like one could
start with a bunch of random-playing algorithms (e.g., Stanley the Monkey in
Chessmaster!), randomly mutate them, select for fitness (i.e., chess
strength), repeat, ... After lots of generations maybe there'd be some that
could beat today's best. Interesting possibility?
DB
|
|
| |
Date: 14 Apr 2007 16:18:18
From: David Richerby
Subject: Re: genetic algorithms for chess
|
Buller <[email protected] > wrote:
> Is anyone aware of any interesting research on developing strong
> chess-playing engines using genetic algorithms? According to
> Wikipedia, this has been done for checkers, resulting in a fairly
> strong program (but not as strong as the best, Chinook). [...] For
> chess, it seems like one could start with a bunch of random-playing
> algorithms (e.g., Stanley the Monkey in Chessmaster!), randomly
> mutate them, select for fitness (i.e., chess strength), repeat, ...
> After lots of generations maybe there'd be some that could beat
> today's best. Interesting possibility?
*shrug* I believe that people have already used this kind of
technique for tuning evaluation functions. As for using it for the
whole search, I'm not convinced. As you say, for checkers, it results
in a weaker program than can be written by ordinary means, as one
would expect from applying a general-purpose technique to a specific
problem.
Dave.
--
David Richerby Gigantic Nuclear Radio (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a radio that's made of atoms but
it's huge!
|
| | |
Date: 15 Apr 2007 15:01:33
From: Ralf Callenberg
Subject: Re: genetic algorithms for chess
|
14.04.2007 17:18, David Richerby:
> As you say, for checkers, it results
> in a weaker program than can be written by ordinary means, as one
> would expect from applying a general-purpose technique to a specific
> problem.
It's not sure, that this is indeed the reason for its weak play compared
to Chinook. There are a lot of techniques to optimize the search which
are not used by Blondie24. So, it might be interesting to take an
existing, strong program and replace its evaluation function with such a
neural network as in Blondie24 and optimize it in a similar way - and
then see how it performs compared to the original program.
Chinook was written by an expert author of chess programs, who knew
barely anything about checkers when he started. He asked a checkers
expert for support with the evaluation function, and after about two
months of adapting the chess program to checkers they were clearly
superior to any existing checkers program. I doubt that the evaluation
function was so sophisticated. The search techniques used by the chess
program made the real difference.
Greetings,
Ralf
|
| | | |
Date: 15 Apr 2007 17:57:16
From: Guy Macon
Subject: Re: genetic algorithms for chess
|
R
alf Callenberg wrote:
>So, it might be interesting to take an existing, strong program
>and replace its evaluation function with such a neural network
>as in Blondie24 and optimize it in a similar way - and
>then see how it performs compared to the original program.
I see no reason why a neural network needs to be introduced
-- unless of course you want to investigate neural networks
as opposed to genetic algorithms. To investigate genetic
algorithms, take an existing, strong program and make many
copies with mutations of the evaluation functions, then let
them play against each other with winners having more
offspring. That will optimize the program for beating copies
of itself with different evaluation functions. Then you do it
all again against other chess programs, and finally do it all
again against human players (perhaps on a web server).
|
| | | | |
Date: 16 Apr 2007 01:44:49
From: Ralf Callenberg
Subject: Re: genetic algorithms for chess
|
15.04.2007 19:57, Guy Macon:
> I see no reason why a neural network needs to be introduced
> -- unless of course you want to investigate neural networks
> as opposed to genetic algorithms.
No, not opposed. They work together. Fogel used an evolutionary
algorithm to optimize the weights of the neural network.
To investigate genetic
> algorithms, take an existing, strong program and make many
> copies with mutations of the evaluation functions, then let
> them play against each other with winners having more
> offspring.
Well, you have to parametrize somehow the evaluation function for this
approach. A neural network offers a very generic way to do so. What
parametrization would you suggest instead?
Greetings,
Ralf
|
| | |
Date: 14 Apr 2007 19:24:48
From: Anders Thulin
Subject: Re: genetic algorithms for chess
|
David Richerby wrote:
> whole search, I'm not convinced. As you say, for checkers, it results
> in a weaker program than can be written by ordinary means, as one
> would expect from applying a general-purpose technique to a specific
> problem.
But isn't the principle the same as Samuels used in his checkers program?
That was a pretty good checkers-playing program for its time, if I recall...
--
Anders Thulin ath*algonet.se http://www.algonet.se/~ath
|
| | | |
Date: 15 Apr 2007 15:05:27
From: Ralf Callenberg
Subject: Re: genetic algorithms for chess
|
14.04.2007 21:24, Anders Thulin:
>
> But isn't the principle the same as Samuels used in his checkers program?
I didn't find anything detailed about Samuel's program. In the texts I
found is just mentioned, that his evaluation function is some
ploynomial. But what are the constituents of this function is nowhere
given. Were they very general or was already some knowledge about what
is important in checkers introduced?
Greetings,
Ralf
|
| | | | |
Date: 16 Apr 2007 08:03:58
From: Hello
Subject: Re: genetic algorithms for chess
|
"Ralf Callenberg" <[email protected] > wrote in message
news:[email protected]...
> 14.04.2007 21:24, Anders Thulin:
>>
>> But isn't the principle the same as Samuels used in his checkers
>> program?
>
> I didn't find anything detailed about Samuel's program. In the texts I
Original 1959 paper:
http://domino.research.ibm.com/tchjr/journalindex.nsf/0b9bc46ed06cbac1852565e6006fe1a0/39a870213169f45685256bfa00683d74?OpenDocument
Followup 1967 paper:
http://domino.research.ibm.com/tchjr/journalindex.nsf/0b9bc46ed06cbac1852565e6006fe1a0/6fb05411fd49d77b85256bfa00683fb6?OpenDocument
2000 reprint:
http://domino.research.ibm.com/tchjr/journalindex.nsf/0b9bc46ed06cbac1852565e6006fe1a0/3d602ed510e01ee985256bfa0067fb65?OpenDocument
> found is just mentioned, that his evaluation function is some ploynomial.
> But what are the constituents of this function is nowhere given. Were they
> very general or was already some knowledge about what is important in
> checkers introduced?
>
> Greetings,
> Ralf
>
----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
|
| | | | |
Date: 15 Apr 2007 13:34:16
From: Anders Thulin
Subject: Re: genetic algorithms for chess
|
Ralf Callenberg wrote:
> given. Were they very general or was already some knowledge about what
> is important in checkers introduced?
If I recall, it was a rather large bag of various things that
could be important. Their actual importance (i.e. the weighting factors)
were recomputed based on the losses of the program.
--
Anders Thulin ath*algonet.se http://www.algonet.se/~ath
|
| | | | | |
Date: 15 Apr 2007 16:06:55
From: Ralf Callenberg
Subject: Re: genetic algorithms for chess
|
15.04.2007 15:34, Anders Thulin:
> If I recall, it was a rather large bag of various things that
> could be important. Their actual importance (i.e. the weighting factors)
> were recomputed based on the losses of the program.
That's what I also assumed. But when this "bag of various things that
could be important" already requires some knowledge about the game, it
can hardly be called "general purpose technique". With an approach like
Blondie24 you just have to know the rules of the game, no other game
specific knowledge is required. This is still confined to a family of
games, but you could create an engine for variants quite easy, as long
as you can encode the rules in a conveniant way.
Greetings,
Ralf
|
| |
Date: 14 Apr 2007 17:08:17
From: Ralf Callenberg
Subject: Re: genetic algorithms for chess
|
14.04.2007 14:47, Buller:
> Is anyone aware of any interesting research on developing strong
> chess-playing engines using genetic algorithms?
You might try Google with the search "genetic algorithms chess".
> According to Wikipedia,
> this has been done for checkers, resulting in a fairly strong program (but
> not as strong as the best, Chinook). The internet mentions some efforts at
> doing so for chess, but I haven't heard of any huge achievement. GA are
> quite fascinating; the resulting problem solvers (for biological research,
> electronic design, financial kets analysis, etc.) often end up being
> something the human designer doesn't even understand, yet perform better
> than what the human would have produced. For chess, it seems like one could
> start with a bunch of random-playing algorithms (e.g., Stanley the Monkey in
> Chessmaster!), randomly mutate them, select for fitness (i.e., chess
> strength), repeat, ...
The basic problem here is to encode the algorithm so that the GA can
operate on this encoding. This is far from easy. Take as an example the
checkers playing program Blondie24 from David Fogel. They didn't let the
whole algorithm evolve. What they did is, they took a standard minimax
and parametrized the evaluation function in form of a neural network.
This means a position is entered into a neural network which returns a
value. The parameters of this neural network are then adapted using an
evolutionary algorithm. (I think, this is a quite obvious approach, I
myself have thought about something quite similar. Yet, the technical
details are still not trivial, so I respect the work Fogel has done, and
don't regard it as something minor) So, not the algorithm was created
using a GA, but just a part of it (although a central one). The whole
stuff todays chess programs use for enhancing the search (and which is
very important for the strength of a program) is not covered by this
approach. It might be, that this way an evaluation of the position can
come out, which was not foreseen by other programmers. It is interesting
and seems to be done for chess as well. But this is already a limited
approach, as the static position is regarded for evaluation. There are
hints, that Rybka uses a different approach for the evaluation, based on
more dynamic aspects of the position. This could not have been detected
by a technique similar to Blondie24.
So this "Genetic algorithms find a playing algorithm without using prior
knowledge of the game" goes too far and is not realistic at this moment.
and also any hope such a program could be superior to existing
solutions. What might be interesting: in all algorithms you have to
weight different aspects, there are parameters in each algorithm. The
parameters are usually determined by assumptions, heuristics or trial
and error. Whenever parameters come into play, it is a good possibility
to determine them using evolutionary algorithms, instead. So the GAs
might enhance classical techniques in chess programming, that they are
able to completely replace them seems not very likely.
Greetings,
Ralf
|
|
