//---------------------------------------------------------------------------
#include <vcl\vcl.h>
#pragma hdrstop

#include "ikos.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <assert.h>

#include <time.h>


#define other(x)        ((x) ^ 1)
#define realplayer(x)  ((x) & 1)

#define popstate() \
        (currentstate = &statestack[--depth])

#define goodnessof(player) \
        (currentstate->score[player] - currentstate->score[other(player)])


typedef struct {

    char **board; 
    int *(scorearray[2]);
    int score[2];          
    short int winner;
    int numofpieces;

} gamestate;


int sizex, sizey, numtoconnect;
int winplaces;

int ***map;  

int magicwinnumber;
bool gameinprogress = false, moveinprogress = false;
bool seedchosen = false;
void (*pollfunction)(void) = NULL;

gamestate statestack[20+1];
gamestate *currentstate;
int depth;
int statesallocated = 0;
int *droporder;



int numofwinplaces(int x, int y, int n);
void updatescore(int player, int x, int y);
int droppiece(int player, int column);
void push(void);
int evaluate(int player, int level, int alpha, int beta);





void
newgame(int width, int height, int num)
{
    register int i, j, k, x;
    int winindex, column;
    int *winindices;

    assert(!gameinprogress);
    assert(width >= 1 && height >= 1 && num >= 1);

    sizex = width;
    sizey = height;
    numtoconnect = num;
    magicwinnumber = 1 << numtoconnect;
    winplaces = numofwinplaces(sizex, sizey, numtoconnect);


    if (!seedchosen) {
        srand((unsigned int) time((time_t *) 0));
        seedchosen = true;
    }

    // set up the board */

    depth = 0;
    currentstate = &statestack[0];

    currentstate->board = (char **) malloc(sizex * sizeof(char *));
    for (i=0; i<sizex; i++) {
        currentstate->board[i] = (char *) malloc(sizey);
        for (j=0; j<sizey; j++)
            currentstate->board[i][j] = 2;
    }

    // set up the score array */

    currentstate->scorearray[0] = (int *) malloc(winplaces * sizeof(int));
    currentstate->scorearray[1] = (int *) malloc(winplaces * sizeof(int));
    for (i=0; i<winplaces; i++) {
        currentstate->scorearray[0][i] = 1;
        currentstate->scorearray[1][i] = 1;
    }

    currentstate->score[0] = currentstate->score[1] = winplaces;
    currentstate->winner = 2;
    currentstate->numofpieces = 0;

    statesallocated = 1;

    // set up the map */

    map = (int ***) malloc(sizex * sizeof(int **));
    for (i=0; i<sizex; i++) {
        map[i] = (int **) malloc(sizey * sizeof(int *));
        for (j=0; j<sizey; j++) {
            map[i][j] = (int *) malloc((numtoconnect*4 + 1) * sizeof(int));
            map[i][j][0] = -1;
        }
    }

    winindex = 0;

    // fill in the horizontal win positions */
    for (i=0; i<sizey; i++)
        for (j=0; j<sizex-numtoconnect+1; j++) {
            for (k=0; k<numtoconnect; k++) {
                winindices = map[j+k][i];
                for (x=0; winindices[x] != -1; x++)
                    ;
                winindices[x++] = winindex;
                winindices[x] = -1;
            }
            winindex++;
        }

    // fill in the vertical win positions */
    for (i=0; i<sizex; i++)
        for (j=0; j<sizey-numtoconnect+1; j++) {
            for (k=0; k<numtoconnect; k++) {
                winindices = map[i][j+k];
                for (x=0; winindices[x] != -1; x++)
                    ;
                winindices[x++] = winindex;
                winindices[x] = -1;
            }
            winindex++;
        }

    // fill in the forward diagonal win positions */
    for (i=0; i<sizey-numtoconnect+1; i++)
        for (j=0; j<sizex-numtoconnect+1; j++) {
            for (k=0; k<numtoconnect; k++) {
                winindices = map[j+k][i+k];
                for (x=0; winindices[x] != -1; x++)
                    ;
                winindices[x++] = winindex;
                winindices[x] = -1;
            }
            winindex++;
        }

    // fill in the backward diagonal win positions */
    for (i=0; i<sizey-numtoconnect+1; i++)
        for (j=sizex-1; j>=numtoconnect-1; j--) {
            for (k=0; k<numtoconnect; k++) {
                winindices = map[j-k][i+k];
                for (x=0; winindices[x] != -1; x++)
                    ;
                winindices[x++] = winindex;
                winindices[x] = -1;
            }
            winindex++;
        }

    droporder = (int *) malloc(sizex * sizeof(int));
    column = (sizex-1) / 2;
    for (i=1; i<=sizex; i++) {
        droporder[i-1] = column;
        column += ((i%2)? i : -i);
    }

    gameinprogress = true;
}


