OI-Public-LIbrary/APIO2012-莫涛教你玩游戏/install/选手开发包/client_gcc/clientAI_usehistory.cpp

#include "clientAI.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;

class simplex {
private:
    static const int maxsize = 12;
    static const double inf = 1e70;
    static const double eps = 1e-13;
    double a[maxsize][maxsize], a2[maxsize][maxsize];
    double b[maxsize], b2[maxsize], q[maxsize], c[maxsize];
    int n, nn[maxsize], bb[maxsize];
    double u, min;

private:
    int getpos()
    {
        int ret = 0;
        double max = 0;
        for (int i = 1; i <= n; ++i)
            if (c[i] > max) {
                max = c[i];
                ret = i;
            }
        return ret;
    }

    void pivot(int e, int l)
    {
        for (int i = 1; i <= n; ++i)
            b2[i] = b[i];
        b2[l] = b[l] / a[l][e];
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                a2[i][j] = a[i][j];
        for (int j = 1; j <= n; ++j)
            if (j != e)
                a2[l][j] = a[l][j] / a[l][e];
        a2[l][e] = 1 / a[l][e];
        for (int i = 1; i <= n; ++i)
            if (i != l) {
                b2[i] = b[i] - a[i][e] * b2[l];
                for (int j = 1; j <= n; ++j)
                    if (j != e)
                        a2[i][j] = a[i][j] - a[i][e] * a2[l][j];
                a2[i][e] = -a[i][e] / a[l][e];
            }
        u += c[e] * b2[l];
        swap(nn[e], bb[l]);
        for (int j = 1; j <= n; ++j)
            if (j != e)
                c[j] -= c[e] * a2[l][j];
        c[e] = -c[e] / a[l][e];
        for (int i = 1; i <= n; ++i) {
            b[i] = b2[i];
            for (int j = 1; j <= n; ++j)
                a[i][j] = a2[i][j];
        }
    }

public:
    simplex(vector< vector<double> > p)
    {
        memset(a, 0, sizeof(a));
        memset(a2, 0, sizeof(a2));
        memset(b, 0, sizeof(b));
        memset(b2, 0, sizeof(b2));
        memset(q, 0, sizeof(q));
        memset(c, 0, sizeof(c));
        memset(nn, 0, sizeof(nn));
        memset(bb, 0, sizeof(bb));
        u = min = 0;
        n = p.size();
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                a[i][j] = -p[j - 1][i - 1];
    }

    vector<double> calc()
    {
        min = -1;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (a[i][j] - 1 < min)
                    min = a[i][j] - 1;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                a[i][j] -= min;
        for (int i = 1; i <= n; ++i) {
            bb[i] = n + i;
            b[i] = 1;
        }
        for (int i = 1; i <= n; ++i) {
            nn[i] = i;
            c[i] = 1;
        }
        int e = getpos();
        double k, t;
        while (e > 0) {
            k = inf;
            int l = 0;
            for (int i = 1; i <= n; ++i)
                if (a[i][e] > eps) {
                    t = b[i] / a[i][e];
                    if (t < k) {
                        k = t;
                        l = i;
                    }
                }
            //assert(l != 0);
            pivot(e, l);
            e = getpos();
        }
        vector<double> ret(n, 0);
        for (int i = 1; i <= n; ++i)
            if (bb[i] <= n)
                ret[bb[i] - 1] = b[i] / u;
        ret.push_back(-(min + 1 / u));
        return ret;
    }
};

