/* f4 v0.4 by Alessandro Presta
   This software is protected by the GNU General Public License */

#include <stdio.h>
 
#define M 7
#define N 6
#define DEPTH 6
#define ALPHA -200
#define BETA 200
#define OTHER(player) ((player) ^ 1)
#define WIN 1000
#define GOODNESS(player) ((score[(player)] - score[OTHER((player))]) % (WIN + 1))

enum {
	HUMAN,
	CPU,
	EMPTY
};

int board[M][N];
int placed;
int score[2];

void init();
void print();
int move(int);
int play(int, int);
void refresh(int, int, int, int);
int place(int, int);

int main()
{
	char cmd;
	int player;
	int column;
	init();
START:
	printf("Vuoi cominciare tu? (s/n) ");
	scanf("%c", &cmd);
	switch (cmd) {
		case 's':
			break;
		case 'n':
			print();
			printf("Sto pensando...\n");
			place(CPU, M / 2);
			break;
		default:
			goto START;
	}
	player = HUMAN;
	while (1) {
		switch (player) {
			case HUMAN:
				print();
			MOVE:
				printf("Colonna? (0-6) ");
				scanf("%d", &column);
				if (place(HUMAN, column) != 0) {
					printf("Mossa non concessa.\n");
					goto MOVE;
				}
				if (score[HUMAN] >= WIN) {
					printf("Hai vinto!\n");
					goto END;
				}
				if (placed == M * N) {
					printf("Parità!\n");
					goto END;
				}
				player = OTHER(player);
				break;
			case CPU:
				print();
				printf("Sto pensando...\n");
				place(CPU, move(CPU));
				if (score[CPU] >= WIN) {
					printf("Il computer ha vinto!\n");
					goto END;
				}
				if (placed == M * N) {
					printf("Parità!\n");
					goto END;
				}
				player = OTHER(player);		
		}
	}
END:
	print();
	return 0;
}

void init()
{
	int i, j;
	score[HUMAN] = score[CPU] = 0;
	for (i = 0; i < M; ++i)
		for (j = 0; j < N; ++j)
			board[i][j] = EMPTY;
	placed = 0;
}

void print()
{
	int i, j;
	printf("\n");
	for (j = 0; j < N; ++j) {
		for (i = 0; i < M; ++i)
			switch (board[i][j]) {
				case EMPTY:
					printf("0 ");
					break;
				case HUMAN:
					printf("H ");
					break;
				case CPU:
					printf("C ");
			}
			printf("\n");
	}
	printf("\n");
}

int move(int player)
{
	int i, j;
	int best_column;
	int best_score, cur_score;
	best_score = -2000;
	for (i = 0; i < M; ++i)
		for (j = N - 1; j >= 0; --j)
			if (board[i][j] == EMPTY) {
				board[i][j] = player;
				++placed;
				refresh(player, 1, i, j);
				if (score[player] >= WIN) {
					board[i][j] = EMPTY;
					--placed;
					refresh(player, 0, i, j);
					best_column = i;
					return best_column;
				}
				if ((cur_score = -play(OTHER(player), 1)) > best_score) {
					best_score = cur_score;
					best_column = i;
				}
				board[i][j] = EMPTY;
				--placed;
				refresh(player, 0, i, j);
				break;
			}
	return best_column;
}

int play(int player, int depth)
{
	int i, j;
	int best_column;
	int best_score, cur_score;
	if (placed == M * N)
		return 0;
	if (score[player] >= WIN)
		return WIN;
	if (depth == DEPTH)
		return GOODNESS(player);
	if (GOODNESS(player) <= ALPHA) {
#ifdef DEBUG
		printf("DEBUG: alpha\n");
#endif
		return ALPHA;
	}
	else if (GOODNESS(player) >= BETA) {
#ifdef DEBUG
		printf("DEBUG: beta\n");
#endif
		return BETA;
}
	best_score = -2000;
	for (i = 0; i < M; ++i)
		for (j = N - 1; j >= 0; --j)
			if (board[i][j] == EMPTY) {
				board[i][j] = player;
				++placed;
				refresh(player, 1, i, j);
				if (score[player] >= WIN) {
					board[i][j] = EMPTY;
					--placed;
					refresh(player, 0, i, j);
					return WIN;
				}
				if ((cur_score = -play(OTHER(player), depth + 1)) > best_score) {
					best_score = cur_score;
					best_column = i;
				}
				board[i][j] = EMPTY;
				--placed;
				refresh(player, 0, i, j);
				break;
			}
	return best_score;	
}