bool
makemove(int player, int column, int *row)
{
    int result; 

    assert(gameinprogress);
    assert(!moveinprogress);

    if (column >= sizex || column < 0)
        return false;

    result = droppiece(realplayer(player), column);
    if (row && result >= 0)
        *row = result;
    return (result >= 0);
}


bool
compmove(int player, int level, int *column, int *row)
{
    int i, bestcolumn = -1, goodness = 0, bestworst = -(INT_MAX);
    int numofequal = 0, realplayer, currentcolumn, result;

    assert(gameinprogress);
    assert(!moveinprogress);
    assert(level >= 1 && level <= 20);

    realplayer = realplayer(player);

    if (currentstate->numofpieces < 2 &&
                        sizex == 7 && sizey == 6 && numtoconnect == 4 &&
                        (currentstate->numofpieces == 0 ||
                         currentstate->board[3][0] != 2)) {
        if (column)
            *column = 3;
        if (row)
            *row = currentstate->numofpieces;
        droppiece(realplayer, 3);
        return true;
    }

    moveinprogress = true;

    // simulate a drop in each of the columns and see what the results are. */

    for (i=0; i<sizex; i++) {
        push();
        currentcolumn = droporder[i];

        // if this column is full, ignore it as a possibility. */
        if (droppiece(realplayer, currentcolumn) < 0) {
            popstate();
            continue;
        }

        // if this drop wins the game, take it! */
        else if (currentstate->winner == realplayer) {
            bestcolumn = currentcolumn;
            popstate();
            break;
        }

        // otherwise, look ahead to see how good this move may turn out */
        // to be (assuming the opponent makes the best moves possible). */
        else {
        
            goodness = evaluate(realplayer, level, -(INT_MAX), -bestworst);
        }

        // if this move looks better than the ones previously considered, */
        // remember it.                                                   */
        if (goodness > bestworst) {
            bestworst = goodness;
            bestcolumn = currentcolumn;
            numofequal = 1;
        }

        // if two moves are equally as good, make a random decision. */
        else if (goodness == bestworst) {
            numofequal++;
            if (rand()%10000 < ((float)1/(float)numofequal) * 10000)
                bestcolumn = currentcolumn;
        }

        popstate();
    }

    moveinprogress = false;

    // drop the piece in the column decided upon. */

    if (bestcolumn >= 0) {
        result = droppiece(realplayer, bestcolumn);
        if (column)
            *column = bestcolumn;
        if (row)
            *row = result;
        return true;
    }
    else
        return false;
}



char ** board(void)
{
    assert(gameinprogress);
    return currentstate->board;
}





bool
iswinner(int player)
{
    assert(gameinprogress);
    return (currentstate->winner == realplayer(player));
}

bool
istie()
{
    assert(gameinprogress);
    return (currentstate->numofpieces == sizex * sizey);
}



void
endgame(void)
{
    int i, j;

    assert(gameinprogress);
    assert(!moveinprogress);

    // free up the memory used by the map. */

    for (i=0; i<sizex; i++) {
        for (j=0; j<sizey; j++)
            free(map[i][j]);
        free(map[i]);
    }
    free(map);

    // free up the memory of all the states used. */

    for (i=0; i<statesallocated; i++) {
        for (j=0; j<sizex; j++)
            free(statestack[i].board[j]);
        free(statestack[i].board);
        free(statestack[i].scorearray[0]);
        free(statestack[i].scorearray[1]);
    }
    statesallocated = 0;

    // free up the memory used by the droporder array. */

    free(droporder);

    gameinprogress = false;
}






 int
