Subversion Repositories connect-6

/*

connectk -- a program to play the connect-k family of games

Copyright (C) 2007 Michael Levin

This program is free software; you can redistribute it and/or

modify it under the terms of the GNU General Public License

as published by the Free Software Foundation; either version 2

of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

GNU General Public License for more details.

You should have received a copy of the GNU General Public License

along with this program; if not, write to the Free Software

Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

*/

//#include "config.h"

//#include <gtk/gtk.h>

//#include <glib/gprintf.h>

//#include <stdlib.h>

//#include <stdio.h>

//#include <string.h>

//#include <math.h>

#include "./shared.h"

//#include "connectk.h"

/*

 *      Allocation chain

 */

#define IA 1103515245u

#define IC 12345u

#define IM 2147483648u

#define CHECK_RAND

//moved the following declaration to connect6_threat

//static unsigned int current_random = 0;

//from vpr uti.c code

/* Portable random number generator defined below.  Taken from ANSI C by  *

 * K & R.  Not a great generator, but fast, and good enough for my needs. */

void my_srandom(int seed,unsigned int *current_random)

{

    *current_random = (unsigned int)seed;

}

int my_irand(int imax,unsigned int current_random)

{

///* Creates a random integer between 0 and imax, inclusive.  i.e. [0..imax] */

//

//    int ival;

//

///* current_random = (current_random * IA + IC) % IM; */

//    current_random = current_random * IA + IC;  /* Use overflow to wrap */

//    ival = current_random & (IM - 1);   /* Modulus */

//      //float not synthesizable

//    //ival = (int)((float)ival * (float)(imax + 0.999) / (float)IM);

//    ival = (int)(ival * (imax + 1) / IM);

//

//#ifdef CHECK_RAND

//    if((ival < 0) || (ival > imax))

//        {

//            //printf("Bad value in my_irand, imax = %d  ival = %d\n", imax,

//            //       ival);

//            //exit(1);

//        }

//#endif

//

//    return (ival);

return(0);

}

//static void achain_init(AllocChain *ac)

//{

//        static unsigned int ids;

//

//        ac->free = FALSE;

//        ac->id = ids++;

//}

//

//AllocChain *achain_new(AllocChain **root, AllocFunc afunc)

//{

//        AllocChain *ac;

//

//        if (!*root) {

//                *root = afunc(NULL);

//                achain_init(*root);

//                (*root)->next = NULL;

//                return *root;

//        }

//        ac = *root;

//        for (;;) {

//                if (ac->free) {

//                        afunc(ac);

//                        achain_init(ac);

//                        return ac;

//                }

//                if (!ac->next)

//                        break;

//                ac = ac->next;

//        }

//        ac->next = afunc(NULL);

//        achain_init(ac->next);

//        ac->next->next = NULL;

//        return ac->next;

//}

//

//void achain_free(AllocChain *ac)

//{

//        if (!ac)

//                return;

//        ac->free = TRUE;

//}

//

//void achain_copy(const AllocChain *src, AllocChain *dest, gsize mem)

//{

//        if (!src || !dest || !mem) {

//                g_warning("NULL argument(s) to achain_copy");

//                return;

//        }

//        memcpy((char*)dest + sizeof (AllocChain),

//               (char*)src + sizeof (AllocChain), mem - sizeof (AllocChain));

//}

//

//static void achain_dealloc(AllocChain **root, gsize mem)

//{

//        AllocChain *ac = *root, *ac_next;

//

//        while (ac) {

//                ac_next = ac->next;

//                g_slice_free1(mem, ac);

//                ac = ac_next;

//        }

//        *root = NULL;

//}

//      Move Arrays

//AllocChain *aimoves_root = NULL;

gsize aimoves_mem = 0;

//AllocChain *aimoves_alloc(AllocChain *ac)

//{

//        //if (!ac)

//        //        ac = (AllocChain*)g_slice_alloc(aimoves_mem);

//        //memset((char*)ac + sizeof (AllocChain), 0, sizeof (AIMoves) -

//        //       sizeof (AllocChain));

//        //return ac;

//}

void aimoves_add(AIMoves *moves, const AIMove *move)

