#include <fstream.h>

#include <string.h>

#include <stdlib.h>

#include <iostream.h>

//A state type is just an array of 9 integers, 1=x 2=o

struct state { int b[9]; };

typedef char string[200];

//Level to search in Minimax

int mm_level = 2;

//=========Standard weights and best weights used in Minimax

//Weight 0: Number of rows with 2 of your mark - num row 2 of his

float w0 = 0; float b0 = 0;

//Weight 1: Number of rows with 3 of your mark - num row 3 of his

float w1 = 0; float b1 = 0;

//Weight 2: Center square is yours = 1, his = -1, none = 0

float w2 = 0; float b2 = 0;

//Weight 3: Number of corners yours - number of corners his

float w3 = 0; float b3 = 0;

//Weight 4: Number of rows with 1 of your mark - num row 1 of his

float w4 = 0; float b4 = 0;

//Best number of matched boards

int bestmatch = -1;

//Number of trys

long trys = 0;

//increment for weights

float incr = 1;

//Ranges to check on the variables

float min4, max4;

float min3, max3;

float min2, max2;

float min1, max1;

float min0, max0;

//Number of board configs in file

int checkNum = 0;

//Best next move

int bestmv = 0;

state bestst;

//File that has board configurations

ifstream fin("create.dat");

//Board configurations

string perfect[1000];

//-=-=-Function Prototypes-=-=-=-

float minimax(int,float,int,state,int);

state getState(int);

char* best_move(int,state);

void takesOn(state*,state*);

state next_ith_state(state,int);

int diff(state);

//-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

int main(int argc, char *argv[]) {

//Open the database of moves and store them into an array

while (!fin.eof())

{ fin >> perfect[checkNum];

checkNum++;}

fin.close();

//Depth of Minimax Search

cout << "Enter minimax Level:";

cin >> mm_level;

cout << "Min 4:"; cin >> min4; cout << "Max 4:"; cin >> max4;

cout << "Min 3:"; cin >> min3; cout << "Max 3:"; cin >> max3;

cout << "Min 2:"; cin >> min2; cout << "Max 2:"; cin >> max2;

cout << "Min 1:"; cin >> min1; cout << "Max 1:"; cin >> max1;

cout << "Min 0:"; cin >> min0; cout << "Max 0:"; cin >> max0;

state start;

for(w4 = min4; w4 <= max4; w4++)

for(w3 = min3; w3 <= max3; w3++)

for(w2 = min2; w2 <= max2; w2++)

for(w1 = min1; w1 <= max1; w1++)

for(w0 = min0; w0 <= max0; w0++) {

//Total matched is initialized

int total_correct =0;

//Go through the transitions

for(int i = 0; i < checkNum; i++)

{takesOn(&start,&getState(i));

if (diff(start) == 0)

{minimax(1,-999,mm_level,start,1);}

else

{minimax(0, 999,mm_level,start,2);}

if (best_move(i,bestst) != 0)

// Add in the below line if we want to represent diff. boards

// { total_correct = total_correct + (perfect[i][0]-'0');}

{ total_correct++;}

}

//---Output results---

if (trys % 100 == 0)

{int total = (max4 -min4+1)*(max3-min3+1)*(max2-min2+1)*(max1-min1+1);

total = total * (max0- min0+1);

total++;

cout << "Try " << trys << " (%"<< (100*trys)/total << ")";

cout << " got " << total_correct<<endl; }

if (total_correct > bestmatch)

{bestmatch = total_correct;

cout << "Best so far @ " << total_correct << " --> ";

cout << w0 << "," << w1 << "," << w2 << "," << w3 << "," << w4 << endl;

b0 = w0; b1 = w1; b2 = w2; b3 = w3; b4 = w4; }

trys++;

} //end for all weights loop

//Output the best reading

cout << "---------------------------" << endl;

cout << "Best reading" << endl;

cout <<b0<<","<<b1<<","<<b2<<","<<b3<<","<<b4<< endl;

cout <<"Best:"<<bestmatch<<endl;

return 1;

}

//-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

//-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

//Returns the number of x's minus the number of o's

int diff(state s) {

int dif = 0;

for(int i = 0; i < 9; i++)

{if (s.b[i] == 1) dif++;

if (s.b[i] == 2) dif--;}

return dif;}

//Checks if the state is terminal

int checkdone(state s) {

if (s.b[0] != 0 && s.b[0] == s.b[1] && s.b[1] == s.b[2]) {return 1;}

if (s.b[3] != 0 && s.b[3] == s.b[4] && s.b[4] == s.b[5]) {return 1;}

if (s.b[6] != 0 && s.b[6] == s.b[7] && s.b[7] == s.b[8]) {return 1;}

if (s.b[0] != 0 && s.b[0] == s.b[3] && s.b[3] == s.b[6]) {return 1;}

if (s.b[1] != 0 && s.b[1] == s.b[4] && s.b[4] == s.b[7]) {return 1;}

if (s.b[2] != 0 && s.b[2] == s.b[5] && s.b[5] == s.b[8]) {return 1;}

if (s.b[0] != 0 && s.b[0] == s.b[4] && s.b[4] == s.b[8]) {return 1;}

if (s.b[6] != 0 && s.b[6] == s.b[4] && s.b[4] == s.b[2]) {return 1;}

int total = 0;

while (total < 9 && s.b[total] != 0)

{total++;}

if (total == 9)

{return 1;}

return 0;}

//Returns the number of next possibles moves from the state

int nextPos(state s)

{ int totalfree = 0;

for(int i = 0; i < 9; i++)

{if (s.b[i] == 0) {totalfree++;}}

return totalfree; }

//equivalent to state a = state d

void takesOn(state* a, state* d)

