#include "othello.h"
STATIC key_type limb_key_stack[BT_MAX_DEPTH];
STATIC int bt_desired_nest;
STATIC int bt_current_nest; /* "stack pointer" (index) for limb_key_stack */
STATIC unsigned char bt_movers_color;
STATIC int human_state;
#define HS_NOT_HUMANS_TURN 0
#define HS_WAITING_FOR_HUMAN 1
#define HS_HUMAN_MOVED 2
STATIC humans_move_limb_key;
int
build_tree(int depth_to_build, unsigned char movers_color)
{
struct limb_struct far *limb_ptr;
int temp;
if (movers_color == THEM_PIECE) {
human_state = HS_WAITING_FOR_HUMAN;
depth_to_build++; /* We'll delete 1 level after the human moves; so we
build an extra level now. */
}
else {
human_state = HS_NOT_HUMANS_TURN;
}
limb_ptr = db_retrieve_limb(curnt_top_limb);
if (limb_ptr->move & BOARD_MASK) {
/* The root is a board. There is a lower-level function
(after_opponents_move()) which assumes that the root is not a board,
so we have to build the first level of the tree before continuing.
*/
build_children_of_a_board(curnt_top_limb,
limb_ptr->bc.board_key,
movers_color);
tree_depth = 1;
}
for (bt_desired_nest = tree_depth - 1;
bt_desired_nest <= depth_to_build - 2;
bt_desired_nest++)
{
limb_key_stack[0] = limb_ptr->bc.child_key;
bt_current_nest = 0;
bt_movers_color = movers_color ^ (US_PIECE | THEM_PIECE);
/* Try to build a level. If the database fills up but we're waiting for
input from the human, keep trying to build until we get his input.
*/
do {
temp = build_a_level();
} while (temp != BT_COMPLETED && human_state == HS_WAITING_FOR_HUMAN);
if (temp == BT_COMPLETED) {
tree_depth = bt_desired_nest + 2;
}
else {
break;
}
}
while (human_state == HS_WAITING_FOR_HUMAN) {
move_type humans_move;
if ((humans_move = check_for_input()) != HASNT_MOVED) {
human_state = HS_HUMAN_MOVED;
after_opponents_move(humans_move);
}
}
if (movers_color == THEM_PIECE) {
free_limb(curnt_top_limb);
curnt_top_limb = humans_move_limb_key;
tree_depth--; /* Since we deleted the old root, the tree is shallower */
}
return (tree_depth);
}
STATIC int
build_a_level()
{
limb_type far *limb_ptr;
move_type humans_move;
while (1) {
if (human_state == HS_WAITING_FOR_HUMAN &&
(humans_move = check_for_input()) != HASNT_MOVED)
{
human_state = HS_HUMAN_MOVED;
if (after_opponents_move(humans_move)) {
return (BT_COMPLETED);
}
}
if (db_almost_full()) {
return (BT_DBFULL);
}
limb_ptr = db_retrieve_limb(limb_key_stack[bt_current_nest]);
if (limb_ptr->move & BOARD_MASK) { /* it's a board */
build_children_of_a_board(limb_key_stack[bt_current_nest],
limb_ptr->bc.board_key,
bt_movers_color);
}
if (bt_current_nest != bt_desired_nest) {
/* Follow child key to nest down one level */
limb_key_stack[bt_current_nest + 1] =
db_retrieve_limb(limb_key_stack[bt_current_nest])->bc.child_key;
++bt_current_nest;
bt_movers_color ^= (US_PIECE | THEM_PIECE);
}
else {
while (bt_current_nest >= 0) { /* also contains a 'break' */
if (
(limb_key_stack[bt_current_nest] =
db_retrieve_limb(limb_key_stack[bt_current_nest])->sibling_key
)
== NO_KEY
)
{
--bt_current_nest; /* pop stack */
bt_movers_color ^= (US_PIECE | THEM_PIECE);
}
else {
break;
}
}
if (bt_current_nest < 0) {
return (BT_COMPLETED);
}
}
}
}
STATIC void
build_children_of_a_board(
key_type parent_limb_key,
key_type parent_board_key,
unsigned char movers_color)
{
struct board_struct parent_board;
struct board_struct child_board;
int aff_list[MAX_AFFECTED_PIECES];
int aff_ct;
int look_at;
move_type db_move;
if (db_retrieve_board(parent_board_key, &parent_board)) {
printf("\nFATAL PROGRAM BUG:\n\
couldn't retrieve parent board in build_children_of_a_board\n");
exit(5);
}
look_at = 0;
while (aff_ct = find_move(&parent_board, look_at, movers_color, aff_list)) {
child_board = parent_board;
update_protection_for_board(&child_board, aff_list, aff_ct,
movers_color);
db_move = 0;
SET_ROW_COL(db_move, aff_list[0] / 10 - 1, aff_list[0] % 10 - 1);
if (db_add_child(parent_limb_key, db_move, &child_board,
bd_eval(&child_board, US_PIECE) ) == -1)
{
printf("OTHELLO FATAL: no room to add board to database\n");
exit(5);
}
look_at = aff_list[0] + 1; /* resume search for moves at next cell */
}
if (look_at == 0) {
if (db_add_child(parent_limb_key, NO_MOVE_MASK, &parent_board,
bd_eval(&parent_board, US_PIECE) ) == -1)
{
printf("OTHELLO FATAL: no room to add board to database\n");
exit(5);
}
}
}
STATIC int
after_opponents_move(move_type humans_move)
{
key_type key;
struct limb_struct far *limb_ptr;
int already_built;
int ret_val;
already_built = 1;
for (key = db_retrieve_limb(curnt_top_limb)->bc.child_key;
key != NO_KEY;
key = limb_ptr->sibling_key)
{
limb_ptr = db_retrieve_limb(key);
if (key == limb_key_stack[0]) {
already_built = 0;
}
if ((limb_ptr->move & ~BOARD_MASK) == humans_move) {
ret_val = already_built;
humans_move_limb_key = key;
if (key != limb_key_stack[0]) {
bt_current_nest = 0;
limb_key_stack[0] = key;
bt_movers_color = US_PIECE;
}
}
else {
db_delete_subtree(curnt_top_limb, key);
}
}
return (ret_val);
}
void
update_tree_after_our_move(
key_type our_move)
{
register key_type ch;
limb_type far *l;
ch = db_retrieve_limb(curnt_top_limb)->bc.child_key;
for ( ; ch != NO_KEY; ch = l->sibling_key) {
l = db_retrieve_limb(ch);
if (ch != our_move) {
db_delete_subtree(curnt_top_limb, ch);
}
}
free_limb(curnt_top_limb);
curnt_top_limb = our_move;
tree_depth--;
}