{

        int i;

        i = aimoves_find(moves, move->x, move->y);

        if (i < 0) {

                if (moves->len >= board_size * board_size)

                        //g_warning("Attempted to add a move to a full AIMoves");

                        //printf("Attempted to add a move to a full AIMoves");

                        return;

                else

                        moves->data[moves->len++] = *move;

        } else

                moves->data[i].weight += move->weight;

}

void aimoves_append(AIMoves *moves, const AIMove *move)

{

        int i;

        if (move->x >= board_size || move->y >= board_size)

                return;

        for (i = 0; i < moves->len; i++) {

                AIMove *aim = moves->data + i;

                if (aim->x == move->x && aim->y == move->y) {

                        aim->weight = move->weight;

                        return;

                }

        }

        if (moves->len >= board_size * board_size) {

                //g_warning("Attempted to append a move to a full AIMoves");

                //printf("Attempted to append a move to a full AIMoves");

                return;

        }

        moves->data[moves->len++] = *move;

}

int aimoves_compare(const void *a, const void *b)

{

        return ((AIMove*)b)->weight - ((AIMove*)a)->weight;

}

int aimoves_choose(AIMoves *moves, AIMove *move)

{

        //#pragma read_write_ports moves.data combined 3

        //#pragma internal_blockram moves

        //#pragma no_memory_analysis moves

        int i = 0, top = 0;

        #pragma bitsize i 4

        if (!moves || !moves->len)

                return 0;

        aimoves_sort(moves);

        for (top = 0; top < moves->len &&

             moves->data[top].weight == moves->data[0].weight; top++);

        if (top)

                //i = my_irand(top,current_random);//g_random_int_range(0, top);

                i=0;

        *move = moves->data[i];

        return 1;

}

//

//void aimoves_crop(AIMoves *moves, unsigned int n)

//{

//        if (moves->len < n)

//                return;

//        aimoves_shuffle(moves);

//        aimoves_sort(moves);

//        moves->len = n;

//}

//

//void aimoves_concat(AIMoves *m1, const AIMoves *m2)

//{

//        gsize max_len = board_size * board_size, len;

//

//        len = m2->len;

//        if (m1->len + len > max_len)

//                len = max_len - m1->len;

//        memcpy(m1->data + len, m2->data, len * sizeof (AIMove));

//        m1->len += len;

//}

//

//AIMoves *aimoves_dup(const AIMoves *moves)

//{

//        AIMoves *dup;

//

//        if (!moves)

//                return NULL;

//        dup = aimoves_new();

//        dup->len = moves->len;

//        memcpy(dup->data, moves->data, moves->len * sizeof (AIMove));

//        return dup;

//}

//

int aimoves_find(const AIMoves *moves, BCOORD x, BCOORD y)

{

        int i;

        if (moves)

                for (i = 0; i < moves->len; i++) {

                        const AIMove *aim = moves->data + i;

                        if (aim->x == x && aim->y == y)

                                return i;

                }

        return -1;

}

//

//void aimoves_range(AIMoves *moves, AIWEIGHT *min, AIWEIGHT *max)

//{

//        int i;

//

//        *min = AIW_MAX;

//        *max = AIW_MIN;

//        for (i = 0; i < moves->len; i++) {

//                if (moves->data[i].weight > *max)

//                        *max = moves->data[i].weight;

//                if (moves->data[i].weight < *min)

//                        *min = moves->data[i].weight;

//        }

//}

//

//void aimoves_merge(AIMoves *m1, const AIMoves *m2)

//{

//        int len = m1->len, i, j;

//

//        for (i = 0; i < m2->len; i++)

//                for (j = 0;; j++) {

//                        if (j >= len) {

//                                aimoves_append(m1, m2->data + i);

//                                break;

//                        }

//                        if (m1->data[j].x == m2->data[i].x &&

//                            m1->data[j].y == m2->data[i].y) {

//                                if (m2->data[i].weight > m1->data[j].weight)

//                                        m1->data[j].weight = m2->data[i].weight;

//                                break;

//                        }

//                }

//}

//

//char *aimove_to_string(const AIMove *aim)

//{

//        static char buffer[32];

//

//        g_snprintf(buffer, sizeof (buffer), "%s (%s)",

