Need help solving a problem with Genetic Algorithm

[Blueychan]

I have this program that simulate a soccer penalty kick between 2 teams.

-The goal is 24 x 8 with coordinate (0,0) at the bottom left corner.

-Each team has 5 kickers and 1 goalkeeper (for convenience, I'll call the 2 team Team A and Team B)

-Team A - there are 5 strategies for the kickers (one for each), and there are 5 strategies for the goalkeeper (because he need a strategy for each kicker on team B)

-Team B - there are 5 strategies for the kickers (one for each), and there are 5 strategies for the goalkeeper (because he need a strategies for each kicker in team A)

- Strategy for the kicker is the coordinate (x,y) and power value. The coordinate is the location of the kick and the power is how strong the kick is. ( I will explain more on the Power attribute later). For example each kicker input strategy would be like this: (1,2) 100 or (24,7) 25

- Strategy for the goalkeeper is a coordinate and a +Width and +Height values. The
goalkeeper coverage region is a rectangle whose bottom left corner is the (x,y) position and the top right corner is (x+width, y+height). For example, (3,4) 5 5 His bottom left coor is at (3,4) and (3+5,4+5) is his top right corner of the rectangle (coverage area).

- MAX RANGE OF COVERAGE AREA IS 25% OF GOAL AREA (the program will check this)

- Power: 0-24; kick will have no error; kick hit goalkeeper coverage area 100% save
Power: 24-49 kick will have 10% error (-/+10% wide of coor); 90% save
Power: 50-75 kick will have 20% error; 80% save
Power: 76-100 kick will have 30% error; 50% save

EXAMPLE INPUT: power must be 0-100, all other values must be positive integer with 0-(2^7-1)
TEAM A
kicker: (14,3) 25 goalkeeper: (2,3) 4 4
(3,5) 50 goalkeeper: (1,1) 5,5
and so on ...

TEAM B:
Kicker: (9,3) 75 goalkeeper: (1,2) 5 5
(3,13) 100 goalkeeper: (2,3) 6 6 (assuming this won't go over 25% of goal area
and so on ....

---------------------------------------------------------------------------------------

Now what I want to do is creating a Genetic Algorithm program to come up with the best team strategy possible to beat a random team strategy and a handcrafted team strategy. The GA program should accept: random generated population, crossover, and mutation as input and output the best possible strategy.

Right now I am not sure how to start and encode this to solve the problem. How would I represent the population. Any idea?

Thanks in advance

 

[degibson]

[snip] How would I represent the population. Any idea?

It sounds to me like your solution space is 'pick the best five kicker strategies' and 'pick the five best goalie strategies'.

Ergo, each member of the kicker-strategy population is an x/y coordinate pair and a power.
Each member of the goalie population is an x/y pair and a height/width pair.

Overall, the strings are a bit short -- (int,int,int) and (int,int,int,int), respectively -- but that's OK for a GA toy. The only thing a tad unusual is that your algorithm will spit out the N best solutions, rather than the single best solution (though that variant is not unheard of).

 

[Blueychan]

It sounds to me like your solution space is 'pick the best five kicker strategies' and 'pick the five best goalie strategies'.

Ergo, each member of the kicker-strategy population is an x/y coordinate pair and a power.
Each member of the goalie population is an x/y pair and a height/width pair.

Overall, the strings are a bit short -- (int,int,int) and (int,int,int,int), respectively -- but that's OK for a GA toy. The only thing a tad unusual is that your algorithm will spit out the N best solutions, rather than the single best solution (though that variant is not unheard of).

I am thinking maybe save the best strategy after each run and after n runs, sort the saved strategies and pick the best 5?

Either way, I am thinking that for just finding the kicker or goalkeeper strategies and not both at the same time. I don't know how to encode both.

 

[Blueychan]

It sounds to me like your solution space is 'pick the best five kicker strategies' and 'pick the five best goalie strategies'.

Ergo, each member of the kicker-strategy population is an x/y coordinate pair and a power.
Each member of the goalie population is an x/y pair and a height/width pair.

Overall, the strings are a bit short -- (int,int,int) and (int,int,int,int), respectively -- but that's OK for a GA toy. The only thing a tad unusual is that your algorithm will spit out the N best solutions, rather than the single best solution (though that variant is not unheard of).

How do you go about representing the population suppose the algorithm will only spit out the best solution insteal of the N best solutions?

 

[degibson]

A single solution (i.e., a kick) will look something like this:

class Kick {
public:
  int x;
  int y;
  int power;
};

 

[CycloWizard]

I am thinking maybe save the best strategy after each run and after n runs, sort the saved strategies and pick the best 5?

Generally in a GA, you will maintain several distinct "chromosomes" or "genomes" (or whatever you like to call the parameter function). All of the chromosomes from one generation are in hand at the end of the computation of the objective function, so it's trivial to see which are the best. Most GA's allow for the passage of a specified number of "elite" chromosomes to pass through to the next generation unmodified by mutation, mating, and so on.

Either way, I am thinking that for just finding the kicker or goalkeeper strategies and not both at the same time. I don't know how to encode both.

Yes, it is probably best to solve the problem uncoupled. You could also take advantage of the symmetry of the problem to reduce the search space, depending on your application.

 

[Schmide]

It doesn't really seem all that genetic, more statistical based problem based on weighted permutations. If you think of it as a card game, you have a power card and a position card each varying the chances of success or failure.

The kicker is basically choosing a coordinate

1 in 192 position

While the goalkeeper is choosing a rectangle such that it covers at most 192*0.25 = 48 blocks. The odd part comes from using an integer system with a floating point restriction. This causes an error term if the goalkeeper was to choose a non divisible side. (i.e. 17 causes a 29% round off error) Avoiding this the goalkeeper is basically choosing 48 squares to block. This is a point where a handcrafted strategy avoiding 5, 7, 9, 10, 11, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23 would have give an ~8% average more area giving a 1% better chance of a block. (I averaged all the error terms )

All terms aside the goalkeeper blocks a kick 24-25% of the time in a pure random sample.

Reducing the Kick chances on purely random samples.

Power: 0-24; kick will have no error; kick hit goalkeeper coverage area 100% save

100% * 100% * 75% = 75% success rate

Power: 24-49 kick will have 10% error (-/+10% wide of coor); 90% save

90% * 90% * 75% = 60% success rate

Power: 50-75 kick will have 20% error; 80% save

80% * 80% * 75% = 48% success rate

Power: 76-100 kick will have 30% error; 50% save

70% * 50% * 75% = 26% success rate.

If I were a kicker, I'd choose low power all the time on a purely random sample.

 

[CycloWizard]

It doesn't really seem all that genetic, more statistical based problem based on weighted permutations. If you think of it as a card game, you have a power card and a position card each varying the chances of success or failure.

The kicker is basically choosing a coordinate

1 in 192 position

While the goalkeeper is choosing a rectangle such that it covers at most 192*0.25 = 48 blocks. The odd part comes from using an integer system with a floating point restriction. This causes an error term if the goalkeeper was to choose a non divisible side. (i.e. 17 causes a 29% round off error) Avoiding this the goalkeeper is basically choosing 48 squares to block. This is a point where a handcrafted strategy avoiding 5, 7, 9, 10, 11, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23 would have give an ~8% average more area giving a 1% better chance of a block. (I averaged all the error terms )

All terms aside the goalkeeper blocks a kick 24-25% of the time in a pure random sample.

Reducing the Kick chances on purely random samples.

Power: 0-24; kick will have no error; kick hit goalkeeper coverage area 100% save

100% * 100% * 75% = 75% success rate

Power: 24-49 kick will have 10% error (-/+10% wide of coor); 90% save

90% * 90% * 75% = 60% success rate

Power: 50-75 kick will have 20% error; 80% save

80% * 80% * 75% = 48% success rate

Power: 76-100 kick will have 30% error; 50% save

70% * 50% * 75% = 26% success rate.

If I were a kicker, I'd choose low power all the time on a purely random sample.

As a life-long soccer player, I think the problems are really better stated as:
1. Given a specific goalkeeper (and his guessing patterns based on previous observations), find the shooting strategy which will maximize the total number of goals scored.
2. Given a specific opponent's PK shooting patterns (again based on previous observations), find the goalkeeping strategy which will minimize the total number of goals scored.

This could be addressed by computing the highest probability for each shooter:goalie pair under all possible conditions, but then this is really just an exhaustive search approach to optimization. Thus, the GA is a reasonable approach to solving this sort of problem in an approximate sense with significantly lower CPU time than would be required for the full exhaustive search solution (the GA solution won't necessarily be optimal, since GA is not a deterministic optimization method). My guess is that this is a homework problem to write a basic GA, and it's a pretty good exercise for that I think.

 

[Blueychan]

Thank you guys, there are some great ideas here. Unfortunately most are not what I am looking for and it was my fault because I didn't explain clearly what it is that I needed help on (due to the fact I was looking to solve the problem at the wrong angle).

Let simplify the problem so everyone can conceptionalize it:

Inputs:
-population (random creation of n team, for ex. if n=5, 5 random teams are created with each team's attribute include 5 kickers' strats, 5 goalkeeper strats)

Output:
-best team strategy (each team will play each other and the best is selected for the next iteration, remember each team has 5 kickers' strats, 5 goalkeeper strats)

So I am looking for 1 solution afterall in a field of n population

--------------------------------------------------------------------

Now my problem is how to encode the teams as chromosomes. Is it a good idea to represent the team with bit string, but wouldn't it be too many attributes in a team to account for them for in bit string? If I encode team as integer [x,y,power,x,y,w,h], how would I do crossover or mutation on this type of encoding?

I am just trying to gather ideas so I have somewhere to start.

Thanks in advance

 

[iCyborg]

I think CycloWizard's post still gives a fair idea of what to do. It also looks to me that if there are no differences between players and GKs (like perhaps accuracy rates vs power should differ, some are inherently better shooters than others, or bigger reach for GKs), then e.g. for a specific GK they should all have the same "best" strategy, right?

Your attempt to clarify isn't doing that for me due to inappropriate usage of the word population in the context of GA (and how I believe others are using it here). If you're looking for the best strategy, then a population (in GA) would be a set of strategies in some representation from which you pick the best one or ones and which is updated during iterations, not a set of n teams.

As for the encoding, I think the standard approach is to look at it as bit arrays/strings and it doesn't look very big to me, I'd even say it's more on the small side.