4

I am making an AI for a zero-sum 4-player board game. It's actually not zero-sum (the 4 players will "die" when they lose all their lives, so there will be a player who died first, second, third and a player who survived. However, I am telling the AI that only surviving counts as a win and anything else is a lose) After some research, I figured I would use a minimax algorithm in combination with a heuristic function. I came across this question and decided to do the same as the OP of that question - write an evolutionary algorithm that gives me the best weights.

However, my heuristic function is different from the one the OP of that question had. Mine takes 9 weights and is a lot slower, so I can't let the agents play 1000 games (takes too much time) or breed them with the crossover method (how do I do a crossover with 9 weights?).

So I decided to come up with my own method of determining fitness and breeding. And this question is only about the fitness function.

Here are my attempts at this.

First Attempt

For each agent A in a randomly generated population of 50 agents, select 3 more agents from the population (with replacement but not the same agent as A itself) and let the 4 agents play a game where A is the first player. Select another 3 and play a game where A is the second player, and so on. For each of these 4 games, if A died first, its fitness does not change. If A died second, its fitness is increased by 1. If it died third, its fitness is increased by 2. If it survived, its fitness is increased by 3. Therefore, I concluded that the highest fitness one can get is 12 (surviving/wining all 4 games -> 3 + 3 + 3 + 3).

I ran this for 7 generations and starting from the first generation, the highest fitness is as high as 10. And I calculated the average fitness of the top 10 agents, but the average didn't increase a bit throughout the 7 generations. It even decreased a little.

I think the reason why this didn't work is because there's gotta be a few agents that got lucky and got some poor performing agents as its opponents.

Second Attempt

The game setups are the same as my first attempt but instead of measuring the results of each game, I decided to measure how many moves did that agent make before it died.

After 7 generations the average fitness of top 10 does increase but still not increasing as much as I think it should.

I think the reason why this failed is that the game is finite, so there is a finite number of moves you can make before you die and the top performing agents pretty much reached that limit. There is no room for growth. Another reason is that the fitness of the player who survived and the fitness of the player who died third differs little.

What I want

From my understanding of EAs (correct me if I'm wrong), the average fitness should increase and the top performing individual's fitness should not decrease over time.

My two attempts failed at both of these. Since the opponents are randomly selected, the top performing agent in generation 1 might get stronger opponents in the next generation, and thus its fitness decreases.

Notes

In my attempts, the agents play 200 games each generation and each generation takes up to 3 hours, so I don't want to let them play too many games.

How can I write a fitness function like this?

Sweeper
  • 213,210
  • 22
  • 193
  • 313

1 Answers1

4

Seven generations doesn't seem like nearly enough to get a useful result. Especially for a game, I would expect something like 200+ generations to be more realistic. You could do a number of things:

  • Implement elitism in order to ensure the survival of the best individual(s).

  • The strength of evolution stems from repeated mutation and crossover, so I'd recommend letting the agents play only a few games per generation (say, 5 ~ 10), at least at the beginning, and then evolve the population. You might even want to do only one game per generation.

  • In this regard, you could adopt a continuous evolution strategy. What this means is that as soon as an agent dies, they are subjected to mutation, and as soon as an agent wins, they can produce offspring. Or any combination of the two. The point is that the tournament is ongoing, everyone can play against anyone else. This is a little more "organic" in the sense that it does not have strictly defined generations, but it should speed up the process (especially if you can parallelise the evaluation).

I hope that helps. The accepted answer in the post you referenced has a good suggestion about the way you could implement crossover.

cantordust
  • 1,542
  • 13
  • 17
  • But what I am seeing here is that the agents' fitnesses don't improve. I kinda want to see the agents' "growth". If I use continuous evolution I can't get the fitness of each agent right? – Sweeper Oct 27 '17 at 06:05
  • Also, I have 9 weights as my chromosome. How do I do a crossover with 9 weights? Is it just randomly pick x weights from one parent and (9-x) weights from the other parent? – Sweeper Oct 27 '17 at 06:39
  • Unless I'm missing something, based on how you described the game, you would be able to get the fitness of any individual as soon as they die or win, isn't that right? Say you have a population of 64 (just to make it divisible by 4). You make 16 random groups of 4 agents, each group playing a game. The first one to die in any group gets a fitness of 0, the second gets 1 and so on. But as soon as an agent dies, they are free to mutate and join in another game, as long as there are 3 other free agents (who either died or won, either way). – cantordust Oct 27 '17 at 11:03
  • Oh I see what you mean now :). What about the crossover? Do I just pick a few weights from one parent and another few from the other parent and use these to create the offspring? – Sweeper Oct 27 '17 at 11:05
  • About crossover: yes, you would randomly pick x weights from one parent and (9-x) from the other. There might be a case for what the person in the referenced post had (each weight in the offspring is the average of the corresponding weights from the two parents). My gut feeling is that the offspring wouldn't be able to improve on the fitter parent, but you'd have to see if that is the case in practice. – cantordust Oct 27 '17 at 11:08
  • Also, looking at the average fitness of the agents can be deceptive. Usually you want one of the agents to solve the problem at hand - be it a game or some optimisation problem - but you don't expect the population to kind of "reach consensus" about the right solution. One of the strengths of evolution is that it is good at exploration, which means that some agents will necessarily be better than others. So that's why I would suggest a smaller number of games per generation and more generations to give the agents a chance to optimise their behaviour. – cantordust Oct 27 '17 at 11:12
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/157657/discussion-between-sweeper-and-cantordust). – Sweeper Oct 27 '17 at 11:20
  • Just to clarify my comment above about crossover. When I said that I think the offspring wouldn't be able to improve on the fitter parent, I was referring to the strategy of taking the average of the weights. One thing I have found to work well in practice is to select a weight from one parent or the other in proportion to their fitness. Say one parent has a fitness of 6, the other 2. So you are three times more likely to select a weight from the fitter parent than from the less fit one. – cantordust Oct 27 '17 at 11:21