How would I go about coding this Genetic Algorithm?

Question

I would like to code a genetic algorithm that learns to play a game similar to Tetris. The game itself is relatively simple; I have written the full behaviour of it below.

The game:

• Grid based, 12x16.
• You must clear blocks from the grid.
• A row of new blocks is added every 5 ticks, to the bottom, pushing the blocks up.
• You can only clear clusters of the same type block.
• The number of types of block increases as the game goes on.
• You can only clear clusters of 3 or above.
• For every cluster cleared, (CLUSTER_SIZE - 3)^2 is added to BLOCK_SCORE.
• After a cluster has been removed from the grid, blocks above slide down to fill the gaps, and if there are any horizontal gaps (On the bottom row) after this, the left side of the gap moves over to fill it.
• The goal of this game is to survive as long as possible. Time is measured in ticks, or the number of moves that you have made.
• Your score (or Fitness) is determined by (TIME_ALIVE * BLOCK_SCORE)
• The game is over once a block reaches the top of the grid.

The score of this game incorporates both longevity and efficiency. The larger the clusters that you clear, the higher the fitness is.

I have coded a few GAs now, but they have been based on local competition, things like collection goals and the like, VS other individuals. My problem is that I don't know how to approach this problem. Each different individual of this new GA should have only the current grid to work on as input. (At least, that's what I think would be needed)

How can I begin to code the GA for this? I cannot for the life of me work it out.

.

Thanks all,

Steffan 'Ruirize' James

Answer 1

Each individual in your population would represent a game played to completion. The attributes of each individual would be parameters necessary to define a given strategy for placing the blocks down. I'm assuming you have a couple of different heuristics for placing a block. One example of a strategy would be to select a heuristic at random from the available strategies so your attributes would be a set of probabilities that a given heuristic is chosen. Can you provide more information on the block k placement heuristic you have?

Answer 2

An alternative encoding might involve:

for each possible move
  set phenotypeBehavior to 0
  calculate the post-move position 
  foreach block cleared add a perBlockClearedEmphasis value to phenotypeBehavior
  foreach column add a perColumnHeightEmphasis value to your phenotypeBehavior
  foreach cluster of size x, add a clusterSizeXEmphasis value to your phenotypeBehavior
choose the move that produces the highest phenotypeBehavior

Encode the various _foo_Emphasis values genetically and evolve them. Presumably, for instance, perBlockClearedEmphasis will drive towards high values, while your heuristic "height is bad" will drive perColumnHeightEmphasis to be negative, and clusterSizeXEmphasis will be negative for small X and positive for larger X.

In the most general sense, this is suggesting that your genetic structure describe a declarative, but highly-parameterized, program.