URL https://opencores.org/ocsvn/connect-6/connect-6/trunk

Subversion Repositories connect-6

[/] [connect-6/] [trunk/] [CONNECTK/] [connectk-2.0/] [src/] [state.c] - Blame information for rev 13

Go to most recent revision | Details | Compare with Previous | View Log


 
/*
 
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 <string.h>
#include <math.h>
#include "shared.h"
#include "connectk.h"
 
/*
 *      Allocation chain
 */
 
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");
                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");
                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)
{
        int i = 0, top = 0;
 
        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 = g_random_int_range(0, top);
        *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)
{
        int i;
 
        if (opt_det_ai)
                return;
 
        /* Fisher-Yates shuffle */
        for (i = 0; i < moves->len; i++) {
                int j;
 
                j = 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;
                }
        }
}
 
void aimoves_sort(AIMoves *moves)
{
        qsort(moves->data, moves->len, sizeof (AIMove), aimoves_compare);
}
 
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, board_stride, move_no, move_last,
    connect_k = 6, place_p = 2, start_q = 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));
}
 
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], NULL);
                c2 = count_pieces(b, x, y, type, -xs[i], -ys[i], NULL);
                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;
}

Browse

Tools

Subversion Repositories connect-6

[/] [connect-6/] [trunk/] [CONNECTK/] [connectk-2.0/] [src/] [state.c] - Blame information for rev 13

