|
|
/*
|
/*
|
|
|
connectk -- a program to play the connect-k family of games
|
connectk -- a program to play the connect-k family of games
|
Copyright (C) 2007 Michael Levin
|
Copyright (C) 2007 Michael Levin
|
|
|
This program is free software; you can redistribute it and/or
|
This program is free software; you can redistribute it and/or
|
modify it under the terms of the GNU General Public License
|
modify it under the terms of the GNU General Public License
|
as published by the Free Software Foundation; either version 2
|
as published by the Free Software Foundation; either version 2
|
of the License, or (at your option) any later version.
|
of the License, or (at your option) any later version.
|
|
|
This program is distributed in the hope that it will be useful,
|
This program is distributed in the hope that it will be useful,
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
GNU General Public License for more details.
|
GNU General Public License for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with this program; if not, write to the Free Software
|
along with this program; if not, write to the Free Software
|
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
|
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
|
|
|
*/
|
*/
|
|
|
#include "config.h"
|
#include "config.h"
|
#include <gtk/gtk.h>
|
#include <gtk/gtk.h>
|
#include <glib/gprintf.h>
|
#include <glib/gprintf.h>
|
#include <stdlib.h>
|
#include <stdlib.h>
|
#include <string.h>
|
#include <string.h>
|
#include <math.h>
|
#include <math.h>
|
#include "shared.h"
|
#include "shared.h"
|
#include "connectk.h"
|
#include "connectk.h"
|
|
|
/*
|
/*
|
* Allocation chain
|
* Allocation chain
|
*/
|
*/
|
|
|
static void achain_init(AllocChain *ac)
|
static void achain_init(AllocChain *ac)
|
{
|
{
|
static unsigned int ids;
|
static unsigned int ids;
|
|
|
ac->free = FALSE;
|
ac->free = FALSE;
|
ac->id = ids++;
|
ac->id = ids++;
|
}
|
}
|
|
|
AllocChain *achain_new(AllocChain **root, AllocFunc afunc)
|
AllocChain *achain_new(AllocChain **root, AllocFunc afunc)
|
{
|
{
|
AllocChain *ac;
|
AllocChain *ac;
|
|
|
if (!*root) {
|
if (!*root) {
|
*root = afunc(NULL);
|
*root = afunc(NULL);
|
achain_init(*root);
|
achain_init(*root);
|
(*root)->next = NULL;
|
(*root)->next = NULL;
|
return *root;
|
return *root;
|
}
|
}
|
ac = *root;
|
ac = *root;
|
for (;;) {
|
for (;;) {
|
if (ac->free) {
|
if (ac->free) {
|
afunc(ac);
|
afunc(ac);
|
achain_init(ac);
|
achain_init(ac);
|
return ac;
|
return ac;
|
}
|
}
|
if (!ac->next)
|
if (!ac->next)
|
break;
|
break;
|
ac = ac->next;
|
ac = ac->next;
|
}
|
}
|
ac->next = afunc(NULL);
|
ac->next = afunc(NULL);
|
achain_init(ac->next);
|
achain_init(ac->next);
|
ac->next->next = NULL;
|
ac->next->next = NULL;
|
return ac->next;
|
return ac->next;
|
}
|
}
|
|
|
void achain_free(AllocChain *ac)
|
void achain_free(AllocChain *ac)
|
{
|
{
|
if (!ac)
|
if (!ac)
|
return;
|
return;
|
ac->free = TRUE;
|
ac->free = TRUE;
|
}
|
}
|
|
|
void achain_copy(const AllocChain *src, AllocChain *dest, gsize mem)
|
void achain_copy(const AllocChain *src, AllocChain *dest, gsize mem)
|
{
|
{
|
if (!src || !dest || !mem) {
|
if (!src || !dest || !mem) {
|
g_warning("NULL argument(s) to achain_copy");
|
g_warning("NULL argument(s) to achain_copy");
|
return;
|
return;
|
}
|
}
|
memcpy((char*)dest + sizeof (AllocChain),
|
memcpy((char*)dest + sizeof (AllocChain),
|
(char*)src + sizeof (AllocChain), mem - sizeof (AllocChain));
|
(char*)src + sizeof (AllocChain), mem - sizeof (AllocChain));
|
}
|
}
|
|
|
static void achain_dealloc(AllocChain **root, gsize mem)
|
static void achain_dealloc(AllocChain **root, gsize mem)
|
{
|
{
|
AllocChain *ac = *root, *ac_next;
|
AllocChain *ac = *root, *ac_next;
|
|
|
while (ac) {
|
while (ac) {
|
ac_next = ac->next;
|
ac_next = ac->next;
|
g_slice_free1(mem, ac);
|
g_slice_free1(mem, ac);
|
ac = ac_next;
|
ac = ac_next;
|
}
|
}
|
*root = NULL;
|
*root = NULL;
|
}
|
}
|
|
|
/*
|
/*
|
* Move Arrays
|
* Move Arrays
|
*/
|
*/
|
|
|
AllocChain *aimoves_root = NULL;
|
AllocChain *aimoves_root = NULL;
|
gsize aimoves_mem = 0;
|
gsize aimoves_mem = 0;
|
|
|
AllocChain *aimoves_alloc(AllocChain *ac)
|
AllocChain *aimoves_alloc(AllocChain *ac)
|
{
|
{
|
if (!ac)
|
if (!ac)
|
ac = (AllocChain*)g_slice_alloc(aimoves_mem);
|
ac = (AllocChain*)g_slice_alloc(aimoves_mem);
|
memset((char*)ac + sizeof (AllocChain), 0, sizeof (AIMoves) -
|
memset((char*)ac + sizeof (AllocChain), 0, sizeof (AIMoves) -
|
sizeof (AllocChain));
|
sizeof (AllocChain));
|
return ac;
|
return ac;
|
}
|
}
|
|
|
void aimoves_add(AIMoves *moves, const AIMove *move)
|
void aimoves_add(AIMoves *moves, const AIMove *move)
|
{
|
{
|
int i;
|
int i;
|
|
|
i = aimoves_find(moves, move->x, move->y);
|
i = aimoves_find(moves, move->x, move->y);
|
if (i < 0) {
|
if (i < 0) {
|
if (moves->len >= board_size * board_size)
|
if (moves->len >= board_size * board_size)
|
g_warning("Attempted to add a move to a full AIMoves");
|
g_warning("Attempted to add a move to a full AIMoves");
|
else
|
else
|
moves->data[moves->len++] = *move;
|
moves->data[moves->len++] = *move;
|
} else
|
} else
|
moves->data[i].weight += move->weight;
|
moves->data[i].weight += move->weight;
|
}
|
}
|
|
|
void aimoves_append(AIMoves *moves, const AIMove *move)
|
void aimoves_append(AIMoves *moves, const AIMove *move)
|
{
|
{
|
int i;
|
int i;
|
|
|
if (move->x >= board_size || move->y >= board_size)
|
if (move->x >= board_size || move->y >= board_size)
|
return;
|
return;
|
for (i = 0; i < moves->len; i++) {
|
for (i = 0; i < moves->len; i++) {
|
AIMove *aim = moves->data + i;
|
AIMove *aim = moves->data + i;
|
|
|
if (aim->x == move->x && aim->y == move->y) {
|
if (aim->x == move->x && aim->y == move->y) {
|
aim->weight = move->weight;
|
aim->weight = move->weight;
|
return;
|
return;
|
}
|
}
|
}
|
}
|
if (moves->len >= board_size * board_size) {
|
if (moves->len >= board_size * board_size) {
|
g_warning("Attempted to append a move to a full AIMoves");
|
g_warning("Attempted to append a move to a full AIMoves");
|
return;
|
return;
|
}
|
}
|
moves->data[moves->len++] = *move;
|
moves->data[moves->len++] = *move;
|
}
|
}
|
|
|
int aimoves_compare(const void *a, const void *b)
|
int aimoves_compare(const void *a, const void *b)
|
{
|
{
|
return ((AIMove*)b)->weight - ((AIMove*)a)->weight;
|
return ((AIMove*)b)->weight - ((AIMove*)a)->weight;
|
}
|
}
|
|
|
int aimoves_choose(AIMoves *moves, AIMove *move)
|
int aimoves_choose(AIMoves *moves, AIMove *move)
|
{
|
{
|
int i = 0, top = 0;
|
int i = 0, top = 0;
|
|
|
if (!moves || !moves->len)
|
if (!moves || !moves->len)
|
return 0;
|
return 0;
|
aimoves_sort(moves);
|
aimoves_sort(moves);
|
for (top = 0; top < moves->len &&
|
for (top = 0; top < moves->len &&
|
moves->data[top].weight == moves->data[0].weight; top++);
|
moves->data[top].weight == moves->data[0].weight; top++);
|
if (top)
|
if (top)
|
i = g_random_int_range(0, top);
|
i = g_random_int_range(0, top);
|
*move = moves->data[i];
|
*move = moves->data[i];
|
return 1;
|
return 1;
|
}
|
}
|
|
|
void aimoves_crop(AIMoves *moves, unsigned int n)
|
void aimoves_crop(AIMoves *moves, unsigned int n)
|
{
|
{
|
if (moves->len < n)
|
if (moves->len < n)
|
return;
|
return;
|
aimoves_shuffle(moves);
|
aimoves_shuffle(moves);
|
aimoves_sort(moves);
|
aimoves_sort(moves);
|
moves->len = n;
|
moves->len = n;
|
}
|
}
|
|
|
void aimoves_concat(AIMoves *m1, const AIMoves *m2)
|
void aimoves_concat(AIMoves *m1, const AIMoves *m2)
|
{
|
{
|
gsize max_len = board_size * board_size, len;
|
gsize max_len = board_size * board_size, len;
|
|
|
len = m2->len;
|
len = m2->len;
|
if (m1->len + len > max_len)
|
if (m1->len + len > max_len)
|
len = max_len - m1->len;
|
len = max_len - m1->len;
|
memcpy(m1->data + len, m2->data, len * sizeof (AIMove));
|
memcpy(m1->data + len, m2->data, len * sizeof (AIMove));
|
m1->len += len;
|
m1->len += len;
|
}
|
}
|
|
|
AIMoves *aimoves_dup(const AIMoves *moves)
|
AIMoves *aimoves_dup(const AIMoves *moves)
|
{
|
{
|
AIMoves *dup;
|
AIMoves *dup;
|
|
|
if (!moves)
|
if (!moves)
|
return NULL;
|
return NULL;
|
dup = aimoves_new();
|
dup = aimoves_new();
|
dup->len = moves->len;
|
dup->len = moves->len;
|
memcpy(dup->data, moves->data, moves->len * sizeof (AIMove));
|
memcpy(dup->data, moves->data, moves->len * sizeof (AIMove));
|
return dup;
|
return dup;
|
}
|
}
|
|
|
int aimoves_find(const AIMoves *moves, BCOORD x, BCOORD y)
|
int aimoves_find(const AIMoves *moves, BCOORD x, BCOORD y)
|
{
|
{
|
int i;
|
int i;
|
|
|
if (moves)
|
if (moves)
|
for (i = 0; i < moves->len; i++) {
|
for (i = 0; i < moves->len; i++) {
|
const AIMove *aim = moves->data + i;
|
const AIMove *aim = moves->data + i;
|
|
|
if (aim->x == x && aim->y == y)
|
if (aim->x == x && aim->y == y)
|
return i;
|
return i;
|
}
|
}
|
return -1;
|
return -1;
|
}
|
}
|
|
|
void aimoves_range(AIMoves *moves, AIWEIGHT *min, AIWEIGHT *max)
|
void aimoves_range(AIMoves *moves, AIWEIGHT *min, AIWEIGHT *max)
|
{
|
{
|
int i;
|
int i;
|
|
|
*min = AIW_MAX;
|
*min = AIW_MAX;
|
*max = AIW_MIN;
|
*max = AIW_MIN;
|
for (i = 0; i < moves->len; i++) {
|
for (i = 0; i < moves->len; i++) {
|
if (moves->data[i].weight > *max)
|
if (moves->data[i].weight > *max)
|
*max = moves->data[i].weight;
|
*max = moves->data[i].weight;
|
if (moves->data[i].weight < *min)
|
if (moves->data[i].weight < *min)
|
*min = moves->data[i].weight;
|
*min = moves->data[i].weight;
|
}
|
}
|
}
|
}
|
|
|
void aimoves_merge(AIMoves *m1, const AIMoves *m2)
|
void aimoves_merge(AIMoves *m1, const AIMoves *m2)
|
{
|
{
|
int len = m1->len, i, j;
|
int len = m1->len, i, j;
|
|
|
for (i = 0; i < m2->len; i++)
|
for (i = 0; i < m2->len; i++)
|
for (j = 0;; j++) {
|
for (j = 0;; j++) {
|
if (j >= len) {
|
if (j >= len) {
|
aimoves_append(m1, m2->data + i);
|
aimoves_append(m1, m2->data + i);
|
break;
|
break;
|
}
|
}
|
if (m1->data[j].x == m2->data[i].x &&
|
if (m1->data[j].x == m2->data[i].x &&
|
m1->data[j].y == m2->data[i].y) {
|
m1->data[j].y == m2->data[i].y) {
|
if (m2->data[i].weight > m1->data[j].weight)
|
if (m2->data[i].weight > m1->data[j].weight)
|
m1->data[j].weight = m2->data[i].weight;
|
m1->data[j].weight = m2->data[i].weight;
|
break;
|
break;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
char *aimove_to_string(const AIMove *aim)
|
char *aimove_to_string(const AIMove *aim)
|
{
|
{
|
static char buffer[32];
|
static char buffer[32];
|
|
|
g_snprintf(buffer, sizeof (buffer), "%s (%s)",
|
g_snprintf(buffer, sizeof (buffer), "%s (%s)",
|
bcoords_to_string(aim->x, aim->y),
|
bcoords_to_string(aim->x, aim->y),
|
aiw_to_string(aim->weight));
|
aiw_to_string(aim->weight));
|
return buffer;
|
return buffer;
|
}
|
}
|
|
|
void aimoves_print(const AIMoves *moves)
|
void aimoves_print(const AIMoves *moves)
|
{
|
{
|
int i;
|
int i;
|
|
|
if (!moves || !moves->len) {
|
if (!moves || !moves->len) {
|
g_print("(empty)");
|
g_print("(empty)");
|
return;
|
return;
|
}
|
}
|
for (i = 0; i < moves->len; i++) {
|
for (i = 0; i < moves->len; i++) {
|
const AIMove *aim = moves->data + i;
|
const AIMove *aim = moves->data + i;
|
|
|
if (i)
|
if (i)
|
g_print(", ");
|
g_print(", ");
|
g_print("%s", aimove_to_string(aim));
|
g_print("%s", aimove_to_string(aim));
|
}
|
}
|
}
|
}
|
|
|
void aimoves_remove_index_fast(AIMoves *moves, int i)
|
void aimoves_remove_index_fast(AIMoves *moves, int i)
|
{
|
{
|
if (moves->len > i)
|
if (moves->len > i)
|
moves->data[i] = moves->data[moves->len - 1];
|
moves->data[i] = moves->data[moves->len - 1];
|
moves->len--;
|
moves->len--;
|
}
|
}
|
|
|
void aimoves_remove(AIMoves *moves, BCOORD x, BCOORD y)
|
void aimoves_remove(AIMoves *moves, BCOORD x, BCOORD y)
|
{
|
{
|
int i;
|
int i;
|
|
|
for (i = 0; i < moves->len; i++) {
|
for (i = 0; i < moves->len; i++) {
|
AIMove *aim = moves->data + i;
|
AIMove *aim = moves->data + i;
|
|
|
if (aim->x == x && aim->y == y) {
|
if (aim->x == x && aim->y == y) {
|
aimoves_remove_index_fast(moves, i);
|
aimoves_remove_index_fast(moves, i);
|
return;
|
return;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
void aimoves_shuffle(AIMoves *moves)
|
void aimoves_shuffle(AIMoves *moves)
|
{
|
{
|
int i;
|
int i;
|
|
|
if (opt_det_ai)
|
if (opt_det_ai)
|
return;
|
return;
|
|
|
/* Fisher-Yates shuffle */
|
/* Fisher-Yates shuffle */
|
for (i = 0; i < moves->len; i++) {
|
for (i = 0; i < moves->len; i++) {
|
int j;
|
int j;
|
|
|
j = g_random_int_range(i, moves->len);
|
j = g_random_int_range(i, moves->len);
|
if (i != j) {
|
if (i != j) {
|
AIMove tmp;
|
AIMove tmp;
|
|
|
tmp = moves->data[i];
|
tmp = moves->data[i];
|
moves->data[i] = moves->data[j];
|
moves->data[i] = moves->data[j];
|
moves->data[j] = tmp;
|
moves->data[j] = tmp;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
void aimoves_sort(AIMoves *moves)
|
void aimoves_sort(AIMoves *moves)
|
{
|
{
|
qsort(moves->data, moves->len, sizeof (AIMove), aimoves_compare);
|
qsort(moves->data, moves->len, sizeof (AIMove), aimoves_compare);
|
}
|
}
|
|
|
void aimoves_subtract(AIMoves *m1, const AIMoves *m2)
|
void aimoves_subtract(AIMoves *m1, const AIMoves *m2)
|
{
|
{
|
int i, j;
|
int i, j;
|
|
|
for (i = 0; i < m1->len; i++)
|
for (i = 0; i < m1->len; i++)
|
for (j = 0; j < m2->len; j++)
|
for (j = 0; j < m2->len; j++)
|
if (m1->data[i].x == m2->data[j].x &&
|
if (m1->data[i].x == m2->data[j].x &&
|
m1->data[i].y == m2->data[j].y) {
|
m1->data[i].y == m2->data[j].y) {
|
aimoves_remove_index_fast(m1, i--);
|
aimoves_remove_index_fast(m1, i--);
|
break;
|
break;
|
}
|
}
|
}
|
}
|
|
|
const char *aiw_to_string(AIWEIGHT w)
|
const char *aiw_to_string(AIWEIGHT w)
|
{
|
{
|
static char buffer[32];
|
static char buffer[32];
|
|
|
switch (w) {
|
switch (w) {
|
case AIW_WIN:
|
case AIW_WIN:
|
return "WIN";
|
return "WIN";
|
case AIW_LOSE:
|
case AIW_LOSE:
|
return "LOSS";
|
return "LOSS";
|
case AIW_NONE:
|
case AIW_NONE:
|
return "NONE";
|
return "NONE";
|
default:
|
default:
|
break;
|
break;
|
}
|
}
|
if (w > 0)
|
if (w > 0)
|
g_snprintf(buffer, sizeof (buffer), "%010d (10^%.2f)", w,
|
g_snprintf(buffer, sizeof (buffer), "%010d (10^%.2f)", w,
|
log10((double)w));
|
log10((double)w));
|
else if (w < 0)
|
else if (w < 0)
|
g_snprintf(buffer, sizeof (buffer), "%010d (-10^%.2f)", w,
|
g_snprintf(buffer, sizeof (buffer), "%010d (-10^%.2f)", w,
|
log10((double)-w));
|
log10((double)-w));
|
return buffer;
|
return buffer;
|
}
|
}
|
|
|
/*
|
/*
|
* Boards
|
* Boards
|
*/
|
*/
|
|
|
Board *board;
|
Board *board;
|
AllocChain *board_root = NULL;
|
AllocChain *board_root = NULL;
|
int board_size, board_stride, move_no, move_last,
|
int board_size, board_stride, move_no, move_last,
|
connect_k = 6, place_p = 2, start_q = 1;
|
connect_k = 6, place_p = 2, start_q = 1;
|
gsize board_mem = 0;
|
gsize board_mem = 0;
|
|
|
Player players[PIECES] = {
|
Player players[PIECES] = {
|
{ PLAYER_HUMAN, SEARCH_NONE, 0 },
|
{ PLAYER_HUMAN, SEARCH_NONE, 0 },
|
{ PLAYER_HUMAN, SEARCH_NONE, 0 },
|
{ PLAYER_HUMAN, SEARCH_NONE, 0 },
|
{ PLAYER_HUMAN, SEARCH_NONE, 0 },
|
{ PLAYER_HUMAN, SEARCH_NONE, 0 },
|
};
|
};
|
|
|
static GPtrArray *history = NULL;
|
static GPtrArray *history = NULL;
|
|
|
static void board_init(Board *b)
|
static void board_init(Board *b)
|
{
|
{
|
memset((char*)b + sizeof (AllocChain), 0, sizeof (Board) -
|
memset((char*)b + sizeof (AllocChain), 0, sizeof (Board) -
|
sizeof (AllocChain));
|
sizeof (AllocChain));
|
}
|
}
|
|
|
AllocChain *board_alloc(AllocChain *ac)
|
AllocChain *board_alloc(AllocChain *ac)
|
{
|
{
|
Board *b = (Board*)ac;
|
Board *b = (Board*)ac;
|
int i;
|
int i;
|
|
|
/* Clear the old board */
|
/* Clear the old board */
|
if (b) {
|
if (b) {
|
for (i = 1; i <= board_size; i++)
|
for (i = 1; i <= board_size; i++)
|
memset(b->data + board_stride * i + 1, 0,
|
memset(b->data + board_stride * i + 1, 0,
|
board_size * sizeof (PIECE));
|
board_size * sizeof (PIECE));
|
board_init(b);
|
board_init(b);
|
return (AllocChain*)b;
|
return (AllocChain*)b;
|
}
|
}
|
|
|
/* New boards are allocated with a 1-tile wide boundary of PIECE_ERROR
|
/* New boards are allocated with a 1-tile wide boundary of PIECE_ERROR
|
around the edges */
|
around the edges */
|
b = (Board*)g_slice_alloc0(board_mem);
|
b = (Board*)g_slice_alloc0(board_mem);
|
memset(b->data, PIECE_ERROR, sizeof (PIECE) * board_stride);
|
memset(b->data, PIECE_ERROR, sizeof (PIECE) * board_stride);
|
for (i = 1; i <= board_size; i++) {
|
for (i = 1; i <= board_size; i++) {
|
b->data[i * board_stride] = PIECE_ERROR;
|
b->data[i * board_stride] = PIECE_ERROR;
|
memset(b->data + board_stride * i + 1, 0,
|
memset(b->data + board_stride * i + 1, 0,
|
board_size * sizeof (PIECE));
|
board_size * sizeof (PIECE));
|
b->data[(i + 1) * board_stride - 1] = PIECE_ERROR;
|
b->data[(i + 1) * board_stride - 1] = PIECE_ERROR;
|
}
|
}
|
memset(b->data + board_stride * (board_stride - 1), PIECE_ERROR,
|
memset(b->data + board_stride * (board_stride - 1), PIECE_ERROR,
|
sizeof (PIECE) * board_stride);
|
sizeof (PIECE) * board_stride);
|
board_init(b);
|
board_init(b);
|
return (AllocChain*)b;
|
return (AllocChain*)b;
|
}
|
}
|
|
|
void board_clean(Board *b)
|
void board_clean(Board *b)
|
{
|
{
|
int y, x;
|
int y, x;
|
|
|
for (y = 0; y < board_size; y++)
|
for (y = 0; y < board_size; y++)
|
for (x = 0; x < board_size; x++)
|
for (x = 0; x < board_size; x++)
|
if (piece_at(b, x, y) >= PIECES)
|
if (piece_at(b, x, y) >= PIECES)
|
place_piece_type(b, x, y, PIECE_NONE);
|
place_piece_type(b, x, y, PIECE_NONE);
|
}
|
}
|
|
|
void set_board_size(unsigned int size)
|
void set_board_size(unsigned int size)
|
{
|
{
|
if (board_size == size)
|
if (board_size == size)
|
return;
|
return;
|
draw_marks(NULL, FALSE);
|
draw_marks(NULL, FALSE);
|
achain_dealloc(&board_root, board_mem);
|
achain_dealloc(&board_root, board_mem);
|
achain_dealloc(&aimoves_root, aimoves_mem);
|
achain_dealloc(&aimoves_root, aimoves_mem);
|
board_size = size;
|
board_size = size;
|
board_stride = size + 2;
|
board_stride = size + 2;
|
board_mem = sizeof (Board) + board_stride * board_stride *
|
board_mem = sizeof (Board) + board_stride * board_stride *
|
sizeof (PIECE);
|
sizeof (PIECE);
|
aimoves_mem = sizeof (AIMoves) + size * size * sizeof (AIMove);
|
aimoves_mem = sizeof (AIMoves) + size * size * sizeof (AIMove);
|
}
|
}
|
|
|
Board *board_at(unsigned int move)
|
Board *board_at(unsigned int move)
|
{
|
{
|
if (move >= history->len)
|
if (move >= history->len)
|
return NULL;
|
return NULL;
|
return (Board*)g_ptr_array_index(history, move);
|
return (Board*)g_ptr_array_index(history, move);
|
}
|
}
|
|
|
int count_pieces(const Board *b, BCOORD x, BCOORD y, PIECE type, int dx, int dy,
|
int count_pieces(const Board *b, BCOORD x, BCOORD y, PIECE type, int dx, int dy,
|
PIECE *out)
|
PIECE *out)
|
{
|
{
|
int i;
|
int i;
|
PIECE p = PIECE_NONE;
|
PIECE p = PIECE_NONE;
|
|
|
if (!dx && !dy)
|
if (!dx && !dy)
|
return piece_at(b, x, y) == type ? 1 : 0;
|
return piece_at(b, x, y) == type ? 1 : 0;
|
for (i = 0; x >= 0 && x < board_size && y >= 0 && y < board_size; i++) {
|
for (i = 0; x >= 0 && x < board_size && y >= 0 && y < board_size; i++) {
|
p = piece_at(b, x, y);
|
p = piece_at(b, x, y);
|
if (p != type)
|
if (p != type)
|
break;
|
break;
|
x += dx;
|
x += dx;
|
y += dy;
|
y += dy;
|
}
|
}
|
if (out)
|
if (out)
|
*out = p;
|
*out = p;
|
return i;
|
return i;
|
}
|
}
|
|
|
gboolean check_win_full(const Board *b, BCOORD x, BCOORD y,
|
gboolean check_win_full(const Board *b, BCOORD x, BCOORD y,
|
BCOORD *x1, BCOORD *y1, BCOORD *x2, BCOORD *y2)
|
BCOORD *x1, BCOORD *y1, BCOORD *x2, BCOORD *y2)
|
{
|
{
|
int i, c1, c2, xs[] = {1, 1, 0, -1}, ys[] = {0, 1, 1, 1};
|
int i, c1, c2, xs[] = {1, 1, 0, -1}, ys[] = {0, 1, 1, 1};
|
PIECE type;
|
PIECE type;
|
|
|
type = piece_at(b, x, y);
|
type = piece_at(b, x, y);
|
if (type != PIECE_BLACK && type != PIECE_WHITE)
|
if (type != PIECE_BLACK && type != PIECE_WHITE)
|
return FALSE;
|
return FALSE;
|
for (i = 0; i < 4; i++) {
|
for (i = 0; i < 4; i++) {
|
c1 = count_pieces(b, x, y, type, xs[i], ys[i], NULL);
|
c1 = count_pieces(b, x, y, type, xs[i], ys[i], NULL);
|
c2 = 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 (c1 + c2 > connect_k) {
|
if (x1)
|
if (x1)
|
*x1 = x + xs[i] * (c1 - 1);
|
*x1 = x + xs[i] * (c1 - 1);
|
if (y1)
|
if (y1)
|
*y1 = y + ys[i] * (c1 - 1);
|
*y1 = y + ys[i] * (c1 - 1);
|
if (x2)
|
if (x2)
|
*x2 = x - xs[i] * (c2 - 1);
|
*x2 = x - xs[i] * (c2 - 1);
|
if (y2)
|
if (y2)
|
*y2 = y - ys[i] * (c2 - 1);
|
*y2 = y - ys[i] * (c2 - 1);
|
return TRUE;
|
return TRUE;
|
}
|
}
|
}
|
}
|
return FALSE;
|
return FALSE;
|
}
|
}
|
|
|
/* Convert a boord coordinate to alpha representation */
|
/* Convert a boord coordinate to alpha representation */
|
const char *bcoord_to_alpha(BCOORD x)
|
const char *bcoord_to_alpha(BCOORD x)
|
{
|
{
|
static char buf[2][32];
|
static char buf[2][32];
|
static int which;
|
static int which;
|
int i, divisor = 26;
|
int i, divisor = 26;
|
|
|
which = !which;
|
which = !which;
|
for (i = 0; i < sizeof (buf[which]) - 1; i++) {
|
for (i = 0; i < sizeof (buf[which]) - 1; i++) {
|
div_t result;
|
div_t result;
|
|
|
result = div(x, divisor);
|
result = div(x, divisor);
|
buf[which][i] = 'a' + result.rem * 26 / divisor;
|
buf[which][i] = 'a' + result.rem * 26 / divisor;
|
if (i)
|
if (i)
|
buf[which][i]--;
|
buf[which][i]--;
|
x -= result.rem;
|
x -= result.rem;
|
if (!x)
|
if (!x)
|
break;
|
break;
|
divisor *= 26;
|
divisor *= 26;
|
}
|
}
|
buf[which][i + 1] = 0;
|
buf[which][i + 1] = 0;
|
return g_strreverse(buf[which]);
|
return g_strreverse(buf[which]);
|
}
|
}
|
|
|
// Get a string representation of board x/y coordinates (d7, h16, etc)
|
// Get a string representation of board x/y coordinates (d7, h16, etc)
|
const char *bcoords_to_string(BCOORD x, BCOORD y)
|
const char *bcoords_to_string(BCOORD x, BCOORD y)
|
{
|
{
|
static char buf[2][32];
|
static char buf[2][32];
|
static int which;
|
static int which;
|
|
|
which = !which;
|
which = !which;
|
g_snprintf(buf[which], sizeof (buf[which]), "%s%d",
|
g_snprintf(buf[which], sizeof (buf[which]), "%s%d",
|
bcoord_to_alpha(x), board_size - y);
|
bcoord_to_alpha(x), board_size - y);
|
return buf[which];
|
return buf[which];
|
}
|
}
|
|
|
/* Convert a string representation to coordinates */
|
/* Convert a string representation to coordinates */
|
void string_to_bcoords(const char *str, BCOORD *x, BCOORD *y)
|
void string_to_bcoords(const char *str, BCOORD *x, BCOORD *y)
|
{
|
{
|
*x = 0;
|
*x = 0;
|
*y = 0;
|
*y = 0;
|
while (*str && *str >= 'a' && *str <= 'z') {
|
while (*str && *str >= 'a' && *str <= 'z') {
|
*x *= 26;
|
*x *= 26;
|
*x += *str - 'a';
|
*x += *str - 'a';
|
str++;
|
str++;
|
}
|
}
|
while (*str && *str >= '0' && *str <= '9') {
|
while (*str && *str >= '0' && *str <= '9') {
|
*y *= 10;
|
*y *= 10;
|
*y += *str - '0';
|
*y += *str - '0';
|
str++;
|
str++;
|
}
|
}
|
if (*y)
|
if (*y)
|
*y = board_size - *y;
|
*y = board_size - *y;
|
}
|
}
|
|
|
const char *piece_to_string(PIECE piece)
|
const char *piece_to_string(PIECE piece)
|
{
|
{
|
switch (piece) {
|
switch (piece) {
|
case PIECE_WHITE:
|
case PIECE_WHITE:
|
return "White";
|
return "White";
|
case PIECE_BLACK:
|
case PIECE_BLACK:
|
return "Black";
|
return "Black";
|
case PIECE_NONE:
|
case PIECE_NONE:
|
return "None";
|
return "None";
|
case PIECE_ERROR:
|
case PIECE_ERROR:
|
return "Error";
|
return "Error";
|
default:
|
default:
|
return "Mark";
|
return "Mark";
|
}
|
}
|
}
|
}
|
|
|
char piece_to_char(PIECE piece)
|
char piece_to_char(PIECE piece)
|
{
|
{
|
switch (piece) {
|
switch (piece) {
|
case PIECE_WHITE:
|
case PIECE_WHITE:
|
return 'W';
|
return 'W';
|
case PIECE_BLACK:
|
case PIECE_BLACK:
|
return 'B';
|
return 'B';
|
case PIECE_NONE:
|
case PIECE_NONE:
|
return '_';
|
return '_';
|
case PIECE_ERROR:
|
case PIECE_ERROR:
|
return 'E';
|
return 'E';
|
default:
|
default:
|
return 'M';
|
return 'M';
|
}
|
}
|
}
|
}
|
|
|
char *search_to_string(SEARCH s)
|
char *search_to_string(SEARCH s)
|
{
|
{
|
switch (s) {
|
switch (s) {
|
case SEARCH_NONE:
|
case SEARCH_NONE:
|
return "No search";
|
return "No search";
|
case SEARCH_DFS:
|
case SEARCH_DFS:
|
return "Depth first search";
|
return "Depth first search";
|
case SEARCHES:
|
case SEARCHES:
|
break;
|
break;
|
}
|
}
|
return "Unknown";
|
return "Unknown";
|
}
|
}
|
|
|
void go_to_move(unsigned int move)
|
void go_to_move(unsigned int move)
|
{
|
{
|
Board *board2;
|
Board *board2;
|
|
|
if (!history)
|
if (!history)
|
history = g_ptr_array_sized_new(32);
|
history = g_ptr_array_sized_new(32);
|
if (move > history->len)
|
if (move > history->len)
|
move = history->len;
|
move = history->len;
|
if (move == history->len) {
|
if (move == history->len) {
|
board2 = board_new();
|
board2 = board_new();
|
if (board)
|
if (board)
|
board_copy(board, board2);
|
board_copy(board, board2);
|
g_ptr_array_add(history, board2);
|
g_ptr_array_add(history, board2);
|
board2->parent = board;
|
board2->parent = board;
|
} else
|
} else
|
board2 = (Board*)g_ptr_array_index(history, move);
|
board2 = (Board*)g_ptr_array_index(history, move);
|
board = board2;
|
board = board2;
|
move_no = move;
|
move_no = move;
|
if (move_no > move_last)
|
if (move_no > move_last)
|
move_last = move_no;
|
move_last = move_no;
|
}
|
}
|
|
|
void clear_history(unsigned int from)
|
void clear_history(unsigned int from)
|
{
|
{
|
int i;
|
int i;
|
|
|
if (!history)
|
if (!history)
|
return;
|
return;
|
if (from >= history->len) {
|
if (from >= history->len) {
|
g_warning("Attempted to clear future history");
|
g_warning("Attempted to clear future history");
|
return;
|
return;
|
}
|
}
|
for (i = from; i < history->len; i++)
|
for (i = from; i < history->len; i++)
|
board_free(g_ptr_array_index(history, i));
|
board_free(g_ptr_array_index(history, i));
|
g_ptr_array_remove_range(history, from, history->len - from);
|
g_ptr_array_remove_range(history, from, history->len - from);
|
move_last = from;
|
move_last = from;
|
}
|
}
|
|
|