I would agree that genetic algorithms (GA) is good way to go. In short, these types of algorithms simulate Darwinian evolution. In general, GA is not very computationally intensive.
You'll need to come up with a set of parameters (genes) that guide an AI's behavior. The first AIs that a player encounters will have these parameters set to values that provide descent behavior. The parameters for each instance of the AI in this first generation should vary a bit.
Next, you'll need to come up with a function which scores how well a particular AI performs. This score might take into account how much damage the AI caused the player, and if the AI survived the round. This score is known as the "objective function" in GA.
After each round, the genes for the best scoring AIs are mated to create a new generation of AIs. There are many ways to mate individuals, and will depend upon the genes, and the tradeoff between how quickly you want the AIs to evolve, and how much the game can tolerate malfunctioning AIs.
Check out some of the resources on GA, and write back if you want to discuss more.