nice.c

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

#define DEPTH 7
#define INVALID 50
#define WIDTH 8
#define BOARD_SIZE WIDTH*WIDTH
#define COLOR(i) ((i)%2)
#define OP(i) (((i)+4)%8)

int dmap[] = {-WIDTH + 1, -WIDTH, -WIDTH-1, -1, WIDTH-1, WIDTH, WIDTH+1, 1};

typedef char piece_t;

struct board_t {
	piece_t pieces[BOARD_SIZE];
	unsigned moves, official_moves, top[WIDTH], max_score;
	char move_stack[BOARD_SIZE];
};

struct board_t* board_new (); // TODO

int querry(struct board_t*); // if it is the player's turn, ask for move and push it
void show_board(struct board_t*); //TODO just show the board
int decide_move(struct board_t*);
void pop_move(struct board_t*);
int push_move(struct board_t*, unsigned);

int main()
{
	struct board_t* board = board_new();
	char ans, undo_commited, player_color = 0;
	printf ("Are you going to play first? (y/n)\n");
	scanf ( " %c", &ans);
	switch (ans) {
	case 'n':
		printf ("Ok I will play first.\n");
		player_color = 1;
		break;
	case 'y':
		printf ("I thought so...\n");
		break;
	default:
		printf ("I will take that as a yes\n");
	}
	do {
		undo_commited = 0;
		board->official_moves = board->moves;
		show_board (board);
		if (COLOR(board->moves) != player_color)
			ans = decide_move(board);
		else
			ans = querry(board);
		printf( "Played: %d\n", ans);
		if (ans==0xff) break;
	} while (push_move(board, ans)<=0);
	board->official_moves = board->moves;
	show_board(board);
	printf ("Mr %s has won!",COLOR(board->moves-1)?"red":"yellow");

	return 0;
}

int querry( struct board_t* b)
{
	char ans;

	int satisfactory_answer = 0;
	while (!satisfactory_answer) {
		printf ("Column('u' to undo): ");
		scanf(" %c", &ans);
		if (ans == 'u') {
			pop_move(b); pop_move(b); pop_move(b);
			show_board(b);
			printf( "Undone!\n" );
		} else if (ans >='0' && ans <='7') {
			ans -= '0';
			satisfactory_answer = 1;
		} else
			printf ( "I am unable to comply('%c').\n", ans);
	}
	return ans;
}
int attempt_to_win(struct board_t* b)
{
	int i, tmp;
	for (i=0; i<WIDTH; i++) {
		tmp = push_move(b,i);
		if (tmp == -1)
			continue;
		if (tmp == 1) {
			pop_move(b);
			break;
		}
		pop_move(b);
	}
	return i;
}

struct move_weight_t {
	unsigned wins, defeats, draws;
	double r;
};

inline unsigned my_pow(unsigned b, unsigned e)
{
	unsigned ret = 1, i;
	for ( i=0; i<e; i++) ret *= b;
	return ret;
}

int descend(struct board_t* b, struct move_weight_t* w)
{
	int m;
	if (attempt_to_win(b) < WIDTH) {
		unsigned remaining_nodes = my_pow(7, 1+DEPTH - (b->moves - b->official_moves));
		if (COLOR(b->moves) == COLOR(b->official_moves))
			w->wins+=remaining_nodes;
		else
			w->defeats+=remaining_nodes;
		return 1;
	}

	if (b->moves > b->official_moves + DEPTH) {
		w->draws++;
		return 0;
	}

	for ( m=0; m<WIDTH; m++) {
		int tmp = b->moves;
		while (push_move(b,m) == -1)
			if(++m >= WIDTH) return 0; // board is full

		assert(b->moves>tmp);
		descend(b,w);
		pop_move(b);
	}
	return 0;
}

