⟦263c9706b⟧

TextFile

#include "challenge.h"

int ncall;
#ifdef DEBUG
int debug=1;
static FILE *log = NULL;
#endif

#define N_COMPUTER  0
#define N_HUMAN     1
#define N_TABLE     2

#define OPPONENT(s)     (1 - (s))

#define INFINITE 0xffff
#define UNDEF    9999

#define BIT_SUIT(x)    ((x)>>13)
#define BIT_VALUE(x)    ((x)&0x1fff)

typedef struct {
    char to_move, ply;
    int  top;
    int  n_cards[2];
    int  cards[3][4];
} position;

int stack[500];
int score[256][4];
int trumps[2];

int jimmy;

int last_score = 0;

store_moves(c, suit, my_cards, table_cards, mp)
    int c, suit, my_cards, table_cards, *mp;
{
    int n = 0;

    suit <<= 13;
    while(c) {
	if(c & my_cards) {
	    *(mp++) = c | suit;
	    n++;
	    do {
		c >>= 1;
	    } while(c & (my_cards | table_cards));
	}
	c >>= 1;
    }
    return n;
}

gen_moves(pos, mp)
    position *pos;
    int *mp;
{
    int my_side, my_trump, his_trump;
    int nm, h, top_suit, top_card;
    int *my_cards, *table_cards;

    my_side     = pos->to_move;
    my_cards    = pos->cards[my_side];
    table_cards = pos->cards[N_TABLE];
    top_suit    = BIT_SUIT(pos->top);
    top_card    = BIT_VALUE(pos->top);
    my_trump    = trumps[my_side];
    his_trump   = trumps[OPPONENT(my_side)];

    if(top_card) {
	*mp = 0;
	nm = 1 + store_moves(top_card >> 1, top_suit, my_cards[top_suit],
			     table_cards[top_suit], mp + 1);
	mp += nm;
	if(top_suit != my_trump) {
	    nm += store_moves(jimmy, my_trump, my_cards[my_trump],
			      table_cards[my_trump], mp);
	}
    }
    else {
	nm = store_moves(jimmy, DIAMONDS, my_cards[DIAMONDS],
			 table_cards[DIAMONDS], mp);
	mp += nm;
	h = store_moves(jimmy, CLUBS, my_cards[CLUBS], table_cards[CLUBS], mp);
	mp += h;
	nm += h;
	h = store_moves(jimmy, his_trump, my_cards[his_trump],
			table_cards[his_trump], mp);
	mp += h;
	nm += h;
	h = store_moves(jimmy, my_trump, my_cards[my_trump],
			table_cards[my_trump], mp);
	nm += h;
    }
    return(nm);
}

#define gscore(x0,x1,y0,y1,a0,a1,b0,b1) 6*x0+5*y0+3*x1+3*y1-a0-b0-2*a1-2*b1