//                   bcoords_to_string(aim->x, aim->y),

//                   aiw_to_string(aim->weight));

//        return buffer;

//}

//

//void aimoves_print(const AIMoves *moves)

//{

//        int i;

//

//        if (!moves || !moves->len) {

//                g_print("(empty)");

//                return;

//        }

//        for (i = 0; i < moves->len; i++) {

//                const AIMove *aim = moves->data + i;

//

//                if (i)

//                        g_print(", ");

//                g_print("%s", aimove_to_string(aim));

//        }

//}

//

//void aimoves_remove_index_fast(AIMoves *moves, int i)

//{

//        if (moves->len > i)

//                moves->data[i] = moves->data[moves->len - 1];

//        moves->len--;

//}

//

//void aimoves_remove(AIMoves *moves, BCOORD x, BCOORD y)

//{

//        int i;

//

//        for (i = 0; i < moves->len; i++) {

//                AIMove *aim = moves->data + i;

//

//                if (aim->x == x && aim->y == y) {

//                        aimoves_remove_index_fast(moves, i);

//                        return;

//                }

//        }

//}

//

void aimoves_shuffle(AIMoves *moves,unsigned int current_random)

{

//        int i;

//

//        if (opt_det_ai)

//                return;

//

//        /* Fisher-Yates shuffle */

//        for (i = 0; i < moves->len; i++) {

//                int j;

//

//                j = my_irand(moves->len,current_random);//g_random_int_range(i, moves->len);

//                if (i != j) {

//                        AIMove tmp;

//

//                        tmp = moves->data[i];

//                        moves->data[i] = moves->data[j];

//                        moves->data[j] = tmp;

//                }

//        }

return;

}

//taken from http://cprogramminglanguage.net/c-bubble-sort-source-code.aspx

void swap(AIMove  *x,AIMove *y)

{

   AIMove temp;

   temp = *x;

   *x = *y;

   *y = temp;

}

void bublesort(AIMove *list, int n)

{

   int i,j;

   for(i=0;i<(n-1);i++)

      for(j=0;j<(n-(i+1));j++)

             if(list[j].weight < list[j+1].weight)

                    swap(&list[j],&list[j+1]);

}

//taken from http://cprogramminglanguage.net/c-bubble-sort-source-code.aspx

void aimoves_sort(AIMoves *moves)

{

        //qsort(moves->data, moves->len, sizeof (AIMove), aimoves_compare);

        bublesort(moves->data,moves->len);

}

//void aimoves_subtract(AIMoves *m1, const AIMoves *m2)

//{

//        int i, j;

//

//        for (i = 0; i < m1->len; i++)

//                for (j = 0; j < m2->len; j++)

//                        if (m1->data[i].x == m2->data[j].x &&

//                            m1->data[i].y == m2->data[j].y) {

//                                aimoves_remove_index_fast(m1, i--);

//                                break;

//                        }

//}

//

//const char *aiw_to_string(AIWEIGHT w)

//{

//        static char buffer[32];

//

//        switch (w) {

//        case AIW_WIN:

//                return "WIN";

//        case AIW_LOSE:

//                return "LOSS";

//        case AIW_NONE:

//                return "NONE";

//        default:

//                break;

//        }

//        if (w > 0)

//                g_snprintf(buffer, sizeof (buffer), "%010d (10^%.2f)", w,

//                           log10((double)w));

//        else if (w < 0)

//                g_snprintf(buffer, sizeof (buffer), "%010d (-10^%.2f)", w,

//                           log10((double)-w));

//        return buffer;

//}

/*

 *      Boards

 */

//Board board;

//AllocChain *board_root = NULL;

//int board_size=19, board_stride=21, move_no, move_last,

//    connect_k = 6, place_p = 2, start_q = 1;

//int opt_det_ai=1;

//gsize board_mem = 0;

//Player players[PIECES] = {

//        { PLAYER_HUMAN, SEARCH_NONE, 0 },

//        { PLAYER_HUMAN, SEARCH_NONE, 0 },

//        { PLAYER_HUMAN, SEARCH_NONE, 0 },

//};

//

//static GPtrArray *history = NULL;

static void board_init(Board *b)

