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.

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

    A := nStrats random strategies;
    B := nStrats random strategies;
        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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.