static_eval(pos)
    position *pos;
{
    int my_side, his_side, my_trump, his_trump;
    int x, x0, x1, dx,
	y, y0, y1, dy,
	a, a0, a1, da,
	b, b0, b1, db, f1;
    int tx, tx0, tx1, tdx,
	ty, ty0, ty1, tdy,
	ta, ta0, ta1, tda,
	tb, tb0, tb1, tdb, f2;

    my_side = pos->to_move;
    his_side = OPPONENT(my_side);
    my_trump = trumps[my_side];
    his_trump = trumps[his_side];

    {
	register int *c_m = pos->cards[my_side];
	register int *c_h = pos->cards[his_side];
	register int *p;

	p = score[c_m[my_trump]];
	x0 = *(p++);
	x1 = *(p++);
	x = *(p++);
	dx = *p;
	p = score[c_h[his_trump]];
	tx0 = *(p++);
	tx1 = *(p++);
	tx = *(p++);
	tdx = *p;
	p = score[c_m[his_trump]];
	y0 = *(p++);
	y1 = *(p++);
	y = *(p++);
	dy = *p;
	p = score[c_h[my_trump]];
	ty0 = *(p++);
	ty1 = *(p++);
	ty = *(p++);
	tdy = *p;
	p = score[c_m[CLUBS]];
	a0 = *(p++);
	a1 = *(p++);
	a = *(p++);
	da = *p;
	p = score[c_h[CLUBS]];
	tb0 = *(p++);
	tb1 = *(p++);
	tb = *(p++);
	tdb = *p;
	p = score[c_m[DIAMONDS]];
	b0 = *(p++);
	b1 = *(p++);
	b = *(p++);
	db = *p;
	p = score[c_h[DIAMONDS]];
	ta0 = *(p++);
	ta1 = *(p++);
	ta = *(p++);
	tda = *p;
    }

    if(x1 + y1 + a + b <= 1) {
	return(INFINITE);
    }
    if(tx0 == pos->n_cards[his_side]) {
	return(-INFINITE);
    }
    if((tx) == 0 && x0 >= x1 - 1) {
	register int n;

	n = da;
	n += db;
	n += dx;
	if(n <= x0 + 1) {
	    return(INFINITE);
	}
    }
    if(x == 0 && tx0 >= x1) {
	register int n;

	n = tda;
	n += tdb;
	if(tx1 == tx0) {
	    n++;
	}
	if(n <= tx0) {
	    return(-INFINITE);
	}
    }
    f1 = gscore(x0, x1, y0, y1, a0, a1, b0, b1);
    f2 = gscore(tx0, tx1, ty0, ty1, ta0, ta1, tb0, tb1);
    return(3 + f1 - f2);
}
#undef gscore

update(pos, mv)
    register position *pos;
    register int mv;
{
    register int his_side = pos->to_move;

    pos->to_move = OPPONENT(his_side);
    pos->top = mv;
    pos->ply += 1;
    if(mv == 0) {
	register int s;

	pos->n_cards[his_side] = max_card - pos->n_cards[OPPONENT(his_side)];
	for(s = 3; s >= 0; s--) {
	    pos->cards[his_side][s] |= pos->cards[N_TABLE][s];
	    pos->cards[N_TABLE][s] = 0;
	}
    } else {
	register int suit;

	pos->n_cards[his_side] -= 1;
	suit = BIT_SUIT(mv);
	pos->cards[N_TABLE][suit] |= BIT_VALUE(mv);
	pos->cards[his_side][suit] ^= BIT_VALUE(mv);
    }
}

eval(pos, mv , mvlist, alfa, beta)
    position pos;
    int  mv, *mvlist, alfa, beta;
{
    int nmoves, e, emax, i;
    int nbeta = beta;

    ++ncall;
    update(&pos, mv);
    if(mv==0) {
	if(pos.n_cards[pos.to_move] == 1) {
	    return(-INFINITE);
	}
	emax = static_eval(&pos);
	if(pos.ply > depth) {
	    return(-emax);
	}
	if(emax == INFINITE) {
	    return(-INFINITE);
	} else if(emax == -INFINITE) {
	    return(INFINITE);
	}
    }
    nmoves = gen_moves(&pos,mvlist);
    if(nmoves > 1 && (pos.n_cards[pos.to_move] == 1)) {
	return(-INFINITE);
    }
    emax = -INFINITE;
    for(i=0; i<nmoves; i++) {
	e = eval(pos, mvlist[i], mvlist + nmoves, -nbeta, -alfa);
	if(e > emax) {
	    emax = e;
	}
	if(emax >= alfa) {
	    break;
	}
	if(emax > nbeta) {
	    nbeta = emax;
	}
    }
    return(-emax);
}