{

//        memset((char*)b + sizeof (AllocChain), 0, sizeof (Board) -

//               sizeof (AllocChain));

int i,j;

for(i=0;i<board_stride;i++)

        b->data[i][0]=PIECE_ERROR;

for(i=0;i<board_stride;i++)

        b->data[i][board_stride-1]=PIECE_ERROR;

for(j=0;j<board_stride;j++)

        b->data[0][j]=PIECE_ERROR;

for(j=0;j<board_stride;j++)

        b->data[board_stride-1][j]=PIECE_ERROR;

for(i=1;i<board_stride-1;i++)

        for(j=1;j<board_stride-1;j++)

                b->data[i][j]=PIECE_NONE;

        //b->ac=(const AllocChain )0;   

        b->moves_left=0;

        b->parent =0;

        b->won    =0;

        b->win_x1 =0;

        b->win_y1 =0;

        b->win_x2 =0;

        b->win_y2 =0;

        b->turn   =0;

        b->move_x =0;

        b->move_y =0;

}

//AllocChain *board_alloc(AllocChain *ac)

//{

//        //Board *b = (Board*)ac;

//        //int i;

//

//        ///* Clear the old board */

//        //if (b) {

//        //        for (i = 1; i <= board_size; i++)

//        //                memset(b->data + board_stride * i + 1, 0,

//        //                       board_size * sizeof (PIECE));

//        //        board_init(b);

//        //        return (AllocChain*)b;

//        //}

//

//        ///* New boards are allocated with a 1-tile wide boundary of PIECE_ERROR

//        //   around the edges */

//        //b = (Board*)g_slice_alloc0(board_mem);

//        //memset(b->data, PIECE_ERROR, sizeof (PIECE) * board_stride);

//        //for (i = 1; i <= board_size; i++) {

//        //        b->data[i * board_stride] = PIECE_ERROR;

//        //        memset(b->data + board_stride * i + 1, 0,

//        //               board_size * sizeof (PIECE));

//        //        b->data[(i + 1) * board_stride - 1] = PIECE_ERROR;

//        //}

//        //memset(b->data + board_stride * (board_stride - 1), PIECE_ERROR,

//        //       sizeof (PIECE) * board_stride);

//        //board_init(&b);

//        //return (AllocChain*)b;

//}

void board_clean(Board *b)

{

        int y, x;

        for (y = 0; y < board_size; y++)

                for (x = 0; x < board_size; x++)

                        if (piece_at(b, x, y) >= PIECES)

                                place_piece_type(b, x, y, PIECE_NONE);

}

//void set_board_size(unsigned int size)

//{

//        //if (board_size == size)

//        //        return;

//        ////draw_marks(NULL, FALSE);

//        //achain_dealloc(&board_root, board_mem);

//        achain_dealloc(&aimoves_root, aimoves_mem);

//        //board_size = size;

//        //board_stride = size + 2;

//        //board_mem = sizeof (Board) + board_stride * board_stride *

//        //            sizeof (PIECE);

//        aimoves_mem = sizeof (AIMoves) + size * size * sizeof (AIMove);

//}

//Board *board_at(unsigned int move)

//{

//        if (move >= history->len)

//                return NULL;

//        return (Board*)g_ptr_array_index(history, move);

//}

int count_pieces(const Board *b, BCOORD x, BCOORD y, PIECE type, int dx, int dy,

                 PIECE *out)

{

        int i;

        PIECE p = PIECE_NONE;

        if (!dx && !dy)

                return piece_at(b, x, y) == type ? 1 : 0;

        for (i = 0; x >= 0 && x < board_size && y >= 0 && y < board_size; i++) {

                p = piece_at(b, x, y);

                if (p != type)

                        break;

                x += dx;

                y += dy;

        }

        if (out)

                *out = p;

        return i;

}

gboolean check_win_full(const Board *b, BCOORD x, BCOORD y,

                        BCOORD *x1, BCOORD *y1, BCOORD *x2, BCOORD *y2)

