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 <iostream>
#include "shared.h"
//#include "q.hpp"
//#include "connectk.h"
#ifdef PICO_SYNTH
//#include "pico.h"
#endif
//#include "./q.hpp"
using namespace std;
/*
 *      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. */
 
 
//int ready=0;
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;
}
//FIFO(moves_fifo,AIMove);
//#pragma fifo_length moves_fifo 361
void aimoves_append(AIMoves *moves, const AIMove *move)
{
        int i;
 
        if (move->x >= board_size || move->y >= board_size)
                return;
	#pragma num_iterations(0,150,361)
        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;
	//if(!moves_fifo.full()) moves_fifo.push(*move);
}
 
int aimoves_compare(const void *a, const void *b)
{
        return ((AIMove*)b)->weight - ((AIMove*)a)->weight;
}
 
int aimoves_choose(AIMoves *moves, AIMove *move/*,index_array *index*/)
{
	//#pragma read_write_ports moves.data combined 3
	//#pragma internal_blockram moves
	//#pragma no_memory_analysis moves
 
        int i = 0;
        int top;
	AIMoves moves1;
	#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;
	/*---------------------------------------
		Rewritten for Hardware
	---------------------------------------*/
        //for (top = 0; top < moves->len; top++){
	//	if(top==0) {
	//			 if (!moves)
        //	        	return 0;
	//	}
	//	if(moves->data[index[top]].weight != moves->data[index[0]].weight){
	//		*move = moves->data[index[i]];
	//		return 1;
	//	}
	//	if(top==moves->len-1) {
	//		*move = moves->data[index[i]];
	//		return 1;
	//	}
	//}
        //                return 0;
	//if(!moves|| !moves->len) return 0;
	//else {*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 swap_bis(AIMove *list,int index1,int index2){
	AIMove temp;
	temp=list[index1];
	list[index1]=list[index2];
	list[index2]=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]);
                    swap_bis(list,j,j+1);
				//cout<<"BUBBLESORT"<<":"<<n<<endl;
				//for(i=0;i<n;i++) cout<<list[i].weight<<",";
				//cout<<endl;
}
//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);
	//streamsort(moves->data,moves->len);
 
}
void aimoves_sort_bis(AIMoves moves[2][16],int depth,int branch)
{
        //qsort(moves->data, moves->len, sizeof (AIMove), aimoves_compare);
	//bublesort(moves[depth][branch].data,moves[depth][branch].len);
   int n=moves[depth][branch].len;
   int i,j;
   for(i=0;i<(n-1);i++)
      for(j=0;j<(n-(i+1));j++)
             if(moves[depth][branch].data[j].weight < moves[depth][branch].data[j+1].weight){
		//swap
		AIMove temp;
		temp=moves[depth][branch].data[j];
		moves[depth][branch].data[j]=moves[depth][branch].data[j+1];
		moves[depth][branch].data[j+1]=temp;
 
		}
	//streamsort(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;
        }
	/* this two lines create problem in synthesis  preprocess ?? */
        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;
	PIECE p;
	if(x<0 || y<0) return FALSE;
        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], &p);
                c2 = count_pieces(b, x, y, type, -xs[i], -ys[i], &p);
                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)
{
        //tree_view_clear(1);
        //clear_history(0);
        //set_board_size(size);
        //board = NULL;
        //go_to_move(0);
	//move_last=0;
	//move_no=0;
	board_init(board);
        board->moves_left = start_q;
        board->turn = PIECE_BLACK;
        //draw_board();
        //stop_ai();
        //setup_move();
}
void board_copy(const Board *from, Board *to){
int i,j;
for(i=0;i<board_stride;i++)
	for(j=0;j<board_stride;j++)
		to->data[i][j]=from->data[i][j];
 
	to->ac=	from->ac;
	to->moves_left=	from->moves_left;
	to->parent =	from->parent;
	to->won    =	from->won;
	to->win_x1 =	from->win_x1;
	to->win_y1 =	from->win_y1;
	to->win_x2 =	from->win_x2;
	to->win_y2 =	from->win_y2;
	to->turn   =	from->turn;
	to->move_x =	from->move_x;
	to->move_y =	from->move_y;
 
 
}