strategy(player)
    int player;
{
    static init = FALSE;
    position pos;
    int nmoves, emax, e, i;
    int bestmv = 0;

    if(depth == 0) {
	return(zero_strategy(player));
    }
#ifdef TIMER
    set_alarm();
#endif
    if(!init) {
	init = TRUE;
	loc_init();
    }

    init_pos(&pos, player);
#ifdef DEBUG
    if(debug) {
	print_pos(&pos);
    }
#endif
    nmoves = gen_moves(&pos, stack);
    if(nmoves == 1) {
	bestmv = stack[0];
	emax = UNDEF;
    } else if(nmoves > 1 && pos.n_cards[pos.to_move] == 1) {
	bestmv = stack[1];
	emax = INFINITE;
    } else {
	ncall = 0;
	emax = -INFINITE;
	bestmv = stack[1];
	for(i=0; i<nmoves; i++) {
	    e = eval(pos, stack[i], stack + nmoves, -emax, -INFINITE);
#ifdef DEBUG
	    if(debug) {
		printmve(0,stack[i],e);
	    }
#endif
	    if(e > emax)
	    {
		emax = e;
		bestmv = stack[i];
	    }
	}
#ifdef DEBUG
	if(debug) {
	    fprintf(log, "chosen ( %d )===> ", ncall);
	    printmve(0, bestmv, emax);
	    fflush(log);
	}
#endif
    }
#ifdef TIMER
    end_alarm();
#endif
    move(COMMENT_LINE, 1);
    clrtoeol();
    if(player == COMPUTER) {
	if(emax == INFINITE || (last_score == INFINITE && emax == UNDEF)) {
	    printw("i think i am going to win!");
	    emax = INFINITE;
	}
    }
    refresh();
    last_score = emax;
    if(bestmv == 0) {
	return(PICK_UP);
    }
    if(player == COMPUTER) {
	return(comp_ind(bestmv, &computer[0]));
    } else {
	return(comp_ind(bestmv, &human[0]));
    }
}

loc_init()
{
    int mcs, s0, s1;
    int i;
#ifdef DEBUG
    if(debug && log==0) {
	unlink(DEBUG);
	log = fopen(DEBUG, "w");
    }
#endif
    for(i=0; i<256; i++) {
	s0 = 0;
	s1 = 0;
	mcs = i;
	while(mcs & 1) {
	    mcs >>= 1;
	    s0++;
	}
	while(mcs) {
	    s1 += mcs&1;
	    mcs >>= 1;
	}
	score[i][0] = s0;
	score[i][1] = s1;
	score[i][2] = s0 + s1;
	if(s1 > s0) {
	    score[i][3] = s1 - s0;
	} else {
	    score[i][3] = 0;
	}
    }
}

#define SUIT1(x) ((x)&3)
#define VALUE1(x) (((x)>>2) & 15)

bit_to_int(mv)
    int mv;
{
    int s, c, v;

    if(mv == 0) {
	return(0);
    }
    s = BIT_SUIT(mv);
    c = BIT_VALUE(mv);
    for(v = 0; c > 1; c >>= 1) {
	v++;
    }
    return(s + (v << 2));
}

comp_ind(c, deck)
    char *deck;
{
    int i;

    c = bit_to_int(c);
    for(i = 0; deck[i] != c ; i++);
    return(i);
}

init_pos(pos, player)
    position *pos;
    int player;
{

    int i, c;

    trumps[N_COMPUTER] = SPADES;
    trumps[N_HUMAN] = HEARTS;
    jimmy = 1 << ((max_card >> 2) - 1);

    if(nr_table == 0) {
	pos->top = 0;
    } else {
	pos->top = (1 << VALUE1(top)) | (SUIT1(top) << 13);
    }
    if(player == COMPUTER) {
	pos->to_move = N_COMPUTER;
    } else {
	pos->to_move = N_HUMAN;
    }
    pos->n_cards[N_COMPUTER] = nr_computer;
    pos->n_cards[N_HUMAN] = nr_human;
    pos->ply = 0;
    for(i=0; i<4 ; i++) {
	pos->cards[N_COMPUTER][i] = 0;
	pos->cards[N_HUMAN][i] = 0;
	pos->cards[N_TABLE][i] = 0;
    }
    for(i=0; i<nr_computer; i++) {
	c = computer[i];
	pos->cards[N_COMPUTER][SUIT1(c)] |= 1 << VALUE1(c);
    }
    for(i=0; i<nr_table; i++) {
	c = table[i];
	pos->cards[N_TABLE][SUIT1(c)] |= 1 << VALUE1(c);
    }
    for(i=0; i<nr_human; i++) {
	c = human[i];
	pos->cards[N_HUMAN][SUIT1(c)] |= 1 << VALUE1(c);
    }
}