{ for(int i = 0; i < 9; i++)

{(*a).b[i] = (*d).b[i];} }

//Returns the next ith state from state s

state next_ith_state(state s, int i)

{ state ret;

takesOn(&ret,&s);

int l = -1;

int xs = 0;

int os = 0;

for(int j = 0; j < 9; j++)

{if (ret.b[j] == 1) {xs++;}

if (ret.b[j] == 2) {os++;}}

while(i != 0)

{l++;

while(ret.b[l] != 0) {l++;}

i--; }

//l--;

if (xs == os) {ret.b[l] = 1;} else {ret.b[l] = 2;};

return ret;

}

//Calculates the h function for a player

float h(state s, int player) {

int opp = 2;

if (player == 2)

{opp = 1;}

int gene0 = 0;

int gene1 = 0;

int gene2 = 0;

int gene3 = 0;

int gene4 = 0;

int your_marks = 0; int opp_marks = 0; int nones = 0;

//check rows and columns

for(int i = 0; i < 3; i++)

{//====Check Rows

your_marks = 0; opp_marks = 0; nones = 0;

for(int x = 0; x < 3; x++)

{if (s.b[i*3+x] == player) your_marks++;

if (s.b[i*3+x] == opp ) opp_marks++;

if (s.b[i*3+x] == 0 ) nones++;}

if (your_marks == 2 && nones == 1) gene0++;

if (opp_marks == 2 && nones == 1) gene0--;

if (your_marks == 3) gene1++;

if (opp_marks == 3) gene1--;

if (your_marks == 1 && nones == 2) gene4++;

if (opp_marks == 1 && nones == 2) gene4--;

//====Check Columns

your_marks = 0; opp_marks = 0; nones = 0;

for(int x = 0; x < 3; x++)

{if (s.b[i+x*3] == player) your_marks++;

if (s.b[i+x*3] == opp ) opp_marks++;

if (s.b[i+x*3] == 0 ) nones++;}

if (your_marks == 2 && nones == 1) gene0++;

if (opp_marks == 2 && nones == 1) gene0--;

if (your_marks == 3) gene1++;

if (opp_marks == 3) gene1--;

if (your_marks == 1 && nones == 2) gene4++;

if (opp_marks == 1 && nones == 2) gene4--;

}

//====Check Diagonals

your_marks = 0; opp_marks = 0; nones = 0;

for(int x = 0; x < 3; x++)

{if (s.b[x*4] == player) your_marks++;

if (s.b[x*4] == opp ) opp_marks++;

if (s.b[x*4] == 0 ) nones++;}

if (your_marks == 2 && nones == 1) gene0++;

if (opp_marks == 2 && nones == 1) gene0--;

if (your_marks == 3) gene1++;

if (opp_marks == 3) gene1--;

if (your_marks == 1 && nones == 2) gene4++;

if (opp_marks == 1 && nones == 2) gene4--;

your_marks = 0; opp_marks = 0; nones = 0;

for(int x = 0; x < 3; x++)

{if (s.b[x*2+2] == player) your_marks++;

if (s.b[x*2+2] == opp ) opp_marks++;

if (s.b[x*2+2] == 0 ) nones++;}

if (your_marks == 2 && nones == 1) gene0++;

if (opp_marks == 2 && nones == 1) gene0--;

if (your_marks == 3) gene1++;

if (opp_marks == 3) gene1--;

if (your_marks == 1 && nones == 2) gene4++;

if (opp_marks == 1 && nones == 2) gene4--;

//Center Square

if (s.b[4] == player) gene2++;

if (s.b[4] == opp) gene2--;

//Corners

if (s.b[0] == player) gene3++;

if (s.b[2] == player) gene3++;

if (s.b[6] == player) gene3++;

if (s.b[8] == player) gene3++;

if (s.b[0] == opp) gene3--;

if (s.b[2] == opp) gene3--;

if (s.b[6] == opp) gene3--;

if (s.b[8] == opp) gene3--;

return gene0*w0+gene1*w1+gene2*w2+gene3*w3+gene4*w4;}

//Performs Minimax

float minimax(int max_t, float value, int level, state st,int p)

{

//Base Cases

if (level == 0)

return h(st,p);

if (checkdone(st) == 1)

return h(st,p);

float curm = -999;

if (max_t == 0)

curm = 999;

int best = -1;

float current = 0;

int possibleNextStates = nextPos(st);

for(int i = 1; i <= possibleNextStates; i++)

{state s_prime;

takesOn(&s_prime,&next_ith_state(st,i));

int opplook = 1;

if (max_t == 1)

{opplook = 0;}

current = minimax(opplook,curm,level-1,s_prime,p);

if (max_t ==1 && current > curm)

{curm = current; best = i;}

if (max_t ==0 && current < curm)

{curm = current; best = i;}

} //all possibilites

bestmv = best;

takesOn(&bestst,&next_ith_state(st,bestmv));

return curm;

}

//Return a state given an array index from the board database

state getState(int i) {

state s;

s.b[0] = perfect[i][2] - '0';

s.b[1] = perfect[i][3] - '0';

s.b[2] = perfect[i][4] - '0';

s.b[3] = perfect[i][5] - '0';

s.b[4] = perfect[i][6] - '0';

s.b[5] = perfect[i][7] - '0';

s.b[6] = perfect[i][8] - '0';

s.b[7] = perfect[i][9] - '0';

s.b[8] = perfect[i][10] - '0';

return s;}

//Checks if state s if a good move from database starting board i

char* best_move(int i, state s) {

string to_string;

for(int j = 0; j < 9; j++)

{to_string[j] = s.b[j] + '0';}

return strstr(perfect[i],to_string);

}