Training a Genetic algorithm?

[BlueAce]

I am working on a chess engine, with a very intelligent Evaluation Function.

I want to tune the parameters of the Eval Function by taking help from a genetic algorithm.

Now the problem is that genetic algorithms are good for unsupervised learning, and they work only using a fitness evaluation and reproduction as incentive, but in all, a genetic algorithm is dumb, i.e. it doesn't care about the problem, its just an easier brute force approach to getting close to the global optima for the problem.

However, for a game like chess, I do have some training data which I want to use to improve the parameters of the Eval fn.
It is easy to use an end game table base as an oracle, or a powerful chess engine that looks deep enough (around 8-10 plys) as an imperfect oracle.
Since I am using a GA, I would like to use this training data to help my GA converge faster to the solution.

However, unlike a Neural Network, where back-propagation can be used easily, I dont know any method of "training" a population of Genetic Algorithm.

So, please suggest me some ways of doing the same.

Also, please suggest some innovative methods of implementing Genetic Algorithms, and maybe some articles/tutorials.

Thanks

[Hamfer]

You can use another chess engine as mentor as described in "Genetic Algorithms for Mentor-Assisted Evaluation Function Optimization".

[Don]

I am working on a chess engine, with a very intelligent Evaluation Function.

I want to tune the parameters of the Eval Function by taking help from a genetic algorithm.

Now the problem is that genetic algorithms are good for unsupervised learning, and they work only using a fitness evaluation and reproduction as incentive, but in all, a genetic algorithm is dumb, i.e. it doesn't care about the problem, its just an easier brute force approach to getting close to the global optima for the problem.

However, for a game like chess, I do have some training data which I want to use to improve the parameters of the Eval fn.
It is easy to use an end game table base as an oracle, or a powerful chess engine that looks deep enough (around 8-10 plys) as an imperfect oracle.
Since I am using a GA, I would like to use this training data to help my GA converge faster to the solution.

However, unlike a Neural Network, where back-propagation can be used easily, I dont know any method of "training" a population of Genetic Algorithm.

So, please suggest me some ways of doing the same.

Also, please suggest some innovative methods of implementing Genetic Algorithms, and maybe some articles/tutorials.

Thanks

I found a way to do this. First of all I adapted PBIL which is population based incremental learning, it is related to the CGA (compact genetic algorithm) and has the requirement that you select 1 individual from a population of individuals and forgo the breeding aspect. So the question is the fitness function. It's my opinon that only matches are appropriate for fitness in chess and of course the resources to measure fitness this way are enormous. But much can be done to improve on that.

The naive approach is to select N individuals for a given generation, play a round robin tournament and select the top player. But that is very inefficient. A better approach is the recursive KO (knockout tournament) or sometimes called the elimination tournament. Due to sample error no evaluation system is going to consistently return the best player but the K/O tournament is a very simple procedure which will consistently return a very good player. And it will do so with significantly less effort than round robin.

The principle is that even though there may be upsets along the way, it is very unlikely the winner will be one of the weaker player. On average you will face increasingly difficult opponents as you progress from round to round so when a weaker players gets "lucky" in one round he is faced with an even stronger opponent. I ran simulations and found the K/O tournament is orders of magnitude more effective than round robin if the only goal is to find a good player. Round Robin tries to evaluate ALL players (even the weak ones) so common sense tells you that this is foolish.

One enhancement I found was that in later rounds you can play longer matches. The procedure I used was to pick an opening and play 2 games per match pairing. If it came out as a draw I simply picked one at random. On the semi-final round I played 4 games and in the final 8 games. A few extra games on late rounds is cheap. Here is an example why. If you play 6 rounds you have 64 players. The first round is by far the most expensive because you must play 32 matches. In the second round you only play 16 matches. When you finally play the final round you only play 1 match - so there is little additional overhead involved in playing extra games in late rounds.

The procedure for playing a K/O is recursive and trivial to implement. I have not checked this for correctness but it works something like this:

Code: Select all

player_t  ko(int round) 
{
  player_t  a;
  player_t  b;

  if (round == 1) {
    a = generate_player();
    b = generate_player();
  } else {
    a = ko(round - 1);
    b = ko(round - 1);
  }

  player_t winner = play_match( a, b );
  return winner;
}

In the first round you generate 2 players using whatever your learning algorithm calls for. Otherwise the 2 players are generated from 2 sub-tournaments. Then we return the winning of these 2 players. Neat and tidy and dirt simple.

Don

[BlueAce]

You can use another chess engine as mentor as described in "Genetic Algorithms for Mentor-Assisted Evaluation Function Optimization".

Thanks for your help, but that was not what I was looking for.

I found a way to do this. First of all I adapted PBIL which is population based incremental learning, it is related to the CGA (compact genetic algorithm) and has the requirement that you select 1 individual from a population of individuals and forgo the breeding aspect.

Thanks, that looks promising, I will try it out..

So the question is the fitness function. It's my opinon that only matches are appropriate for fitness in chess and of course the resources to measure fitness this way are enormous. But much can be done to improve on that.

The naive approach is to select N individuals for a given generation, play a round robin tournament and select the top player. But that is very inefficient. A better approach is the recursive KO (knockout tournament) or sometimes called the elimination tournament. Due to sample error no evaluation system is going to consistently return the best player but the K/O tournament is a very simple procedure which will consistently return a very good player. And it will do so with significantly less effort than round robin.

