// ****************************************************************************
// *                                                                          *
// *                      Velena Source Code V1.0                             *
// *                   Written by Giuliano Bertoletti                         *
// *       Based on the knowledged approach of Louis Victor Allis             *
// *   Copyright (C) 1996-97 by Giuliano Bertoletti & GBE 32241 Software PR   *
// *                                                                          *
// ****************************************************************************

// Portable engine version.
// read the README file for further informations.

// ==========================================================================


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>

#include "connect4.h"
#include "con4vals.h"
#include "pnsearch.h"
#include "proto.h"

#define BLSTRSIZE 14

short maxdepth;

short get_black_best_move(struct board *board)
    {
    short black_str[BLSTRSIZE]={4,4,4,4,4,2,2,2,2,6,6,6,6,6};
    short x,flag=YES;

    if(board->filled>=BLSTRSIZE) return -1;

    for(x=0;x<board->filled && flag;x++)
        if(board->moves[x]!=(black_str[x]-1)) flag=NO;

    if(flag) return black_str[board->filled]-1;

    return -1;
    }

void reverse_board(struct board *board)
    {
    short x,y,z;

    for(y=0;y<BOARDY;y++)
        for(x=0;x<BOARDX/2;x++)
            {
            z=board->square[ELM(x,y)];
            board->square[ELM(x,y)]=board->square[ELM(BOARDX-x-1,y)];
            board->square[ELM(BOARDX-x-1,y)]=z;
            }

    for(x=0;x<BOARDX/2;x++)
        {
        z=board->stack[x];
        board->stack[x]=board->stack[BOARDX-x-1];
        board->stack[BOARDX-x-1]=z;
        }
    }

short pentas(struct board *board,short x,short y,short side)
	{
	if(board->stack[x]>=y) return NO;
	if(board->stack[x+2]>=y) return NO;
	if(board->stack[x+4]>=y) return NO;

	if(board->square[ELM(x+1,y)]!=side) return NO;
	if(board->square[ELM(x+3,y)]!=side) return NO;

	return YES;
	}

short check_pentas(struct board *board,short side)
	{
	short x,y,px,py,flag=0;

	for(x=0;x<3 && !flag;x++)
		for(y=0;y<2 && !flag;y++)
			{
			px=x;
			py=(y+1)*2;

			flag=(flag || pentas(board,px,py,side));
			}

	return flag;
	}

short gen_odd_threat(struct board *board,short x,short side)
	{
	short y,empty=0,fill=0,emp[TILES],px,py;

	for(y=0;y<TILES;y++)
		{
		if(*board->groups[x][y]==EMPTY)
			{
			px=board->xplace[x][y];
			py=board->yplace[x][y];
			emp[empty++]=ELM(px,py);
			}
		else if (*board->groups[x][y]==side) fill++;
		}

	if(empty==1 && fill==3 && (py&1)==0 && board->stack[px]<py) return emp[0];
	return -1;
	}

short check_double(struct board *board,short group,short pos,short side)
	{
	short x,y;

	for(x=group+1;x<GROUPS;x++)
		{
		y=gen_odd_threat(board,x,side);
		if(y==pos) return YES;
		}

	return NO;
	}

short groupeval(struct board *board)
	{
	short x,v1,v2;
	short z,f,p1,p2,t1,t2,score=0;

	t1=board->turn;
	t2=board->turn^SWITCHSIDE;

	for(x=0;x<GROUPS;x++)
		{
		p1=0;
		p2=0;

		if     (*board->groups[x][0]==t1) p1++;
		else if(*board->groups[x][0]==t2) p2++;

		if     (*board->groups[x][1]==t1) p1++;
		else if(*board->groups[x][1]==t2) p2++;

		if     (*board->groups[x][2]==t1) p1++;
		else if(*board->groups[x][2]==t2) p2++;

		if     (*board->groups[x][3]==t1) p1++;
		else if(*board->groups[x][3]==t2) p2++;

		if(p1==4) return GOODMOVE;
		if(p2==4) return BADMOVE;

		if(p1==3 && p2==0)
			{
			score+=100;
			z=gen_odd_threat(board,x,t1);
			if(z!=-1)
				{
				f=check_double(board,x,z,t1);
				if(!f)
					{
					if(t1==WHITE) score+=200;
					else score+=150;
					}
				else
					{
					if(t1==WHITE) score+=750;
					else score+=500;
					}
				}
			}

		if(p2==3 && p1==0)
			{
			score-=100;
			z=gen_odd_threat(board,x,t2);
			if(z!=-1)
				{
				f=check_double(board,x,z,t2);
				if(!f)
					{
					if(t1==BLACK) score-=200;
					else score-=150;
					}
				else
					{
					if(t1==BLACK) score-=750;
					else score-=500;
					}
				}
			}

		if(p1==2 && p2==0) score+=10;
		if(p2==2 && p1==0) score-=10;
		}


	if(check_pentas(board,WHITE))
		{
		if(t1==WHITE) score+=800;
		else score-=800;
		}

	return score;
	}