numofwinplaces(int x, int y, int n)
{
    if (x < n && y < n)
        return 0;
    else if (x < n)
        return x * ((y-n)+1);
    else if (y < n)
        return y * ((x-n)+1);
    else
        return 4*x*y - 3*x*n - 3*y*n + 3*x + 3*y - 4*n + 2*n*n + 2;
}



 void
updatescore(int player, int x, int y)
{
    register int i;
    int winindex;
    int thisdifference = 0, otherdifference = 0;
    int **currentscorearray = currentstate->scorearray;
    int otherplayer = other(player);

    for (i=0; map[x][y][i] != -1; i++) {
       winindex = map[x][y][i];
       thisdifference += currentscorearray[player][winindex];
       otherdifference += currentscorearray[otherplayer][winindex];

           currentscorearray[player][winindex] <<= 1;
        currentscorearray[otherplayer][winindex] = 0;

       if (currentscorearray[player][winindex] == magicwinnumber)
           if (currentstate->winner == 2)
              currentstate->winner = player;
   }

    currentstate->score[player] += thisdifference;
    currentstate->score[otherplayer] -= otherdifference;
}



 int
droppiece(int player, int column)
{
    int y = 0;

    while (currentstate->board[column][y] != 2 && ++y < sizey)
        ;

    if (y == sizey)
        return -1;

    currentstate->board[column][y] = player;
    currentstate->numofpieces++;
    updatescore(player, column, y);

    return y;
}


 void
push(void)
{
    register int i, winplacesarraysize;
    gamestate *oldstate, *newstate;

    winplacesarraysize = winplaces * sizeof(int);
    oldstate = &statestack[depth++];
    newstate = &statestack[depth];

    if (depth == statesallocated) {

        // allocate space for the board */

        newstate->board = (char **) malloc(sizex * sizeof(char *));
        for (i=0; i<sizex; i++)
            newstate->board[i] = (char *) malloc(sizey);

        // allocate space for the score array */

        newstate->scorearray[0] = (int *) malloc(winplacesarraysize);
        newstate->scorearray[1] = (int *) malloc(winplacesarraysize);

        statesallocated++;
    }

    // copy the board */

    for (i=0; i<sizex; i++)
        memcpy(newstate->board[i], oldstate->board[i], sizey);

    // copy the score array */

    memcpy(newstate->scorearray[0], oldstate->scorearray[0],
           winplacesarraysize);
    memcpy(newstate->scorearray[1], oldstate->scorearray[1],
           winplacesarraysize);

    newstate->score[0] = oldstate->score[0];
    newstate->score[1] = oldstate->score[1];
    newstate->winner = oldstate->winner;

    currentstate = newstate;
}

 int
evaluate(int player, int level, int alpha, int beta)
{
    int i, goodness, best, maxab;



    if (level == depth)
        return goodnessof(player);
    else {
        // assume it is the other player's turn. 
        best = -(INT_MAX);
        maxab = alpha;
        for(i=0; i<sizex; i++) {
            push();
            if (droppiece(other(player), droporder[i]) < 0) {
                popstate();
                continue;
            }
            else if (currentstate->winner == other(player))
                goodness = INT_MAX - depth;
            else
                goodness = evaluate(other(player), level, -beta, -maxab);
            if (goodness > best) {
                best = goodness;
                if (best > maxab)
                    maxab = best;
            }
            popstate();
            if (best > beta)
                break;
        }

        // what's good for the other player is bad for this one.
        return -best;
    }
}


//---------------------------------------------------------------------------
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
	: TForm(Owner)
{
	w=10;
    h=10;
    gameinprogress=false;
    width->Text="7";
    height->Text="5";
    mode=1;


}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
int x=atoi(width->Text.c_str());
int y=atoi(height->Text.c_str());
elevel= atoi(level->Text.c_str());
int edelay=   atoi(delay->Text.c_str());
//___0 means human___

if(x<1 || y<1 || elevel<2 || elevel>15)
	return;

w=x;
h=y;

int i,j,k;



	if(gameinprogress)
    	endgame();



     newgame(w, h, 4);


    gameinprogress=true;
    move=-1;
      humanthinking=1;

      turn=0;

    if(mode==1 && firstturn->State==cbChecked)
    {
    	turn=1;
         message->Text="Thinking...";
        compmove(turn, 7, &move, NULL);
        turn = 1-turn;
    }


	message->Text="Player 1...";
    paintboard(w,h);


    Timer1->Interval=100;
    if(mode==3)
    	Timer1->Interval=edelay;


}

