2

I have a simple zero sum, discrete, deterministic, complete information board game. I want to machine learn an evaluation function for an AI agent.

Suppose each board state has ~20 identifiable features which could be weighted to form an evaluation function.

Suppose the time constraint for both players is 15 seconds for all moves in the entire game, so each game takes up to 30 seconds.

It seems to me that a naive approach would be to endlessly cycle through each of the features, creating agents with a small increment/decrement to the feature weighting and playing them against each other.

Create agent(N=0) with uniform or random weightings

While (Brendan hasn't stopped the program)

    For each F in features

       Clone agent(N) -> agent(N+1), with increased weighting of F
       Clone agent(N) -> agent(N+2), with decreased weighting of F
       Play ~20 games of agent(N+1) vs agent(N+2)

       If one agent was clearly stronger (eg. won 60%+?), then 
           N <- [the stronger agent]

Then let this run continuously for a long time. The final agent[N] will hopefully have a strong set of weightings.

This seems inefficient because for 20 games with 20 features with 30 second games, it will take several hours to complete a single iteration of the main loop.

What is a more sophisticated algorithm?

Are there generic Java implementations of such machine learning algorithms which would work for training a game playing agent?

4

This is a good candidate for Differential Evolution.

DE is a very simple (but powerful) population based, stochastic function minimizer/maximizer.

A key point for integrating DE in your scheme is the fitness function:

double fitness(Agent_k)
   fit = 0

   repeat M times
      randomly extract an individual Agent_i (i <> k)

      switch (result of Agent_k vs Agent_i)
         case Agent_k wins:   fit = fit + 1
         case Agent_i wins:   fit = fit - 2
         case draw:           fit doesn't change

   return fit

I.e. an agent plays against M randomly selected opponents from the population (with replacement but avoiding self match).

The parameter M is important: large values give a precise measurement, small values could prevent convergence. I would start with M=5 (a value used in some chess-related experiments).

A sketch of the search is:

Create a population of N agents with random weights

While (Brendan hasn't stopped the program and
       population diversity is greater than a given threshold)

   randomly select Agent_b

   randomly select Agent_i (i <> b)
   randomly select Agent_j (j <> i and j <> b)
   randomly select Agent_k (k <> j and k <> i and k <> b)

   Agent_m = Agent_i + F (Agent_j - Agent_k)

   Agent_child = crossover(Agent_b, Agent_m)

   if (fitness(Agent_child) > fitness(Agent_b)
      replace Agent_b with Agent_child

This is a steady state population approach (the alternative is a generational approach; further information in Essentials of Metaheuristics by Sean Luke).

For more details about how DE works take a look at:

DE will drive the search towards promising areas of the feasible space (without performing a systematic search as in your code).

Anyway this kind of optimization may easily require several days.

The official page of DE has implementations in many languages (also Java).


I would expect "crossover" to average out the parent function weightings, but how does the variation arise?

In DE there's a "blend" of mutation and crossover.

A view of the DE's mutation scheme

(in the picture Agent_j = Xa, Agent_k = Xb, Agent_i = Xc. DE's mutation scheme, crossover not shown)

Traditional Evolutionary Strategies mutated vectors by adding zero-mean Gaussian noise to them but, to remain efficient, the mutation scheme had to adjust the standard deviation of the Gaussian noise to suit each parameter (this is also a function of time).

DE use a vector differential Xa - Xb, in place of Gaussian noise, to "perturb" another vector Xc:

Xc_ = Xc + F * (Xa - Xb)

F (differential weight) is a user-supplied scaling factor in the [0.1, 1.2] range.

This form of mutation (with population derived-noise) ensures that the search space is efficiently searched in each dimension.

For example, if the population becomes compact in one dimension, but remains widely dispersed along another, the differentials sampled from it will be small in one dimension yet large in the other. Whatever the case, step sizes will be comparable to the breadth of the region they are being used to search, even as these regions expand and contract during the course of evolution.

(from Dr.Dobb's Journal # 264 April 1997 pg. 22, "Differential Evolution" by K. Price and R. Storn)

Xc_ (Agent_m in the pseudo-code) is used to produce a trial vector via crossover with a random individual (Xi below, Agent_b in the pseudo-code):

Xt = crossover(Xi, Xc_)

The crossover operator produces an offspring by a series of binomial experiments: in this way it's established which parent contributes which trial vector parameter.

The best between Xt and Xi (Agent_child and Agent_b) survives.

  • Thanks for the suggestion I will investigate. How exactly are variations of the evaluation function weightings generated? I would expect "crossover" to average out the parent function weightings, but how does the variation arise? – Brendan Hill May 6 '16 at 5:25
  • @BrendanHill I've added some explanations to the answer. I hope it's clear enough. – manlio May 6 '16 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.