short connected(struct board *board,short move)
	{
	short maxcon=1;
	short px,py,connect;

	/* Check vertical */

	connect=1;

	px=move;
	py=board->stack[move]-1;

	while(py>=0 && board->square[ELM(px,py)]==board->turn)
		{
		connect++;
		py--;
		}

	maxcon=max(connect,maxcon);

	/* Check horizontal */

	connect=1;

	px =move-1;
	py =board->stack[move];

	while(px>=0 && board->square[ELM(px,py)]==board->turn)
		{
		connect++;
		px--;
		}

	px=move+1;

	while(px<BOARDX && board->square[ELM(px,py)]==board->turn)
		{
		connect++;
		px++;
		}

	maxcon=max(connect,maxcon);

	/* Check NW - SE diagonal */

	connect=1;

	px=move-1;
	py=board->stack[move]+1;

	while(px>=0 && py<BOARDY && board->square[ELM(px,py)]==board->turn)
		{
		connect++;
		px--;
		py++;
		}

	px=move+1;
	py=board->stack[move]-1;

	while(px<BOARDX && py>=0 && board->square[ELM(px,py)]==board->turn)
		{
		connect++;
		px++;
		py--;
		}

	maxcon=max(connect,maxcon);

	/* Check NE - SW */

	connect=1;

	px=move-1;
	py=board->stack[move]-1;

	while(px>=0 && py>=0 && board->square[ELM(px,py)]==board->turn)
		{
		connect++;
		px--;
		py--;
		}

	px=move+1;
	py=board->stack[move]+1;

	while(px<BOARDX && py<BOARDY && board->square[ELM(px,py)]==board->turn)
		{
		connect++;
		px++;
		py++;
		}

	maxcon=max(connect,maxcon);

	return maxcon;
	}

short opponent_connected(struct board *board,short move)
	{
	short con;

	board->turn^=SWITCHSIDE;
	con=connected(board,move);
	board->turn^=SWITCHSIDE;

	return con;
	}


short makemove(struct board *board,short move)
	{
	if(board->stack[move]>=6) return 0;

	board->square[ELM(move,board->stack[move]++)]=board->turn;
	board->moves[board->filled]=move;
    board->mlist[board->filled]=ELM(move,board->stack[move]);
    board->turn^=SWITCHSIDE;
	board->filled++;

	return 1;
	}

short undomove(struct board *board,short move)
	{
	if(board->stack[move]<1) return 0;

	board->square[ELM(move,--board->stack[move])]=EMPTY;
	board->turn^=SWITCHSIDE;
	board->filled--;
	board->moves[board->filled]=-1;
    board->mlist[board->filled]=-1;

	return 1;
	}

int get_game_result(struct board *board)
    {
    short answer=-1;
    short i;

    for(i=0;i<GROUPS && answer==-1;i++)
		{
        if (*board->groups[i][0]!=EMPTY &&
			*board->groups[i][0]==*board->groups[i][1] &&
			*board->groups[i][0]==*board->groups[i][2] &&
            *board->groups[i][0]==*board->groups[i][3])
                {
                if(*board->groups[i][0]==WHITE) answer=WHITE;
                else answer=BLACK;
                }
        }

    if(board->filled==MAXSQUARES && answer==-1) answer=0;
    return answer;
    }

short endgame(struct board *board)
	{
	short answer=NOTHING;
	short i,j;

	for(i=0;i<GROUPS && answer==NOTHING;i++)
		{
		if(*board->groups[i][0]!=EMPTY &&
			*board->groups[i][0]==*board->groups[i][1] &&
			*board->groups[i][0]==*board->groups[i][2] &&
			*board->groups[i][0]==*board->groups[i][3]) answer=WIN;

		j=*board->groups[i][0];
		}

	if(board->filled==MAXSQUARES && answer==NOTHING)
		{
		answer=DRAW;
		board->lastwin=0;
		}

	if(answer==WIN)
		{
		board->wins[j-1]++;
		board->lastwin=j;
		if(board->oracle[2-j]==YES)
			fatal_error("Oracle failed to tell the truth");
		}

	else if(answer==DRAW) board->draws++;

	return answer;
	}