Line No.	Rev	Author	Line
1	3	sumanta.ch
2			`/*`
3
4			`connectk -- a program to play the connect-k family of games`
5			`Copyright (C) 2007 Michael Levin`
6
7			`This program is free software; you can redistribute it and/or`
8			`modify it under the terms of the GNU General Public License`
9			`as published by the Free Software Foundation; either version 2`
10			`of the License, or (at your option) any later version.`
11
12			`This program is distributed in the hope that it will be useful,`
13			`but WITHOUT ANY WARRANTY; without even the implied warranty of`
14			`MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the`
15			`GNU General Public License for more details.`
16
17			`You should have received a copy of the GNU General Public License`
18			`along with this program; if not, write to the Free Software`
19			`Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.`
20
21			`*/`
22
23			`#include "config.h"`
24			`#include <gtk/gtk.h>`
25			`#include <glib/gprintf.h>`
26			`#include <stdlib.h>`
27			`#include <string.h>`
28			`#include <math.h>`
29			`#include "shared.h"`
30			`#include "connectk.h"`
31
32			`/*`
33			`* Allocation chain`
34			`*/`
35
36			`static void achain_init(AllocChain *ac)`
37			`{`
38			`static unsigned int ids;`
39
40			`ac->free = FALSE;`
41			`ac->id = ids++;`
42			`}`
43
44			`AllocChain achain_new(AllocChain *root, AllocFunc afunc)`
45			`{`
46			`AllocChain *ac;`
47
48			`if (!*root) {`
49			`*root = afunc(NULL);`
50			`achain_init(*root);`
51			`(*root)->next = NULL;`
52			`return *root;`
53			`}`
54			`ac = *root;`
55			`for (;;) {`
56			`if (ac->free) {`
57			`afunc(ac);`
58			`achain_init(ac);`
59			`return ac;`
60			`}`
61			`if (!ac->next)`
62			`break;`
63			`ac = ac->next;`
64			`}`
65			`ac->next = afunc(NULL);`
66			`achain_init(ac->next);`
67			`ac->next->next = NULL;`
68			`return ac->next;`
69			`}`
70
71			`void achain_free(AllocChain *ac)`
72			`{`
73			`if (!ac)`
74			`return;`
75			`ac->free = TRUE;`
76			`}`
77
78			`void achain_copy(const AllocChain src, AllocChain dest, gsize mem)`
79			`{`
80			`if (!src \|\| !dest \|\| !mem) {`
81			`g_warning("NULL argument(s) to achain_copy");`
82			`return;`
83			`}`
84			`memcpy((char*)dest + sizeof (AllocChain),`
85			`(char*)src + sizeof (AllocChain), mem - sizeof (AllocChain));`
86			`}`
87
88			`static void achain_dealloc(AllocChain **root, gsize mem)`
89			`{`
90			`AllocChain ac = root, *ac_next;`
91
92			`while (ac) {`
93			`ac_next = ac->next;`
94			`g_slice_free1(mem, ac);`
95			`ac = ac_next;`
96			`}`
97			`*root = NULL;`
98			`}`
99
100			`/*`
101			`* Move Arrays`
102			`*/`
103
104			`AllocChain *aimoves_root = NULL;`
105			`gsize aimoves_mem = 0;`
106
107			`AllocChain aimoves_alloc(AllocChain ac)`
108			`{`
109			`if (!ac)`
110			`ac = (AllocChain*)g_slice_alloc(aimoves_mem);`
111			`memset((char*)ac + sizeof (AllocChain), 0, sizeof (AIMoves) -`
112			`sizeof (AllocChain));`
113			`return ac;`
114			`}`
115
116			`void aimoves_add(AIMoves moves, const AIMove move)`
117			`{`
118			`int i;`
119
120			`i = aimoves_find(moves, move->x, move->y);`
121			`if (i < 0) {`
122			`if (moves->len >= board_size * board_size)`
123			`g_warning("Attempted to add a move to a full AIMoves");`
124			`else`
125			`moves->data[moves->len++] = *move;`
126			`} else`
127			`moves->data[i].weight += move->weight;`
128			`}`
129
130			`void aimoves_append(AIMoves moves, const AIMove move)`
131			`{`
132			`int i;`
133
134			`if (move->x >= board_size \|\| move->y >= board_size)`
135			`return;`
136			`for (i = 0; i < moves->len; i++) {`
137			`AIMove *aim = moves->data + i;`
138
139			`if (aim->x == move->x && aim->y == move->y) {`
140			`aim->weight = move->weight;`
141			`return;`
142			`}`
143			`}`
144			`if (moves->len >= board_size * board_size) {`
145			`g_warning("Attempted to append a move to a full AIMoves");`
146			`return;`
147			`}`
148			`moves->data[moves->len++] = *move;`
149			`}`
150
151			`int aimoves_compare(const void a, const void b)`
152			`{`
153			`return ((AIMove)b)->weight - ((AIMove)a)->weight;`
154			`}`
155
156			`int aimoves_choose(AIMoves moves, AIMove move)`
157			`{`
158			`int i = 0, top = 0;`
159
160			`if (!moves \|\| !moves->len)`
161			`return 0;`
162			`aimoves_sort(moves);`
163			`for (top = 0; top < moves->len &&`
164			`moves->data[top].weight == moves->data[0].weight; top++);`
165			`if (top)`
166			`i = g_random_int_range(0, top);`
167			`*move = moves->data[i];`
168			`return 1;`
169			`}`
170
171			`void aimoves_crop(AIMoves *moves, unsigned int n)`
172			`{`
173			`if (moves->len < n)`
174			`return;`
175			`aimoves_shuffle(moves);`
176			`aimoves_sort(moves);`
177			`moves->len = n;`
178			`}`
179
180			`void aimoves_concat(AIMoves m1, const AIMoves m2)`
181			`{`
182			`gsize max_len = board_size * board_size, len;`
183
184			`len = m2->len;`
185			`if (m1->len + len > max_len)`
186			`len = max_len - m1->len;`
187			`memcpy(m1->data + len, m2->data, len * sizeof (AIMove));`
188			`m1->len += len;`
189			`}`
190
191			`AIMoves aimoves_dup(const AIMoves moves)`
192			`{`
193			`AIMoves *dup;`
194
195			`if (!moves)`
196			`return NULL;`
197			`dup = aimoves_new();`
198			`dup->len = moves->len;`
199			`memcpy(dup->data, moves->data, moves->len * sizeof (AIMove));`
200			`return dup;`
201			`}`
202
203			`int aimoves_find(const AIMoves *moves, BCOORD x, BCOORD y)`
204			`{`
205			`int i;`
206
207			`if (moves)`
208			`for (i = 0; i < moves->len; i++) {`
209			`const AIMove *aim = moves->data + i;`
210
211			`if (aim->x == x && aim->y == y)`
212			`return i;`
213			`}`
214			`return -1;`
215			`}`
216
217			`void aimoves_range(AIMoves moves, AIWEIGHT min, AIWEIGHT *max)`
218			`{`
219			`int i;`
220
221			`*min = AIW_MAX;`
222			`*max = AIW_MIN;`
223			`for (i = 0; i < moves->len; i++) {`
224			`if (moves->data[i].weight > *max)`
225			`*max = moves->data[i].weight;`
226			`if (moves->data[i].weight < *min)`
227			`*min = moves->data[i].weight;`
228			`}`
229			`}`
230
231			`void aimoves_merge(AIMoves m1, const AIMoves m2)`
232			`{`
233			`int len = m1->len, i, j;`
234
235			`for (i = 0; i < m2->len; i++)`
236			`for (j = 0;; j++) {`
237			`if (j >= len) {`
238			`aimoves_append(m1, m2->data + i);`
239			`break;`
240			`}`
241			`if (m1->data[j].x == m2->data[i].x &&`
242			`m1->data[j].y == m2->data[i].y) {`
243			`if (m2->data[i].weight > m1->data[j].weight)`
244			`m1->data[j].weight = m2->data[i].weight;`
245			`break;`
246			`}`
247			`}`
248			`}`
249
250			`char aimove_to_string(const AIMove aim)`
251			`{`
252			`static char buffer[32];`
253
254			`g_snprintf(buffer, sizeof (buffer), "%s (%s)",`
255			`bcoords_to_string(aim->x, aim->y),`
256			`aiw_to_string(aim->weight));`
257			`return buffer;`
258			`}`
259
260			`void aimoves_print(const AIMoves *moves)`
261			`{`
262			`int i;`
263
264			`if (!moves \|\| !moves->len) {`
265			`g_print("(empty)");`
266			`return;`
267			`}`
268			`for (i = 0; i < moves->len; i++) {`
269			`const AIMove *aim = moves->data + i;`
270
271			`if (i)`
272			`g_print(", ");`
273			`g_print("%s", aimove_to_string(aim));`
274			`}`
275			`}`
276
277			`void aimoves_remove_index_fast(AIMoves *moves, int i)`
278			`{`
279			`if (moves->len > i)`
280			`moves->data[i] = moves->data[moves->len - 1];`
281			`moves->len--;`
282			`}`
283
284			`void aimoves_remove(AIMoves *moves, BCOORD x, BCOORD y)`
285			`{`
286			`int i;`
287
288			`for (i = 0; i < moves->len; i++) {`
289			`AIMove *aim = moves->data + i;`
290
291			`if (aim->x == x && aim->y == y) {`
292			`aimoves_remove_index_fast(moves, i);`
293			`return;`
294			`}`
295			`}`
296			`}`
297
298			`void aimoves_shuffle(AIMoves *moves)`
299			`{`
300			`int i;`
301
302			`if (opt_det_ai)`
303			`return;`
304
305			`/* Fisher-Yates shuffle */`
306			`for (i = 0; i < moves->len; i++) {`
307			`int j;`
308
309			`j = g_random_int_range(i, moves->len);`
310			`if (i != j) {`
311			`AIMove tmp;`
312
313			`tmp = moves->data[i];`
314			`moves->data[i] = moves->data[j];`
315			`moves->data[j] = tmp;`
316			`}`
317			`}`
318			`}`
319
320			`void aimoves_sort(AIMoves *moves)`
321			`{`
322			`qsort(moves->data, moves->len, sizeof (AIMove), aimoves_compare);`
323			`}`
324
325			`void aimoves_subtract(AIMoves m1, const AIMoves m2)`
326			`{`
327			`int i, j;`
328
329			`for (i = 0; i < m1->len; i++)`
330			`for (j = 0; j < m2->len; j++)`
331			`if (m1->data[i].x == m2->data[j].x &&`
332			`m1->data[i].y == m2->data[j].y) {`
333			`aimoves_remove_index_fast(m1, i--);`
334			`break;`
335			`}`
336			`}`
337
338			`const char *aiw_to_string(AIWEIGHT w)`
339			`{`
340			`static char buffer[32];`
341
342			`switch (w) {`
343			`case AIW_WIN:`
344			`return "WIN";`
345			`case AIW_LOSE:`
346			`return "LOSS";`
347			`case AIW_NONE:`
348			`return "NONE";`
349			`default:`
350			`break;`
351			`}`
352			`if (w > 0)`
353			`g_snprintf(buffer, sizeof (buffer), "%010d (10^%.2f)", w,`
354			`log10((double)w));`
355			`else if (w < 0)`
356			`g_snprintf(buffer, sizeof (buffer), "%010d (-10^%.2f)", w,`
357			`log10((double)-w));`
358			`return buffer;`
359			`}`
360
361			`/*`
362			`* Boards`
363			`*/`
364
365			`Board *board;`
366			`AllocChain *board_root = NULL;`
367			`int board_size, board_stride, move_no, move_last,`
368			`connect_k = 6, place_p = 2, start_q = 1;`
369			`gsize board_mem = 0;`
370
371			`Player players[PIECES] = {`
372			`{ PLAYER_HUMAN, SEARCH_NONE, 0 },`
373			`{ PLAYER_HUMAN, SEARCH_NONE, 0 },`
374			`{ PLAYER_HUMAN, SEARCH_NONE, 0 },`
375			`};`
376
377			`static GPtrArray *history = NULL;`
378
379			`static void board_init(Board *b)`
380			`{`
381			`memset((char*)b + sizeof (AllocChain), 0, sizeof (Board) -`
382			`sizeof (AllocChain));`
383			`}`
384
385			`AllocChain board_alloc(AllocChain ac)`
386			`{`
387			`Board b = (Board)ac;`
388			`int i;`
389
390			`/* Clear the old board */`
391			`if (b) {`
392			`for (i = 1; i <= board_size; i++)`
393			`memset(b->data + board_stride * i + 1, 0,`
394			`board_size * sizeof (PIECE));`
395			`board_init(b);`
396			`return (AllocChain*)b;`
397			`}`
398
399			`/* New boards are allocated with a 1-tile wide boundary of PIECE_ERROR`
400			`around the edges */`
401			`b = (Board*)g_slice_alloc0(board_mem);`
402			`memset(b->data, PIECE_ERROR, sizeof (PIECE) * board_stride);`
403			`for (i = 1; i <= board_size; i++) {`
404			`b->data[i * board_stride] = PIECE_ERROR;`
405			`memset(b->data + board_stride * i + 1, 0,`
406			`board_size * sizeof (PIECE));`
407			`b->data[(i + 1) * board_stride - 1] = PIECE_ERROR;`
408			`}`
409			`memset(b->data + board_stride * (board_stride - 1), PIECE_ERROR,`
410			`sizeof (PIECE) * board_stride);`
411			`board_init(b);`
412			`return (AllocChain*)b;`
413			`}`
414
415			`void board_clean(Board *b)`
416			`{`
417			`int y, x;`
418
419			`for (y = 0; y < board_size; y++)`
420			`for (x = 0; x < board_size; x++)`
421			`if (piece_at(b, x, y) >= PIECES)`
422			`place_piece_type(b, x, y, PIECE_NONE);`
423			`}`
424
425			`void set_board_size(unsigned int size)`
426			`{`
427			`if (board_size == size)`
428			`return;`
429			`draw_marks(NULL, FALSE);`
430			`achain_dealloc(&board_root, board_mem);`
431			`achain_dealloc(&aimoves_root, aimoves_mem);`
432			`board_size = size;`
433			`board_stride = size + 2;`
434			`board_mem = sizeof (Board) + board_stride * board_stride *`
435			`sizeof (PIECE);`
436			`aimoves_mem = sizeof (AIMoves) + size * size * sizeof (AIMove);`
437			`}`
438
439			`Board *board_at(unsigned int move)`
440			`{`
441			`if (move >= history->len)`
442			`return NULL;`
443			`return (Board*)g_ptr_array_index(history, move);`
444			`}`
445
446			`int count_pieces(const Board *b, BCOORD x, BCOORD y, PIECE type, int dx, int dy,`
447			`PIECE *out)`
448			`{`
449			`int i;`
450			`PIECE p = PIECE_NONE;`
451
452			`if (!dx && !dy)`
453			`return piece_at(b, x, y) == type ? 1 : 0;`
454			`for (i = 0; x >= 0 && x < board_size && y >= 0 && y < board_size; i++) {`
455			`p = piece_at(b, x, y);`
456			`if (p != type)`
457			`break;`
458			`x += dx;`
459			`y += dy;`
460			`}`
461			`if (out)`
462			`*out = p;`
463			`return i;`
464			`}`
465
466			`gboolean check_win_full(const Board *b, BCOORD x, BCOORD y,`
467			`BCOORD x1, BCOORD y1, BCOORD x2, BCOORD y2)`
468			`{`
469			`int i, c1, c2, xs[] = {1, 1, 0, -1}, ys[] = {0, 1, 1, 1};`
470			`PIECE type;`
471
472			`type = piece_at(b, x, y);`
473			`if (type != PIECE_BLACK && type != PIECE_WHITE)`
474			`return FALSE;`
475			`for (i = 0; i < 4; i++) {`
476			`c1 = count_pieces(b, x, y, type, xs[i], ys[i], NULL);`
477			`c2 = count_pieces(b, x, y, type, -xs[i], -ys[i], NULL);`
478			`if (c1 + c2 > connect_k) {`
479			`if (x1)`
480			`x1 = x + xs[i] (c1 - 1);`
481			`if (y1)`
482			`y1 = y + ys[i] (c1 - 1);`
483			`if (x2)`
484			`x2 = x - xs[i] (c2 - 1);`
485			`if (y2)`
486			`y2 = y - ys[i] (c2 - 1);`
487			`return TRUE;`
488			`}`
489			`}`
490			`return FALSE;`
491			`}`
492
493			`/* Convert a boord coordinate to alpha representation */`
494			`const char *bcoord_to_alpha(BCOORD x)`
495			`{`
496			`static char buf[2][32];`
497			`static int which;`
498			`int i, divisor = 26;`
499
500			`which = !which;`
501			`for (i = 0; i < sizeof (buf[which]) - 1; i++) {`
502			`div_t result;`
503
504			`result = div(x, divisor);`
505			`buf[which][i] = 'a' + result.rem * 26 / divisor;`
506			`if (i)`
507			`buf[which][i]--;`
508			`x -= result.rem;`
509			`if (!x)`
510			`break;`
511			`divisor *= 26;`
512			`}`
513			`buf[which][i + 1] = 0;`
514			`return g_strreverse(buf[which]);`
515			`}`
516
517			`// Get a string representation of board x/y coordinates (d7, h16, etc)`
518			`const char *bcoords_to_string(BCOORD x, BCOORD y)`
519			`{`
520			`static char buf[2][32];`
521			`static int which;`
522
523			`which = !which;`
524			`g_snprintf(buf[which], sizeof (buf[which]), "%s%d",`
525			`bcoord_to_alpha(x), board_size - y);`
526			`return buf[which];`
527			`}`
528
529			`/* Convert a string representation to coordinates */`
530			`void string_to_bcoords(const char str, BCOORD x, BCOORD *y)`
531			`{`
532			`*x = 0;`
533			`*y = 0;`
534			`while (str && str >= 'a' && *str <= 'z') {`
535			`x = 26;`
536			`x += str - 'a';`
537			`str++;`
538			`}`
539			`while (str && str >= '0' && *str <= '9') {`
540			`y = 10;`
541			`y += str - '0';`
542			`str++;`
543			`}`
544			`if (*y)`
545			`y = board_size - y;`
546			`}`
547
548			`const char *piece_to_string(PIECE piece)`
549			`{`
550			`switch (piece) {`
551			`case PIECE_WHITE:`
552			`return "White";`
553			`case PIECE_BLACK:`
554			`return "Black";`
555			`case PIECE_NONE:`
556			`return "None";`
557			`case PIECE_ERROR:`
558			`return "Error";`
559			`default:`
560			`return "Mark";`
561			`}`
562			`}`
563
564			`char piece_to_char(PIECE piece)`
565			`{`
566			`switch (piece) {`
567			`case PIECE_WHITE:`
568			`return 'W';`
569			`case PIECE_BLACK:`
570			`return 'B';`
571			`case PIECE_NONE:`
572			`return '_';`
573			`case PIECE_ERROR:`
574			`return 'E';`
575			`default:`
576			`return 'M';`
577			`}`
578			`}`
579
580			`char *search_to_string(SEARCH s)`
581			`{`
582			`switch (s) {`
583			`case SEARCH_NONE:`
584			`return "No search";`
585			`case SEARCH_DFS:`
586			`return "Depth first search";`
587			`case SEARCHES:`
588			`break;`
589			`}`
590			`return "Unknown";`
591			`}`
592
593			`void go_to_move(unsigned int move)`
594			`{`
595			`Board *board2;`
596
597			`if (!history)`
598			`history = g_ptr_array_sized_new(32);`
599			`if (move > history->len)`
600			`move = history->len;`
601			`if (move == history->len) {`
602			`board2 = board_new();`
603			`if (board)`
604			`board_copy(board, board2);`
605			`g_ptr_array_add(history, board2);`
606			`board2->parent = board;`
607			`} else`
608			`board2 = (Board*)g_ptr_array_index(history, move);`
609			`board = board2;`
610			`move_no = move;`
611			`if (move_no > move_last)`
612			`move_last = move_no;`
613			`}`
614
615			`void clear_history(unsigned int from)`
616			`{`
617			`int i;`
618
619			`if (!history)`
620			`return;`
621			`if (from >= history->len) {`
622			`g_warning("Attempted to clear future history");`
623			`return;`
624			`}`
625			`for (i = from; i < history->len; i++)`
626			`board_free(g_ptr_array_index(history, i));`
627			`g_ptr_array_remove_range(history, from, history->len - from);`
628			`move_last = from;`
629			`}`