void refresh(int player, int add, int x, int y)
{
	int i;
	int length, rlen, llen;
	int empty[2];
	int diff;
	diff = 0;
	length = 1;
	rlen = llen = 0;
	empty[0] = empty[1] = 0;
	for (i = x + 1; i < M; ++i) {
		if (board[i][y] == player) {
			++length;
			++rlen;
			if (length == 4)
				break;
		}
		else if (board[i][y] == EMPTY) {
			empty[0] = 1;
			break;
		}
		else {
			empty[0] = 0;
			break;
		}
	}
	for (i = x - 1; i >= 0; --i) {
		if (board[i][y] == player) {
			++length;
			++llen;
			if (length == 4)
				break;
		}
		else if (board[i][y] == EMPTY) {
			empty[1] = 1;
			break;
		}
		else {
			empty[1] = 0;
			break;
		}
	}
	if (length > 4)
		length = 4;
	switch (length) {
		case 4:
			diff += WIN;
			diff -= 10 * (rlen >= 3 || llen >= 3);
			break;
		case 3:
			diff += 10 * (empty[0] || empty[1]);
			diff -= 1 * (rlen >= 2 || llen >= 2);
			break;
		case 2:
			diff += 1 * (empty[0] && empty[1]);
	}
	length = 1;
	rlen = llen = 0;
	empty[0] = empty[1] = 0;
	for (i = y + 1; i < N; ++i) {
		if (board[x][i] == player) {
			++length;
			++rlen;
			if (length == 4)
				break;
		}
		else if (board[x][i] == EMPTY) {
			empty[0] = 1;
			break;
		}
		else {
			empty[0] = 0;
			break;
		}
	}
	for (i = y - 1; i >= 0; --i) {
		if (board[x][i] == player) {
			++length;
			++llen;
			if (length == 4)
				break;
		}
		else if (board[x][i] == EMPTY) {
			empty[1] = 1;
			break;
		}
		else {
			empty[1] = 0;
			break;
		}
	}
	if (length > 4)
		length = 4;
	switch (length) {
		case 4:
			diff += WIN;
			diff -= 10 * (rlen >= 3 || llen >= 3);
			break;
		case 3:
			diff += 10 * (empty[0] || empty[1]);
			diff -= 1 * (rlen >= 2 || llen >= 2);
			break;
		case 2:
			diff += 1 * (empty[0] && empty[1]);
	}
	length = 1;
	rlen = llen = 0;
	empty[0] = empty[1] = 0;
	for (i = 1; (x + i < M) && (y + i < N); ++i) {
		if (board[x + i][y + i] == player) {
			++length;
			++rlen;
			if (length == 4)
				break;
		}
		else if (board[x + i][y + i] == EMPTY) {
			empty[0] = 1;
			break;
		}
		else {
			empty[0] = 0;
			break;
		}
	}
	for (i = -1; (x + i >= 0) && (y + i >= 0); --i) {
		if (board[x + i][y + i] == player) {
			++length;
			++llen;
			if (length == 4)
				break;
		}
		else if (board[x + i][y + i] == EMPTY) {
			empty[1] = 1;
			break;
		}
		else {
			empty[1] = 0;
			break;
		}
	}
	if (length > 4)
		length = 4;
	switch (length) {
		case 4:
			diff += WIN;
			diff -= 10 * (rlen >= 3 || llen >= 3);
			break;
		case 3:
			diff += 10 * (empty[0] || empty[1]);
			diff -= 1 * (rlen >= 2 || llen >= 2);
			break;
		case 2:
			diff += 1 * (empty[0] && empty[1]);
	}
	length = 1;
	rlen = llen = 0;
	empty[0] = empty[1] = 0;
	for (i = 1; (x + i < M) && (y - i >= 0); ++i) {
		if (board[x + i][y - i] == player) {
			++length;
			++rlen;
			if (length == 4)
				break;
		}
		else if (board[x + i][y - i] == EMPTY) {
			empty[0] = 1;
			break;
		}
		else {
			empty[0] = 0;
			break;
		}
	}
	for (i = -1; (x + i >= 0) && (y - i < N); --i) {
		if (board[x + i][y - i] == player) {
			++length;
			++llen;
			if (length == 4)
				break;
		}
		else if (board[x + i][y - i] == EMPTY) {
			empty[1] = 1;
			break;
		}
		else {
			empty[1] = 0;
			break;
		}
	}
	if (length > 4)
		length = 4;
	switch (length) {
		case 4:
			diff += WIN;
			diff -= 10 * (rlen >= 3 || llen >= 3);
			break;
		case 3:
			diff += 10 * (empty[0] || empty[1]);
			diff -= 1 * (rlen >= 2 || llen >= 2);
			break;
		case 2:
			diff += 1 * (empty[0] && empty[1]);
	}
	if (add)
		score[player] += diff;
	else
		score[player] -= diff;
}

int place(int player, int column)
{
	int j;
	for (j = N - 1; j >= 0; j--)
		if (board[column][j] == EMPTY) {
			board[column][j] = player;
			refresh(player, 1, column, j);
			++placed;
			return 0;
		}
	return 1;
}