short try_to_win(struct board *board)
	{
	short x,av[BOARDX],win=NO;

	for(x=0;x<BOARDX;x++)
		{
		if(board->stack[x]<BOARDY && connected(board,x)>=4)
			{
			av[x]=YES;
			win=YES;
			}
		else av[x]=NO;
		}

	if(win)
		{
		do
			{
			x=my_random(BOARDX);
			} while(av[x]==NO);
		}
	else x=-1;

	return x;
	}


short fast_try_to_win(struct board *board)
	{
    short x,win=-1;

	for(x=0;x<BOARDX;x++)
        if(board->stack[x]<BOARDY && connected(board,x)>=4) win=x;

    return win;
	}

short avoid_tricks(struct board *board,short side)
	{
	short x,answ,cn=0,tmp;

	maxdepth++;

	if(board->turn!=side)
		{
		answ=GOODMOVE;

		for(x=0;x<BOARDX;x++)
			{
			if(board->stack[x]<BOARDY)
				{
				cn++;
				if(connected(board,x)>=4)
					{
					maxdepth--;
					return BADMOVE;
					}
				else
					{
					makemove(board,x);
					tmp=avoid_tricks(board,side);
					answ=min(answ,tmp);
					undomove(board,x);
					}
				}

			}

		if(cn==0) answ=NOCOMMENT;
		}

	else
		{
		answ=GOODMOVE;

		for(x=0;x<BOARDX;x++)
			{
			if(board->stack[x]<BOARDY)
				{
				cn++;
				if(connected(board,x)>=4)
					{
					maxdepth--;
					return GOODMOVE;
					}
				else if(opponent_connected(board,x)>=4)
					{
					makemove(board,x);
					tmp=avoid_tricks(board,side);
					answ=min(answ,tmp);
					undomove(board,x);
					}
				}
			}

		if(cn==0) answ=NOCOMMENT;
		}

	maxdepth--;

	return answ;
	}

short play_tricks(struct board *board,short side)
	{
	short tmp;

	tmp=avoid_tricks(board,side^SWITCHSIDE);

	switch(tmp)
		{
		case GOODMOVE:
			tmp=BADMOVE;
			break;

		case BADMOVE:
			tmp=GOODMOVE;
			break;
		}

	return tmp;
	}

short save_position(struct board *board)
	{
	short x,y=GOODMOVE,z=IMPOSSIBLE,pos,score[BOARDX];

	for(x=0;x<BOARDX;x++)
		{
		score[x]=IMPOSSIBLE;
		if(board->stack[x]<BOARDY)
			{
			makemove(board,x);
			score[x]=avoid_tricks(board,board->turn^SWITCHSIDE);
			y=min(score[x],y);
			z=max(score[x],z);
			undomove(board,x);
			}
		}

	if(y<GOODMOVE)
		{
		do
			{
			pos=my_random(BOARDX);
			} while(score[pos]!=z);
		}

	else pos=-1;

	return pos;
	}

short explore_tree(struct board *board,short side,short depth)
	{
	short x,c,answ,cn=0,tmp;

	if(depth==0)
		{
		tmp=groupeval(board);
		if(board->turn==side) return tmp;
		else return -tmp;
		}

	/*
	if((depth==DEPTH-1) && avoid_tricks(board,side)==BADMOVE)
		return BADMOVE;


	if((depth==DEPTH-1) && play_tricks(board,side)==GOODMOVE)
		return GOODMOVE;
   */
	maxdepth++;

	if(board->turn!=side)
		{
		answ=GOODMOVE-depth;

		for(x=0;x<BOARDX && answ!=BADMOVE;x++)
			{
			if(board->stack[x]<BOARDY)
				{
				cn++;
				if(connected(board,x)>=4) answ=BADMOVE;
				else
					{
					makemove(board,x);
					tmp=explore_tree(board,side,depth-1);
					answ=min(answ,tmp);
					undomove(board,x);
					}
				}

			}

		if(cn==0) answ=NOCOMMENT;
		}

	else
		{
		answ=BADMOVE+depth;

		for(x=0;x<BOARDX;x++)
			{
			if(board->stack[x]<BOARDY)
				{
				cn++;
				if(connected(board,x)>=4) answ=GOODMOVE;
				else
					{
					makemove(board,x);
					tmp=explore_tree(board,side,depth-1);
					answ=max(answ,tmp);
					undomove(board,x);
					}
				}
			}

		if(cn==0) answ=NOCOMMENT;
		}

	maxdepth--;

	return answ;
	}