int decide_move (struct board_t* b)
{
	printf ("AI gets to work...\n");
	int move = attempt_to_win(b);
	if (move<WIDTH) return move;

	printf ("AI is unable to win instantly and apparently you cant either...\nThinking: ");
	struct move_weight_t mw[WIDTH];
	memset(mw, 0, sizeof(struct move_weight_t) * WIDTH);

	// If move defaults to 0 an 0 is full we are fucked
	for (move=0; move<WIDTH; move++)
		if (b->top[move] < WIDTH)
			break;

	if (move == WIDTH) {
		printf ("No available moves found\n");
		return -1;
	}

	push_move(b, move);
	unsigned tmp = attempt_to_win(b);
	pop_move(b);
	if (tmp<WIDTH) return tmp;

	int i;
	for (i=0; i<WIDTH; i++) {
		printf ("=="); fflush(stdout);
		while (push_move(b,i) == -1)
			if(++i >= WIDTH) break; // board is full
		descend(b, mw+i);
		pop_move(b);

		if (mw[i].defeats > 0) {
			mw[i].r = (double)mw[i].wins/(double)mw[i].defeats;
			if (mw[move].r < mw[i].r  || (mw[move].r == mw[i].r &&  mw[i].r == 0 && mw[move].defeats > mw[i].defeats))
				move = i;
		} else if (mw[i].wins > 0)
			move = i;
		else
			printf ("No idea what to do with %d\n",i);

	}
	printf ("\nAI decided: %d (%d/%d)\n", move, mw[move].wins, mw[move].defeats);
	for (i = 0; i<WIDTH; i++) printf ("%d: (%d/%d), ", i, mw[i].wins, mw[i].defeats);
	return move;

}

void pop_move(struct board_t* b)
{
	if (!b->moves) return;
	b->moves--;
	b->top[b->move_stack[b->moves]]--;
	assert(*(b->pieces + b->top[b->move_stack[b->moves]] + b->move_stack[b->moves]*WIDTH) != 50);
	*(b->pieces + b->top[b->move_stack[b->moves]] + b->move_stack[b->moves]*WIDTH) = 50;
}

void show_board(struct board_t* b)
{
	int i,j;
	for (i=WIDTH-1; i>=0; i--) {
		for (j=0;j<WIDTH;j++) printf ("%c ",
					      b->pieces[j*WIDTH+i] < b->official_moves ? (COLOR(b->pieces[j*WIDTH+i])? '*':'o' ):' ');
		printf ("\n");
	}
	printf ("=============\n0 1 2 3 4 5 6\n");
	// for (i=0; i<WIDTH; i++) printf("%d ",b->top[i]);
	printf ("\nMoves: %d\n", b->moves);
	printf("\n");
}

struct board_t* board_new()
{
	struct board_t* ret = (struct board_t*)malloc(sizeof(struct board_t));
	if (!ret) return NULL;
	memset(ret, 0, sizeof(struct board_t));
	int i;
	for (i=0;i<BOARD_SIZE;i++)
		ret->pieces[i] = INVALID;
	return ret;
}

int follow (piece_t* s, int step, struct board_t* b)
{
	unsigned ret = 0;
	while ((s+step >= b->pieces && s+step < b->pieces + BOARD_SIZE ) &&
	       !(((s - b->pieces)/sizeof(piece_t))%WIDTH == 0 && step == -1) &&
	       !(((s - b->pieces)/sizeof(piece_t))%WIDTH == WIDTH && step == 1) &&
	       *(s+step) < b->moves &&
	       COLOR(*(s+step)) == COLOR(b->moves)) {
		s += step;
		ret++;
	}
	return ret;
}

int push_move (struct board_t* b, unsigned m)
{
	int max_score = 0, score;
	if (b->top[m] >= WIDTH) {
		return -1;
	}

	piece_t* start = b->pieces+b->top[m]+ m*WIDTH;
	*start = b->moves;

	int i;
	for (i=0;i<4; i++) {
		score = follow( start, dmap[i], b);
		score += follow( start, dmap[OP(i)], b);
		score++;
		if (score>max_score) max_score = score;
	}

	assert(*(b->pieces + b->top[m] + m*WIDTH) == b->moves);
	b->top[m]++;
	b->move_stack[b->moves] = m;
	b->moves++;
	b->max_score = max_score;
	if (max_score >= 4) return 1;
	return 0;
}