Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old April 14th 07, 01:47 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Apr 2007
Posts: 5
Default 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 markets 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


  #2   Report Post  
Old April 14th 07, 04:08 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Dec 2005
Posts: 383
Default 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 markets 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




  #3   Report Post  
Old April 14th 07, 04:18 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Apr 2005
Posts: 2,598
Default genetic algorithms for chess

Buller 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!
  #4   Report Post  
Old April 14th 07, 08:24 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Aug 2006
Posts: 157
Default 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
  #5   Report Post  
Old April 15th 07, 02:01 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Dec 2005
Posts: 383
Default 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


  #6   Report Post  
Old April 15th 07, 02:05 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Dec 2005
Posts: 383
Default 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
  #7   Report Post  
Old April 15th 07, 02:34 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Aug 2006
Posts: 157
Default 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
  #8   Report Post  
Old April 15th 07, 03:06 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Dec 2005
Posts: 383
Default 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
  #9   Report Post  
Old April 15th 07, 06:57 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Jul 2004
Posts: 834
Default 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).


  #10   Report Post  
Old April 16th 07, 12:44 AM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Dec 2005
Posts: 383
Default 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
Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On



All times are GMT +1. The time now is 10:32 AM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright 2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017