The principle is that even though there may be upsets along the way, it is very unlikely the winner will be one of the weaker player. On average you will face increasingly difficult opponents as you progress from round to round so when a weaker players gets "lucky" in one round he is faced with an even stronger opponent. I ran simulations and found the K/O tournament is orders of magnitude more effective than round robin if the only goal is to find a good player. Round Robin tries to evaluate ALL players (even the weak ones) so common sense tells you that this is foolish.

One enhancement I found was that in later rounds you can play longer matches. The procedure I used was to pick an opening and play 2 games per match pairing. If it came out as a draw I simply picked one at random. On the semi-final round I played 4 games and in the final 8 games. A few extra games on late rounds is cheap. Here is an example why. If you play 6 rounds you have 64 players. The first round is by far the most expensive because you must play 32 matches. In the second round you only play 16 matches. When you finally play the final round you only play 1 match - so there is little additional overhead involved in playing extra games in late rounds.

The procedure for playing a K/O is recursive and trivial to implement. I have not checked this for correctness but it works something like this:

Code: Select all

player_t  ko(int round) 
{
  player_t  a;
  player_t  b;

  if (round == 1) {
    a = generate_player();
    b = generate_player();
  } else {
    a = ko(round - 1);
    b = ko(round - 1);
  }

  player_t winner = play_match( a, b );
  return winner;
}

In the first round you generate 2 players using whatever your learning algorithm calls for. Otherwise the 2 players are generated from 2 sub-tournaments. Then we return the winning of these 2 players. Neat and tidy and dirt simple.

Don

Well, yes.. A knock out tournament was exactly what I was planning for my fitness evaluation, but I will be implementing it in a way that every individual plays atleast 4 matches in the first round itself, so as to minimize the risk of a good individual getting knocked out in the first round out of bad luck.

Thanks a lot

[Don]

You can use another chess engine as mentor as described in "Genetic Algorithms for Mentor-Assisted Evaluation Function Optimization".

Thanks for your help, but that was not what I was looking for.

I found a way to do this. First of all I adapted PBIL which is population based incremental learning, it is related to the CGA (compact genetic algorithm) and has the requirement that you select 1 individual from a population of individuals and forgo the breeding aspect.

Thanks, that looks promising, I will try it out..

So the question is the fitness function. It's my opinon that only matches are appropriate for fitness in chess and of course the resources to measure fitness this way are enormous. But much can be done to improve on that.

The naive approach is to select N individuals for a given generation, play a round robin tournament and select the top player. But that is very inefficient. A better approach is the recursive KO (knockout tournament) or sometimes called the elimination tournament. Due to sample error no evaluation system is going to consistently return the best player but the K/O tournament is a very simple procedure which will consistently return a very good player. And it will do so with significantly less effort than round robin.

The principle is that even though there may be upsets along the way, it is very unlikely the winner will be one of the weaker player. On average you will face increasingly difficult opponents as you progress from round to round so when a weaker players gets "lucky" in one round he is faced with an even stronger opponent. I ran simulations and found the K/O tournament is orders of magnitude more effective than round robin if the only goal is to find a good player. Round Robin tries to evaluate ALL players (even the weak ones) so common sense tells you that this is foolish.

One enhancement I found was that in later rounds you can play longer matches. The procedure I used was to pick an opening and play 2 games per match pairing. If it came out as a draw I simply picked one at random. On the semi-final round I played 4 games and in the final 8 games. A few extra games on late rounds is cheap. Here is an example why. If you play 6 rounds you have 64 players. The first round is by far the most expensive because you must play 32 matches. In the second round you only play 16 matches. When you finally play the final round you only play 1 match - so there is little additional overhead involved in playing extra games in late rounds.

The procedure for playing a K/O is recursive and trivial to implement. I have not checked this for correctness but it works something like this:

Code: Select all

player_t  ko(int round) 
{
  player_t  a;
  player_t  b;

  if (round == 1) {
    a = generate_player();
    b = generate_player();
  } else {
    a = ko(round - 1);
    b = ko(round - 1);
  }

  player_t winner = play_match( a, b );
  return winner;
}

In the first round you generate 2 players using whatever your learning algorithm calls for. Otherwise the 2 players are generated from 2 sub-tournaments. Then we return the winning of these 2 players. Neat and tidy and dirt simple.

Don

Well, yes.. A knock out tournament was exactly what I was planning for my fitness evaluation, but I will be implementing it in a way that every individual plays atleast 4 matches in the first round itself, so as to minimize the risk of a good individual getting knocked out in the first round out of bad luck.

Thanks a lot

Just so you know, it's more important that good individuals do not get knocked out in later rounds, so if you are playing 4 games per match in the first round you should play at least that many in later rounds, perhaps even more as you progress. If you have a player who is good enough to survive to the final round, it's very unlikely he will get knocked out in the first round and the effort should be spend in later rounds (where you get more bang for you buck as the cost is half.) He is more likely to get knocked out in the second round, then 3rd, etc ...

I did simulations on this and it turns out that the most efficient use of effort (the most bang for your buck) is to escalate the number of games at later rounds. That is because the cost of adding games goes down by 2 after every round. The name of the game is getting the most for the work you put into it.

[jonpall]

Hi Don,

this is a bit off-topic, but might help you improve your wonderful engine, the following has been posted on the rybkaforum, http://rybkaforum.net/cgi-bin/rybkaforu ... ?tid=26392

jonpall