#ifdef DEBUG
printmv(mv)
    int mv;
{
    int c, sc, vc;

    if(mv == 0) {
	fprintf(log, " pu ");
    } else {
	c = bit_to_int(mv);
	fprintf(log, " %c%c ", "AKQJX98765432"[VALUE(c)], "scdh"[SUIT(c)]);
    }
}

printmve(level, mv, e)
    int level, mv, e;
{
    fprintf(log, "level:%d ", level);
    printmv(mv);
    fprintf(log, " = %d \n", e);
}

print_pos(pos)
    position *pos;
{
    int s, c, bl;
    int *cp;

    fprintf(log, "\n******************\n");
    fprintf(log, "computer : \n");
    cp = pos->cards[N_COMPUTER];
    for(s = 0; s < 4; s++) {
	bl = 0;
	for(c = 1; c <= jimmy; c = c << 1) {
	    if(c & cp[s]) {
		bl = 1;
		printmv(c + (s << 13));
	    }
	}
	if(bl) {
	    fprintf(log, " \n");
	}
    }
    fprintf(log, "human : \n");
    cp = pos->cards[N_HUMAN];
    for(s = 0; s < 4; s++) {
	bl = 0;
	for(c = 1; c <= jimmy; c = c << 1) {
	    if(c & cp[s]) {
		bl = 1;
		printmv(c + (s << 13));
	    }
	}
	if(bl) {
	    fprintf(log, " \n");
	}
    }
    fprintf(log, "table    : \n");
    cp = pos->cards[N_TABLE];
    for(s = 0; s < 4; s++) {
	bl = 0;
	for(c = 1; c <= jimmy; c = c << 1) {
	    if(c & cp[s]) {
		bl = 1;
		printmv(c + (s << 13));
	    }
	}
	if(bl) {
	    fprintf(log, " \n");
	}
    }
    if(pos->top) {
	fprintf(log, "on top >>>>");
	printmv(pos->top);
	fprintf(log, " <<<<\n");
    }
}
#endif

zero_strategy(player)
    int player;
{
    int i, j = PICK_UP, iresult, jresult, nr_deck;
    char *deck;

    last_score = 0;
    if(player == COMPUTER) {
	deck = &computer[0];
	nr_deck = nr_computer;
    } else {
	deck = &human[0];
	nr_deck = nr_human;
    }
    jresult = evaluate_card(player, PICK_UP);
    for(i = 0; i < nr_deck; i++) {
	if(valid(player, i)) {
	    iresult = evaluate_card(player, deck[i]);
	    if(iresult > jresult) {
		j = i;
		jresult = iresult;
	    }
	}
    }
    return(j);
}

evaluate_card(player, card)
    int player, card;
{
    int value, suit;

    if(card == PICK_UP) {
	return(-1);
    }
    value = VALUE(card);
    suit = SUIT(card);
    if(((player == COMPUTER) && (suit == SPADES)) ||
       ((player == HUMAN) && (suit == HEARTS))) {
	return(value);
    }
    if(((player == COMPUTER) && (suit == HEARTS)) ||
       ((player == HUMAN) && (suit == SPADES))) {
	return(value + size);
    }
    return(value + size2);
}

accept_draw()
{
    return(last_score < -20);
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦263c9706b⟧ TextFile

Derivation

TextFile