short look_ahed(struct board *board)
	{
	long def_nodes=0L;
	short x,y,score[BOARDX],sc=IMPOSSIBLE,p;
    short depth=DEPTH,oracle,set=NO,def_depth=0,cpu_level;

	maxdepth=0;

    if(board->turn==WHITE) cpu_level=board->white_lev;
    else cpu_level=board->black_lev;

	for(x=0;x<BOARDX;x++)
		{
		score[x]=IMPOSSIBLE;
		if(board->stack[x]<BOARDY)
			{
			makemove(board,x);

			p=heuristic_play_best(board,C4_NODE_SIZE);
			def_nodes+=board->nodes_visited;
			def_depth=max(def_depth,board->maxtreedepth);

            if(p>=0) score[x]=BADMOVE+board->maxtreedepth;
            else if(p==-2) score[x]=GOODMOVE-board->maxtreedepth;
			else
				{
				score[x]=explore_tree(board,board->turn^SWITCHSIDE,depth-1);
                if(score[x]>-3500 && score[x]<3500)
                    {
                    if(board->autotest) score[x]=my_random(RANDVARIANCE);
                    else score[x]+=my_random(RANDVARIANCE);
                    }

                if(cpu_level>1) oracle=evaluation_function(board);
                else oracle=0;

                score[x]+=(oracle<<13);
				if(oracle)
					{
					set=YES;
					if(!board->oracle[2-board->turn])
						{
						board->lastguess=board->filled+1;
						board->oracle[2-board->turn]=YES;
						if(board->lastguess<board->bestguess)
							board->bestguess=board->lastguess;
						}
					}
				}
			undomove(board,x);
			}

		sc=max(score[x],sc);
		}

    for(x=0,y=0;x<BOARDX;x++)
		if(score[x]==sc) y++;

	board->choices[board->filled]=y;

	do
		{
		x=my_random(BOARDX);
		} while(score[x]!=sc);

	return x;
	}

short defending_function(struct board *board)
    {
    int x,y=0;

    for(x=0;x<BOARDX;x++)
        {
        if(board->stack[x]<BOARDY)
            {
            makemove(board,x);
            if(evaluation_function(board) ||
               heuristic_play_best(board,C4_NODE_SIZE)>=0)
                  y++;
            undomove(board,x);
            }
        else y++;
        }

    if(y<BOARDX) return 0;
    return 1;
    }

short heuristic_defend_best(struct board *board)
    {
    int x,y=0;

    for(x=0;x<BOARDX;x++)
        {
        if(board->stack[x]<BOARDY)
            {
            makemove(board,x);
            if(heuristic_play_best(board,C4_NODE_SIZE)>=0) y++;
            undomove(board,x);
            }
        else y++;
        }

    if(y<BOARDX) return -1;
    return 1;
    }

short mybincmp(unsigned char *p1,unsigned char *p2,short len)
    {
    short x;

    for(x=0;x<len;x++)
        {
        if(p1[x]<p2[x]) return -1;
        else if(p1[x]>p2[x]) return +1;
        }

    return 0;
    }

short check_book(struct board *board,unsigned char *cmparray,short side)
    {
    short res,value;
    long x,head,tail;

    head=0;
    tail=board->wbposit;

    if(side==WHITE) value=PROVED;
    else value=DISPROVED;

    cmparray[12]=(value)&255;
    cmparray[13]=(value)>>8;

    do
        {
        x=(head + tail)/2;
        res=mybincmp(cmparray,&board->white_book[14*x],14);
        if(res==1) head=x+1;
        else if(res==-1) tail=x;
        } while(res!=0 && head!=tail);

    if(res==0)
        {
        board->lastob=x;
        return YES;
        }
    return NO;
    }