{

        int i, c1, c2, xs[] = {1, 1, 0, -1}, ys[] = {0, 1, 1, 1};

        PIECE type;

        type = piece_at(b, x, y);

        if (type != PIECE_BLACK && type != PIECE_WHITE)

                return FALSE;

        for (i = 0; i < 4; i++) {

                c1 = count_pieces(b, x, y, type, xs[i], ys[i], 0);

                c2 = count_pieces(b, x, y, type, -xs[i], -ys[i], 0);

                if (c1 + c2 > connect_k) {

                        if (x1)

                                *x1 = x + xs[i] * (c1 - 1);

                        if (y1)

                                *y1 = y + ys[i] * (c1 - 1);

                        if (x2)

                                *x2 = x - xs[i] * (c2 - 1);

                        if (y2)

                                *y2 = y - ys[i] * (c2 - 1);

                        return TRUE;

                }

        }

        return FALSE;

}

///* Convert a boord coordinate to alpha representation */

//const char *bcoord_to_alpha(BCOORD x)

//{

//        static char buf[2][32];

//        static int which;

//        int i, divisor = 26;

//

//        which = !which;

//        for (i = 0; i < sizeof (buf[which]) - 1; i++) {

//                div_t result;

//

//                result = div(x, divisor);

//                buf[which][i] = 'a' + result.rem * 26 / divisor;

//                if (i)

//                        buf[which][i]--;

//                x -= result.rem;

//                if (!x)

//                        break;

//                divisor *= 26;

//        }

//        buf[which][i + 1] = 0;

//        return g_strreverse(buf[which]);

//}

//// Get a string representation of board x/y coordinates (d7, h16, etc)

//const char *bcoords_to_string(BCOORD x, BCOORD y)

//{

//        static char buf[2][32];

//        static int which;

//

//        which = !which;

//        g_snprintf(buf[which], sizeof (buf[which]), "%s%d",

//                   bcoord_to_alpha(x), board_size - y);

//        return buf[which];

//}

//

/* Convert a string representation to coordinates */

void string_to_bcoords(const char *str, BCOORD *x, BCOORD *y)

{

        *x = 0;

        *y = 0;

        while (*str && *str >= 'a' && *str <= 'z') {

                *x *= 26;

                *x += *str - 'a';

                str++;

        }

        while (*str && *str >= '0' && *str <= '9') {

                *y *= 10;

                *y += *str - '0';

                str++;

        }

        if (*y)

                *y = board_size - *y;

}

const char *piece_to_string(PIECE piece)

{

        switch (piece) {

        case PIECE_WHITE:

                return "White";

        case PIECE_BLACK:

                return "Black";

        case PIECE_NONE:

                return "None";

        case PIECE_ERROR:

                return "Error";

        default:

                return "Mark";

        }

}

char piece_to_char(PIECE piece)

{

        switch (piece) {

        case PIECE_WHITE:

                return 'W';

        case PIECE_BLACK:

                return 'B';

        case PIECE_NONE:

                return '_';

        case PIECE_ERROR:

                return 'E';

        default:

                return 'M';

        }

}

//char *search_to_string(SEARCH s)

//{

//        switch (s) {

//        case SEARCH_NONE:

//                return "No search";

//        case SEARCH_DFS:

//                return "Depth first search";

//        case SEARCHES:

//                break;

//        }

//        return "Unknown";

//}

//void go_to_move(unsigned int move)

//{

//        Board board2;

//

//        if (!history)

//                history = g_ptr_array_sized_new(32);

//        if (move > history->len)

//                move = history->len;

//        if (move == history->len) {

//                //board2 = board_new();

//                if (&board)

//                        board_copy(&board, &board2);

//                g_ptr_array_add(history, &board2);

//                board2.parent = &board;

//        } else

//                //board2 = (Board*)g_ptr_array_index(history, move);

//        //&board = &board2;

//        move_no = move;

//        if (move_no > move_last)

//                move_last = move_no;

//}

//void clear_history(unsigned int from)

//{

//        int i;

//

//        if (!history)

//                return;

//        if (from >= history->len) {

//                g_warning("Attempted to clear future history");

//                return;

//        }

//        for (i = from; i < history->len; i++)

//                board_free(g_ptr_array_index(history, i));

//        g_ptr_array_remove_range(history, from, history->len - from);

//        move_last = from;

//}

/* Clear the board and history for a new game */

void new_game(Board *board,unsigned int size)

{