const double p[100][8] = {
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000},
{0.326214077,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.673785923},
{0.360759516,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.639240484},
{0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000},
{0.000000000,0.234699425,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.765300575},
{0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.430972608,0.000000000,0.000000000,0.569027392},
{0.186779202,0.000000000,0.000000000,0.000000000,0.518296112,0.000000000,0.000000000,0.294924685},
{0.247984354,0.000000000,0.000000000,0.000000000,0.526573867,0.000000000,0.000000000,0.225441779},
{0.195828207,0.000000000,0.212775315,0.000000000,0.485008821,0.000000000,0.000000000,0.106387657},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.508864848,0.000000000,0.491135152},
{0.000000000,0.170392972,0.000000000,0.000000000,0.000000000,0.560620915,0.000000000,0.268986113},
{0.000000000,0.160958296,0.268899318,0.000000000,0.000000000,0.475152201,0.000000000,0.094990184},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.360759516,0.000000000,0.000000000,0.639240484},
{0.188429176,0.000000000,0.000000000,0.000000000,0.558420581,0.000000000,0.000000000,0.253150243},
{0.000000000,0.212766115,0.000000000,0.000000000,0.426795483,0.000000000,0.000000000,0.360438402},
{0.040984904,0.153643979,0.127244302,0.000000000,0.501479928,0.000000000,0.000000000,0.176646887},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.471944192,0.000000000,0.528055808},
{0.000000000,0.208009580,0.000000000,0.000000000,0.000000000,0.485924068,0.000000000,0.306066352},
{0.000000000,0.220388626,0.130209468,0.000000000,0.000000000,0.496664921,0.000000000,0.152736986},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000},
{0.121611094,0.000000000,0.000000000,0.000000000,0.291573724,0.243222189,0.000000000,0.343592993},
{0.247887510,0.002852454,0.000000000,0.000000000,0.132786242,0.319611965,0.000000000,0.296861829},
{0.000000000,0.000000000,0.351552849,0.000000000,0.000000000,0.351552849,0.000000000,0.296894302},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000},
{0.000000000,0.313924586,0.000000000,0.000000000,0.000000000,0.338534720,0.000000000,0.347540695},
{0.000000000,0.000000000,0.406570036,0.000000000,0.000000000,0.316845991,0.000000000,0.276583973},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000},
{0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000},
{0.353637024,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.646362976},
{0.471944192,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.528055808},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000},
{1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000},
{0.000000000,0.346113151,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.653886849},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000},
{0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.234699425,0.000000000,0.000000000,0.765300575},
{0.199880553,0.000000000,0.000000000,0.000000000,0.477441742,0.000000000,0.000000000,0.322677705},
{0.276066172,0.000000000,0.000000000,0.000000000,0.547303276,0.000000000,0.000000000,0.176630552},
{0.000000000,0.000000000,0.160665079,0.000000000,0.525410335,0.000000000,0.000000000,0.313924586},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.346113151,0.000000000,0.653886849},
{0.000000000,0.221542882,0.000000000,0.000000000,0.000000000,0.470683420,0.000000000,0.307773698},
{0.000000000,0.249140538,0.000000000,0.000000000,0.000000000,0.529316580,0.000000000,0.221542882},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000},
{0.094990184,0.000000000,0.000000000,0.000000000,0.234699425,0.306676138,0.000000000,0.363634253},
{0.199915278,0.000000000,0.000000000,0.000000000,0.228805623,0.308153870,0.000000000,0.263125229},
{0.000000000,0.000000000,0.300801436,0.000000000,0.000000000,0.370814689,0.000000000,0.328383875},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000},
{0.000000000,0.264658290,0.000000000,0.000000000,0.000000000,0.437714865,0.000000000,0.297626844},
{0.000000000,0.000000000,0.333333333,0.000000000,0.000000000,0.333333333,0.000000000,0.333333333},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{1.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000},
{0.000000000,0.000000000,0.000000000,1.000000000,0.000000000,0.000000000,0.000000000,0.000000000}
};

const double f[100] = {
0.500000000,0.784513696,0.922261265,1.000000000,1.000000000,
0.690258965,0.927303957,1.000000000,1.000000000,1.000000000,
0.215486304,0.500000000,0.680185803,0.878388906,1.000000000,
0.351248523,0.690258965,0.905009816,1.000000000,1.000000000,
0.077738735,0.319814197,0.500000000,0.749260036,1.000000000,
0.165769701,0.543423024,0.800084722,1.000000000,1.000000000,
0.000000000,0.121611094,0.250739964,0.500000000,1.000000000,
0.000000000,0.313924586,0.597484603,1.000000000,1.000000000,
0.000000000,0.000000000,0.000000000,0.000000000,0.500000000,
0.000000000,0.000000000,0.000000000,0.690258965,0.927303957,
0.309741035,0.648751477,0.834230299,1.000000000,1.000000000,
0.500000000,0.826943425,1.000000000,1.000000000,1.000000000,
0.072696043,0.309741035,0.456576976,0.686075414,1.000000000,
0.173056575,0.500000000,0.735341710,1.000000000,1.000000000,
0.000000000,0.094990184,0.199915278,0.402515397,1.000000000,
0.000000000,0.264658290,0.500000000,1.000000000,1.000000000,
0.000000000,0.000000000,0.000000000,0.000000000,0.309741035,
0.000000000,0.000000000,0.000000000,0.500000000,0.826943425,
0.000000000,0.000000000,0.000000000,0.000000000,0.072696043,
0.000000000,0.000000000,0.000000000,0.173056575,0.500000000
};