short get_lower(short *bb,unsigned char *tp)
    {
    char tp2[64];

    short x,y,flag=0;

    memset(tp,0xff,64);
    memset(tp2,0xff,64);

    for(y=0;y<BOARDY;y++)
        for(x=0;x<BOARDX;x++)
            {
            tp [ELM(x,y)]=bb[ELM(x,y)];
            tp2[ELM(x,y)]=bb[ELM(BOARDX-x-1,y)];
            }

    for(x=0;x<64 && flag==0;x++)
        {
        if(tp[x]<tp2[x]) flag=-1;
        else if(tp[x]>tp2[x]) flag=1;
        }

    if(flag==1)
        {
        memcpy(tp,tp2,64);
        return 0;
        }

    return 1;
    }

short use_opening_book(struct board *board,short side)
    {
    char flags[BOARDX],flagno=0;
    unsigned char cmparray[14];
    unsigned char tempboard[64];
    short x;

    if(!board->white_book) return -1;

    for(x=0;x<BOARDX;x++)
        {
        flags[x]=NO;
        if(makemove(board,x))
            {
            get_lower(board->square,tempboard);
            collapse_position(tempboard,cmparray);
            if(check_book(board,cmparray,side))
                {
                flags[x]=YES;
                flagno++;
                }
            undomove(board,x);
            }
        }

    if(flagno) while(1)
        {
        x=my_random(BOARDX);
        if(flags[x]) return x;
        }

    return -1;
    }

short check_presence(struct board *board,short side)
    {
    unsigned char tempboard[64],cmparray[14];

    get_lower(board->square,tempboard);
    collapse_position(tempboard,cmparray);
    return check_book(board,cmparray,side);
    }

short avoid_immediate_loss(struct board *board)
        {
        short move;

        board->turn^=SWITCHSIDE;
        move=try_to_win(board);
        board->turn^=SWITCHSIDE;
        return move;
        }

short ia_compute_move(struct board *board)
	{
	short move,x,y;

	board->choices[board->filled]=1;

        if(board->filled==0)
		{
		move=3;
		goto IA_RETURN_MOVE;
		}

    if(board->filled==1)
        {
        move=3;
        if(board->moves[0]==1) move=2;
        else if(board->moves[0]==5) move=4;
        goto IA_RETURN_MOVE;
        }

    if(board->filled==MAXMEN-1)
        {
        for(x=0;x<BOARDX;x++)
            {
            if(board->stack[x]<BOARDY)
                {
                move=x;
                goto IA_RETURN_MOVE;
                }
            }
        fatal_error("I shouldn't have come here...");
        }
    
    move=try_to_win(board);
    if(move>=0) goto IA_RETURN_MOVE;

    move=avoid_immediate_loss(board);
    if(move>=0) goto IA_RETURN_MOVE;
    
    if(board->turn==BLACK && board->black_lev==3)
        {
        move=get_black_best_move(board);
        if(move>=0) goto IA_RETURN_MOVE;
        }

    else if(board->filled==1 && board->stack[3]==1)
        {
        if(board->autotest)
            {
            short sel;

            /* The probability should not be uniform, but triangular */
            sel=my_random(15);

            if(sel==0) move=0;
            else if(sel<= 2) move=1;
            else if(sel<= 5) move=2;
            else if(sel<= 9) move=3;
            else if(sel<=12) move=4;
            else if(sel<=14) move=5;
            else move=6;
            }
        else move=3;

        goto IA_RETURN_MOVE;
        }

    /* Let's look in the opening book */
    switch(board->turn)
        {
        case WHITE:
            if(board->white_lev==3) move=use_opening_book(board,WHITE);
            else move=-1;
            break;

        case BLACK:
            if(board->black_lev==3) move=use_opening_book(board,BLACK);
            else move=-1;
            break;

        default:
            fatal_error("I don't know who's to move...");
            break;
        }

    if(move>=0) goto IA_RETURN_MOVE;

    fight(NO);
    move=heuristic_play_best(board,C4_NODE_SIZE);

    // Here we handle the fact that Black could also look for a win
    // improving the algorithm.

    if(board->turn==BLACK)
        {
        short temp;

        fight(YES);
        temp=heuristic_play_best(board,C4_NODE_SIZE);
        fight(NO);

        if(temp>=0) move=temp;
        }

    if(move>=0) goto IA_RETURN_MOVE;

    move=look_ahed(board);

	IA_RETURN_MOVE:
	return move;
	}

// ***************************************************************************

short get_last_move(struct board *board)
    {
    short x,y=-1;

    for(x=0;x<BOARDX && y==-1;x++)
        if(board->stack[x]<BOARDY) y=x;

    if(y==-1) fatal_error("Problem finding a solution...");

    if(connected(board,y)>=4) return 10;
    return 11;
    }