1
$\begingroup$

I am developing a program which seeks strategies for the players A, B in any of a family of simple 2-player gambling-games. The program iterates, using a genetic algorithm to determine, from the current iteration's results, the strategies which are to play one another in the next iteration.

Below I give an overview of my algorithm. Although I've used pseudocode, I am not asking about how to code an algorithm; rather, I would like to learn what the algorithm should contain.

main
{
    Strategy A[], B[];
    input nIters, nStrats, maxTweak, gameRules;

    A := nStrats random strategies;
    B := nStrats random strategies;
    for(t=1..nIters)
    {
        make each A play each B;
        for each A and each B
            its total score := sum of its scores in its individual games;
        sort the A's by total score;
        sort the B's by total score;
        v := the game's bias in favour of the best A;
        write v;
        evolveStrategies(A, nStrats, maxTweak);
        evolveStrategies(B, nStrats, maxTweak);
    }
}

evolveStrategies(X, nStrats, maxTweak)
{
    keep the best few Xs where they are;
    for(each of the others X[i])
    {
        j := index of one of the best Xs;
        X[i] := X[j];
        tweak the value of each parameter of X[i] by no more than maxTweak;
    }
}

The nature of the game is that there is (with best play by A and B) a bias (positive or negative) in favour of A. Its value $V$ is what it is when A's and B's strategies are those at a Nash equilibrium. Let $v$ be my program's estimate of $V$. Ideally my iterations' successive values of $v$ would converge to $V$. For some games in the relevant family, I happen to know what $V$ is; for others, I don't.

The trouble I find is that even if maxTweak is very small, the succession of $v$-values written shows oscillation with an amplitude much larger than maxTweak. Choosing a suitably large number of iterations shows that the oscillation, after an initial large rise and fall, is hardly damped if at all. For example on a simple game, maxTweak=$4\times10^{-6}$ gives an initial large rise and fall, then oscillation with amplitude, peak to peak, $\approx 0.2$ and period $\approx 500000$ iterations.

One solution is to reduce maxTweak. But this entails using many more iterations, and thus more CPU time. A more radical change to my approach is needed.

Given that, a priori, the program does not know the oscillation's period or the limit value, how can my program detect the oscillation and deal with it (e.g. damp it)?

If $v$ varied as undamped simple harmonic motion, plus a constant, then $\frac{dv}{dt}$ varies as undamped simple harmonic motion about 0, so $\frac{d^3 v}{dt^3} \propto -\frac{dv}{dt}$. Since the tweaking is random, there will be small-scale oscillations due to that, as well as the larger-scale oscillation. So it seems that attempts to find higher-order derivatives of $v$ as a function of $t$ will fail.

I tried estimating the first and second derivatives $\frac{dv}{dt}$ and $\frac{d^2 v}{dt^2}$ by maintaining exponentially-weighted averages of $v$ and my estimate of $\frac{dv}{dt}$. Based on the sign of my estimate of $\frac{d^2 v}{dt^2}$ I evolved just A or B. This increased the number of iterations during $v$'s initial large rise and fall, but the following oscillation was as large and undamped as before.

One idea is to start maxTweak at a value which is not small, and adaptively reduce it. But in deciding (at each iteration) whether to reduce it or not, what should I be looking for?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.