const int stateNum = 100;
const int actionNum = 8;

const int Dmp[2][actionNum] = {{-1, -2, -3, -4, 0, -1, -2, 1},
                               {-5, -1, -2, -3, -5, 0, -5, 1}};

int cntRand, randNum[100000];
int e[stateNum][actionNum][actionNum];
int win[stateNum], lose[stateNum];
vector<int> history;
int Set, cntlose;
bool useHistory;

int calc(int mymp, int mylv, int opmp, int oplv, ACTION myact, ACTION opact)
{
    bool myerr = mymp + Dmp[mylv][myact] < 0;
    bool operr = opmp + Dmp[oplv][opact] < 0;
    if (myerr && operr) return -3;
    if (myerr) return -4;
    if (operr) return -5;
    if (myact < 4 && opact < 4) {
        if (myact > opact) return -1;
        if (myact < opact) return -2;
    }else {
        if (myact < 2 && opact >= 6) return -1;
        if (myact == ATTACK_3 && opact != DEFEND_2) return -1;
        if (myact == ATTACK_4) return -1;
        if (opact < 2 && myact >= 6) return -2;
        if (opact == ATTACK_3 && myact != DEFEND_2) return -2;
        if (opact == ATTACK_4) return -2;
    }
    mymp += Dmp[mylv][myact];
    if (myact == RAMPAGE) ++mylv;
    opmp += Dmp[oplv][opact];
    if (opact == RAMPAGE) ++oplv;
    if (mymp > 4) mymp = 4;
    if (opmp > 4) opmp = 4;
    return mymp + mylv * 5 + opmp * 10 + oplv * 50;
}

void init(int totalSet) {
	srand(((time(NULL)) + 5) % 10000);
	cntRand = 0;
	for (int i = 0; i < 100000; i ++)
		randNum[i] = (rand() + rand() + rand() + rand()) % 10000;
    useHistory = false;
    cntlose = 0;
    memset(win, 0, sizeof(win));
    memset(lose, 0, sizeof(lose));
    for (int i = 0; i < stateNum; ++i)
        for (int j = 0; j < actionNum; ++j)
            for (int k = 0; k < actionNum; ++k)
                e[i][j][k] = calc(i % 5, i % 10 / 5, i / 10 % 5, i / 50, (enum ACTION)j, (enum ACTION)k);
}

void beginSet(int cntSet) {
    Set = cntSet;
    history.clear();
}

void endSet(int result) {
    if (result == 2) {
        ++cntlose;
        if (cntlose == 2) {
            useHistory = !useHistory;
            cntlose = 0;
        }
    }else
        cntlose = 0;
        
    for (int i = 0; i < history.size(); ++i) {
        if (result == 0 || result == 1)
            ++win[history[i]];
        if (result == 0 || result == 2)
            ++lose[history[i]];
    }
}

ACTION getAction(int cntRound, int myMP, int myState, int opMP, int opState, ACTION opAction)
{
    if (myMP > 4) myMP = 4;
    if (opMP > 4) opMP = 4;
    int S = myMP + myState * 5 + opMP * 10 + opState * 50;
    history.push_back(S);
    double P = randNum[cntRand++] * 10000 + randNum[cntRand++] + 1;
    //probs: when to use the study strayge
    if (useHistory) {
        vector< vector<double> > c(actionNum, vector<double>(actionNum, 0));
        for (int i = 0; i < actionNum; ++i)
            for (int j = 0; j < actionNum; ++j) {
                int k = e[S][i][j];
                if (k >= 0)
                    if (win[k] > 0 && lose[k] > 0)
                        c[i][j] = sqrt(f[k] * win[k] / (win[k] + lose[k]));
                    else
                        c[i][j] = f[k];
                else
                if (k == -1 || k == -5)
                    c[i][j] = 1;
                else
                    c[i][j] = 0;
            }
        vector<double> ret = simplex(c).calc();
        for (int i = 0; i < actionNum; ++i) {
            P -= 1e8 * ret[i];
            if (P <= 0 && myMP + Dmp[myState][i] >= 0) return (enum ACTION)(i);
        }
    }else
        for (int i = 0; i < 8; ++i) {
            P -= 1e8 * p[S][i];
            if (P <= 0 && myMP + Dmp[myState][i] >= 0) return (enum ACTION)(i);
        }
    return RESTORE;
}