void TForm1::paintboard( int x, int y)
{
		if(!gameinprogress)
        	return;
     int bh=(ClientHeight-56)/y;
     int bw=ClientWidth/x;

     int xc,yc;
     yc=56;
     xc=1;
     int i,j,k;

     TRect r;
     r.Left=1;
     r.Right=ClientWidth;
     r.Top=56;
     r.Bottom=ClientHeight;
     Canvas->Brush->Color=clWhite;
     Canvas->FillRect(r);
     //Canvas->Brush->Color=clBlack;

     char** brd;
     brd=board();


     for(i=0;i<y;i++)
     {
     	xc=1;
        for(j=0;j<x;j++)
        {
            Canvas->Brush->Color=clWhite;
        	Canvas->Rectangle(xc,yc,xc+bw,yc+bh);
            if(brd[j][y-i-1]==0)
            {
            	Canvas->Brush->Color=clBlue;
                Canvas->Ellipse(xc+2,yc+2,xc+bw-2,yc+bh-2);
            }
            else if(brd[j][y-i-1]==1)
            {
            	Canvas->Brush->Color=clRed;
                Canvas->Ellipse(xc+2,yc+2,xc+bw-2,yc+bh-2);

            }
            xc+=bw;

        }
        yc+=bh;
     }

}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormResize(TObject *Sender)
{
paintboard(w,h);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender)
{
paintboard(w,h);

}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormMouseUp(TObject *Sender, TMouseButton Button,
	TShiftState Shift, int X, int Y)
{



	int bw=ClientWidth/w;
    move=X/bw;
	humanthinking=0;

    paintboard(w,h);


}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormClick(TObject *Sender)
{
paintboard(w,h);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{
Application->MessageBox("Developed for Tryst 2001 - IKOS SAMADHAN by\nAshish Gupta , 3rd year B.Tech CSE, 98131\nD-30 , Jwalamukhi Hostel , IIT Delhi","About",1);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::hcClick(TObject *Sender)
{
if(hc->Checked)
	mode=1;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::hhClick(TObject *Sender)
{
if(hh->Checked)
	mode=2;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ccClick(TObject *Sender)
{
if(cc->Checked)
	mode=3;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Timer1Timer(TObject *Sender)
{
 	if(!gameinprogress)
    	return;

    // paintboard(w,h);

     if (turn == 0 ) {

		if((mode==1 || mode==2) && !humanthinking)
        {
     	message->Text="Player 1...";
         if(!makemove(turn, move, NULL))
         {
         	Application->MessageBox("Invalid Move !","Message",1);
            return;
         }
         humanthinking=1;
     	turn=1-turn;
        paintboard(w,h);
        }
        if(mode==3)
        {
            compmove(turn,5, &move, NULL);
        	turn = 1-turn;
            paintboard(w,h);

        }


     }
     if(turn==1)
     {
         message->Text="Player 2...";

			if(mode==1 || mode==3)
            {
            compmove(turn,5, &move, NULL);
        	turn = 1-turn;
            paintboard(w,h);
            }
            if(mode==2 && !humanthinking)
            {
            	    	message->Text="Your move...";
      	  	 if(!makemove(turn, move, NULL))
     	    {
         	Application->MessageBox("Invalid Move !","Message",1);
            return;
       		  }
        	 humanthinking=1;
     		turn=1-turn;
      		  paintboard(w,h);
            }


     }



    if(turn==0)
    	message->Text="Player 1...";
    else
    	message->Text="Player 2...";


if(! (!iswinner(0) && !iswinner(1) && !istie()))
{


  gameinprogress=false;
  if (iswinner(0)) {
          message->Text="Player 1  wins!";
          Application->MessageBox("Player 1  wins!","Message",1);
   }
  else if (iswinner(1)) {

          message->Text="Player 2 wins !";
          Application->MessageBox("Player 2 wins !","Message",1);

  }
  else {
      message->Text="There was a tie!";
          Application->MessageBox("There was a tie !","Message",1);

  }
       endgame();
  }

}
//---------------------------------------------------------------------------