4
$\begingroup$

I am developing AI in the form of NEAT, and it has passed certain tasks like the XOR problem outlined in the NEAT Research Paper. In the XOR Problem, the fitness of a network was determined by an existing function (XOR in this case). It also passed another tests. One I developed was to determine the sine at a certain point X in radians. It also worked, but yet again, its fitness was determined by an existing function (sin (x)).

I've recently been working on training it to play Tic Tac Toe. I decided that to determine its fitness, it would play against a "dumb" AI, placing O's in random locations on the grid, and gaining fitness based on whether or not it placed X's in a valid location (losing fitness if it placed an X on top of another X or an O), and gaining a lot of fitness if it won against the "dumb" AI. This would work, but when a network got really lucky and the "dumb" AI placed O's in impractical locations, the network would win and gain a lot of fitness, making it very difficult for another network to beat that fitness. Therefore, the learning process did not work and I was not able to generate a Tic Tac Toe network that actually worked well.

I do not want the GA to learn based off an "intelligent" tic tac toe AI because the whole point of me training this GA is so that I do not have to make the AI in the first place. I want it to be able to learn rules on its own without me having to hard code an AI to be very good at it.

So, I got to thinking, and I thought it would be interesting if the fitness of a network could be determined based off how well it played against OTHER NETWORKS in its generation. This does seem similar to how humans learn to play games, as I learned to play chess by playing against other people hundreds of times, learning from my mistakes, and my friends also increased in their ability to play chess as well. If GA's were to do that, that would mean I don't have to program AI to play the game (in fact, I wouldn't have to program a "dumb" AI as well, I would only have to hard code the rules of the game, obviously).

My questions are:

  1. Has there been any research or results from GA's determining their fitness based off competing against each other? I did some searching but I have no idea what to look for in the first place (searching 'NEAT fight against each other' did not work well :-( )

  2. Does this method of training a GA seem practical? It seems practical to me, but are there any potential drawbacks to this? Are GA's meant to only calculate predetermined functions that exist, or do they have the potential to learn and do some decision making?

  3. If I were to do this, how would fitness be determined? Say, for the tic tac toe example, should fitness be determined based on whether or not a network places its X's or O's in viable locations, and add fitness if it wins and subtracts fitness if it loses? What about tying the game?

  4. Should networks of the same species compete against each other? If they did, then it would seem impractical to have species in the first place, as networks in the same species competing against each other would not allow a successful species to rise to the top, as it would be fighting against each other.

  5. Kind of out of topic, but with my original idea for the tic tac toe GA, would there be a better way to determine fitness? Would creating an intelligent AI be the best way to train a GA?

Thanks for your time, as this is somewhat lengthy, and for your feedback!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What you're describing is a type of what's known as a coevolutionary algorithm. Googling that should be a useful exercise. I'd also point out that the general idea of playing against versions of yourself has a long history in the literature around learning to play games. One of the very earliest real success stories in AI was Arthur Samuel's checkers program in 1959. He trained a program to play the game at the level of a very strong human by having it play games against itself, each time improving itself via a mechanism that resembles what we would today call reinforcement learning. $\endgroup$
    – deong
    Commented Jun 20, 2017 at 14:18
  • 1
    $\begingroup$ Let's have it clear...try to make your question brief and kept in mind that every one understands it .fast $\endgroup$
    – quintumnia
    Commented Jun 20, 2017 at 16:08

3 Answers 3

Reset to default
6
$\begingroup$

i'm the main developer of Neataptic, a Javascript neuro-evolution library.

  1. Very effective! Realise that this is how real-life evolution happened as well: we kept on improving against other species, which forced them to improve as well.

  2. Very practical, especially if you don't want to set up any 'rules' like you say, it makes the genomes find out what the rules are themselves.

  3. Basically, you let each genome in the population play X games against other genomes, I advise you let each genome play against every other genome in the population. An example of scoring would be giving the genome 1 point for winning, and 0.25 or 0.5 for a tie. Each game should always have a result!

  4. I'm not sure about this one, as I haven't implemented speciation.

I want to give you some examples that I have worked on:

  • Agar.io AI (neuro-evolved neural agents) - basically, I let neural networks evolve to get the highest score they can in agar.io, by competing against each other! It worked better than I expected.

  • Currently i'm working on new project, a kind of 'cops and robbers' style game.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Awesome answer! (More links would be useful on the basic concepts, since I'm noticing a recent disconnect in that area due the growing accessibility of the methods.) I favor this approach because I can use guided learning to give my automata some basic axioms, but let their intelligence be a factor of self evolution, which hopefully leads to axioms they themselves discover. :) $\endgroup$
    – DukeZhou
    Commented Jun 20, 2017 at 20:40
  • $\begingroup$ I was going to post examples from Neataptic, but then I saw your answer sir, and I am not worthy :D Nice to e-meet you! $\endgroup$
    – Alexus
    Commented Mar 13, 2018 at 22:07
2
$\begingroup$

The general notion is that of 'Competitive Coevolution' and there are many (maybe hundreds) of academic papers that describe various alternatives.

The excellent (and freely available) Essentials of Metaheuristics has a whole chapter on the subject.

Improve this answer
$\endgroup$
0
$\begingroup$

Look up tournament selection Tournament selection is a method of selecting an individual from a population of individuals in a genetic algorithm.[1] Tournament selection involves running several "tournaments" among a few individuals (or "chromosomes") chosen at random from the population. The winner of each tournament (the one with the best fitness) is selected for crossover. Selection pressure, a probabilistic measure of a chromosome's likelihood of participation in the tournament based on the participant selection pool size, is easily adjusted by changing the tournament size[why?]. If the tournament size is larger, weak individuals have a smaller chance to be selected, because, if a weak individual is selected to be in a tournament, there is a higher probability that a stronger individual is also in that tournament.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .