/* '='='=' '@' '='='='='='='='='=' '@' '='='='='='='='='=' '@' '='='='| */ /* ='='=' '@'@' '='='='='='='='=' '@'@' '='='='='='='='=' '@'@' '='='=| */ /* '='=' '@':'@' '='='='='='='=' '@':'@' '='='='='='='=' '@':'@' '='='| */ /* ='=' '@':':'@' '='='='='='=' '@':':'@' '='='='='='=' '@':':'@' '='=| */ /* '=' '@':':':'@' '='='='='=' '@':':':'@' '='='='='=' '@':':':'@' '='| */ /* =' '@':':':':'@' '='='='=' '@':':':':'@' '='='='=' '@':':':':'@' '=| */ /* ' '@':' '@' '| */ /* '@' 3rd Year Project - ROY SCHESTOWITZ - 2002 @' | */ /* '@ @'| */ /* @':':':':':':':':'@' ' '@':':':':':':':':'@' ' '@':':':':':':':':'@| */ /* ':':':':':':':':':'@' '@':':':':':':':':':'@' '@':':':':':':':':':'| */ /* :':':':':':':':':':'@'@':':':':':':':':':':'@'@':':':':':':':':':':| */ /* ':':':': : :':':':':'@':':':':': : :':':':':'@':':':':': : :':':':'| */ /* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- */ /* Name: computation.c */ /* Version: 0.6.6 */ /* Date: 12/2/2003 */ /* */ /* Main procedures to compute a move in the game */ /* */ /* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- */ #include "computation.h" #include "misc.h" #include "hashing.c" /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* board_map make_nth_best_move - makes the Nth best move for color given N */ /* inputs: the board that is dealt with */ /* the color for which the move is carried out */ /* the priority n where 1 is best choice */ /* returns: the board after the move was carried out */ /* */ /* */ board_map make_nth_best_move ( board_map inputboard, int color, int priority ) { int i, j, k; move_score move_database[MOVES_UPPER_BOUND]; /* upper bound for moves available : safe */ int wanted_i, wanted_j; for ( k = 0; k < MOVES_UPPER_BOUND; k++ ) /* k for readability; Variable reuse unwanted */ { move_database[k].score = SCORE_LOWER_BOUND; move_database[k].i = -1; /* initialise to invalid moves */ move_database[k].j = -1; } for ( i = 1; i < 9; i++ ) { for ( j = 1; j < 9; j++ ) { if ( reducible ( i, j, color, inputboard ) ) /* if reduction is possible */ { board_map temp_board; /* create a draft board */ int current_score; int database_index; database_index = MOVES_UPPER_BOUND; /* set up size of database */ temp_board = inputboard; // copy of current board temp_board.slot[i][j] = color; /* put stone */ temp_board = reduce ( i, j, temp_board ); /* reduce */ current_score = evaluate ( color, temp_board ); /* and evaluate it */ while ( ( database_index > 1 ) && ( current_score > move_database[database_index - 1].score ) ) database_index--; /* step to right priority in databse */ move_database[database_index].score = current_score; move_database[database_index].i = i; move_database[database_index].j = j; /* and record it at that position */ /* storing the score and position in the right position indexed by priority */ /* note that 0 will not be dealt with dur to priority 0 undefined */ } } } wanted_i = move_database[priority].i; /* record the i corresponding to priority */ wanted_j = move_database[priority].j; /* record the j corresponding to priority */ inputboard.slot[wanted_i][wanted_j] = color; /* and carry out the move now */ inputboard = reduce ( wanted_i, wanted_j, inputboard ); return inputboard; } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* get_mobility_of_color - gets the number of moves available */ /* inputs: the board that is dealt with */ /* the color for which the number is calculated */ /* returns: the number of moves available */ /* */ /* */ int get_mobility_of_color ( board_map inputboard, int color ) { int i, j; int moves_available; /* records mobility value */ moves_available = 0; /* initialise this */ for ( i = 1; i < 9; i++ ) for ( j = 1; j < 9; j++ ) if ( reducible ( i, j, color, board ) ) moves_available++; /* increment if reducible */ return moves_available; } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* evaluate_straight_lines_complete - calculate the value of the */ /* complete stright lines on the given board */ /* inputs: the board that is dealt with */ /* the color for which the value is calculated */ /* returns: the value of the lines */ /* */ /* */ int evaluate_straight_lines_complete ( board_map input_board, int color ) { int horizontal; /* horizontal coordinate */ int vertical; /* and a vertical one */ int value_acc; /* to return a total value */ value_acc = 0; /* initilaise score accumulator */ /* horizontal scan begins here */ horizontal = 1; while ( horizontal < 9 ) /* while end of board not reached */ { vertical = 1; /* start at row 1 */ while ( ( input_board.slot[horizontal][vertical] == color ) && ( vertical < 9 ) ) /* step downwards */ vertical++; if ( vertical == 9 ) /* if all 8 stones were of colour color */ switch ( horizontal ) { case 1: /* these are the lines adjacent to borders */ case 8: /* 1 and 8 are equivalent */ value_acc += LINE_STRAIGHT_EDGE; break; case 2: case 7: value_acc += LINE_STRAIGHT_NEAR_EDGE; break; case 3: case 6: value_acc += LINE_STRAIGHT_NEAR_MIDDLE; break; case 4: /* lines going through the middle */ case 5: value_acc += LINE_STRAIGHT_MIDDLE; break; default: /* for safety and debugging only */ if ( debugging ) printf ( "Error in switch statement in evaluate_straight_lines_complete()" ); break; } horizontal++; /* step to next horizontal line */ } /* vertical scan begins here */ vertical = 1; /* see above for annotation */ while ( vertical < 9 ) { horizontal = 1; while ( ( input_board.slot[horizontal][vertical] == color ) && ( horizontal < 9 ) ) horizontal++; if ( horizontal == 9 ) /* if all 8 stones were of colour color */ switch ( vertical ) { case 1: case 8: value_acc += LINE_STRAIGHT_EDGE; break; case 2: case 7: value_acc += LINE_STRAIGHT_NEAR_EDGE; break; case 3: case 6: value_acc += LINE_STRAIGHT_NEAR_MIDDLE; break; case 4: case 5: value_acc += LINE_STRAIGHT_MIDDLE; break; default: if ( debugging ) printf ( "Error in switch statement in evaluate_straight_lines_complete()" ); break; } vertical++; } return value_acc; /* return the value of the accumulator */ } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* evaluate_straight_lines_complete - calculate the value of the */ /* complete diagonal lines on the given board */ /* inputs: the board that is dealt with */ /* the color for which the value is calculated */ /* returns: the value of the lines */ /* */ /* */ int evaluate_diagonal_lines_complete ( board_map input_board, int color ) { int horizontal; /* see above for annotation */ int vertical; int value_acc; value_acc = 0; horizontal = 1; while ( horizontal < 6 ) /* 1 to 5 from left to right */ { int temp; vertical = 1; temp = horizontal; while ( input_board.slot[temp][vertical] == color ) { temp++; vertical++; } if ( ( 8 - horizontal ) == vertical ) /* if found a valid diagonal sequence */ switch ( horizontal ) { case 1: value_acc += LINE_DIAGONAL_MIDDLE; break; case 2: value_acc += LINE_DIAGONAL_NEAR_MIDDLE; break; case 3: value_acc += LINE_DIAGONAL_BETWEEN_MIDDLE_AND_CORNER; break; case 4: value_acc += LINE_DIAGONAL_NEAR_CORNER; break; case 5: value_acc += LINE_DIAGONAL_CORNER; break; default: if ( debugging ) printf ( "Error in switch statement in evaluate_diagonal_lines_complete()" ); break; } horizontal++; } horizontal = 8; /* see above for more annotation */ while ( horizontal > 3 ) /* 8 to 4 from right to left */ { int temp; vertical = 1; temp = horizontal; while ( input_board.slot[temp][vertical] == color ) { temp--; vertical++; } if ( horizontal == ( vertical - 1 ) ) /* if found a valid diagonal sequence */ switch ( horizontal ) { case 8: value_acc += LINE_DIAGONAL_MIDDLE; break; case 7: value_acc += LINE_DIAGONAL_NEAR_MIDDLE; break; case 6: value_acc += LINE_DIAGONAL_BETWEEN_MIDDLE_AND_CORNER; break; case 5: value_acc += LINE_DIAGONAL_NEAR_CORNER; break; case 4: value_acc += LINE_DIAGONAL_CORNER; break; default: if ( debugging ) printf ( "Error in switch statement in evaluate_diagonal_lines_complete()" ); break; } horizontal--; } horizontal = 2; /* see above for more annotation */ while ( horizontal < 6 ) /* 1 to 5 from left to right */ { int temp; vertical = 8; temp = horizontal; while ( input_board.slot[temp][vertical] == color ) { temp++; vertical--; } if ( horizontal == ( vertical - 1 ) ) /* if found a valid diagonal sequence */ switch ( horizontal ) { case 2: value_acc += LINE_DIAGONAL_NEAR_MIDDLE; break; case 3: value_acc += LINE_DIAGONAL_BETWEEN_MIDDLE_AND_CORNER; break; case 4: value_acc += LINE_DIAGONAL_NEAR_CORNER; break; case 5: value_acc += LINE_DIAGONAL_CORNER; break; default: if ( debugging ) printf ( "Error in switch statement in evaluate_diagonal_lines_complete()" ); break; } horizontal++; } horizontal = 7; /* see above for more annotation */ while ( horizontal > 3 ) /* 8 to 4 from right to left */ { int temp; vertical = 8; temp = horizontal; while ( input_board.slot[temp][vertical] == color ) { temp--; vertical--; } if ( horizontal == ( 8 - vertical ) ) /* if found a valid diagonal sequence */ switch ( horizontal ) { case 7: value_acc += LINE_DIAGONAL_NEAR_MIDDLE; break; case 6: value_acc += LINE_DIAGONAL_BETWEEN_MIDDLE_AND_CORNER; break; case 5: value_acc += LINE_DIAGONAL_NEAR_CORNER; break; case 4: value_acc += LINE_DIAGONAL_CORNER; break; default: if ( debugging ) printf ( "Error in switch statement in evaluate_diagonal_lines_complete()" ); break; } horizontal--; } return value_acc; /* return the value of the accumulator */ } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* evaluate_straight_lines_complete - calculate the value of the */ /* incomplete stright lines on the given board */ /* inputs: the board that is dealt with */ /* the color for which the value is calculated */ /* returns: the value of the lines */ /* */ /* */ int evaluate_straight_lines_incomplete ( board_map input_board, int color ) { int horizontal; int vertical; int value_acc; value_acc = 0; /* horizontal scan begins here */ horizontal = 1; while ( horizontal < 9 ) { vertical = 1; while ( ( input_board.slot[horizontal][vertical] == color ) && ( vertical < 9 ) ) vertical++; if ( vertical == 1 ) /* if dropped out at beginning... */ { vertical = 2; /* set to next stone */ while ( ( input_board.slot[horizontal][vertical] == color ) && ( vertical < 9 ) ) vertical++; /* progress until reaching last stone of colour color */ vertical--; /* little offset for the following condition and switch statement */ } if ( vertical == 8 ) /* if 7 stones were of colour color */ switch ( horizontal ) { case 1: case 8: value_acc += INCOMPLETE_LINE_STRAIGHT_EDGE; break; case 2: case 7: value_acc += INCOMPLETE_LINE_STRAIGHT_NEAR_EDGE; break; case 3: case 6: value_acc += INCOMPLETE_LINE_STRAIGHT_NEAR_MIDDLE; break; case 4: case 5: value_acc += INCOMPLETE_LINE_STRAIGHT_MIDDLE; break; default: if ( debugging ) printf ( "Error in switch statement in evaluate_straight_lines_incomplete()" ); break; } horizontal++; } /* vertical scan begins here */ vertical = 1; while ( vertical < 9 ) { horizontal = 1; while ( ( input_board.slot[horizontal][vertical] == color ) && ( horizontal < 9 ) ) horizontal++; if ( horizontal == 1 ) /* if dropped out at beginning... */ { horizontal = 2; /* set to next stone */ while ( ( input_board.slot[horizontal][vertical] == color ) && ( horizontal < 9 ) ) horizontal++; /* progress until reaching last stone of colour color */ horizontal--; /* little offset for the following condition and switch statement */ } if ( horizontal == 8 ) /* if 7 stones were of colour color */ switch ( vertical ) { case 1: case 8: value_acc += INCOMPLETE_LINE_STRAIGHT_EDGE; break; case 2: case 7: value_acc += INCOMPLETE_LINE_STRAIGHT_NEAR_EDGE; break; case 3: case 6: value_acc += INCOMPLETE_LINE_STRAIGHT_NEAR_MIDDLE; break; case 4: case 5: value_acc += INCOMPLETE_LINE_STRAIGHT_MIDDLE; break; default: if ( debugging ) printf ( "Error in switch statement in evaluate_straight_lines_incomplete()" ); break; } vertical++; } return value_acc; /* return the value of the accumulator */ } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* evaluate_diagonal_lines_complete - calculate the value of the */ /* incomplete diagonal lines on the given board */ /* inputs: the board that is dealt with */ /* the color for which the value is calculated */ /* returns: the value of the lines */ /* */ /* */ int evaluate_diagonal_lines_incomplete ( board_map input_board, int color ) { int horizontal; int vertical; int value_acc; value_acc = 0; horizontal = 1; while ( horizontal < 6 ) /* 1 to 5 from left to right */ { int temp; vertical = 1; temp = horizontal; while ( input_board.slot[temp][vertical] == color ) { temp++; vertical++; } if ( vertical == 1 ) /* if dropped out at beginning... */ { temp++; vertical = 2; /* set to next stone */ while ( input_board.slot[temp][vertical] == color ) { temp++; vertical++; } vertical--; /* little offset for the following condition and switch statement */ } if ( ( 9 - horizontal ) == vertical ) /* if found a valid diagonal sequence */ switch ( horizontal ) { case 1: value_acc += LINE_DIAGONAL_MIDDLE; break; case 2: value_acc += LINE_DIAGONAL_NEAR_MIDDLE; break; case 3: value_acc += LINE_DIAGONAL_BETWEEN_MIDDLE_AND_CORNER; break; case 4: value_acc += LINE_DIAGONAL_NEAR_CORNER; break; case 5: value_acc += LINE_DIAGONAL_CORNER; break; default: if ( debugging ) printf ( "Error in switch statement in evaluate_diagonal_lines_complete()" ); break; } horizontal++; } horizontal = 8; while ( horizontal > 3 ) /* 8 to 4 from right to left */ { int temp; vertical = 1; temp = horizontal; while ( input_board.slot[temp][vertical] == color ) { temp--; vertical++; } if ( vertical == 1 ) /* if dropped out at beginning... */ { temp++; vertical = 2; /* set to next stone */ while ( input_board.slot[temp][vertical] == color ) { temp++; vertical++; } vertical--; /* little offset for the following condition and switch statement */ } if ( horizontal == vertical ) /* if found a valid diagonal sequence */ switch ( horizontal ) { case 8: value_acc += LINE_DIAGONAL_MIDDLE; break; case 7: value_acc += LINE_DIAGONAL_NEAR_MIDDLE; break; case 6: value_acc += LINE_DIAGONAL_BETWEEN_MIDDLE_AND_CORNER; break; case 5: value_acc += LINE_DIAGONAL_NEAR_CORNER; break; case 4: value_acc += LINE_DIAGONAL_CORNER; break; default: if ( debugging ) printf ( "Error in switch statement in evaluate_diagonal_lines_complete()" ); break; } horizontal--; } horizontal = 2; while ( horizontal < 6 ) /* 1 to 5 from left to right */ { int temp; vertical = 8; temp = horizontal; while ( input_board.slot[temp][vertical] == color ) { temp++; vertical--; } if ( vertical == 8 ) /* if dropped out at beginning... */ { temp--; vertical = 7; /* set to next stone */ while ( input_board.slot[temp][vertical] == color ) { temp--; vertical--; } vertical++; /* little offset for the following condition and switch statement */ } if ( horizontal == vertical ) /* if found a valid diagonal sequence */ switch ( horizontal ) { case 2: value_acc += LINE_DIAGONAL_NEAR_MIDDLE; break; case 3: value_acc += LINE_DIAGONAL_BETWEEN_MIDDLE_AND_CORNER; break; case 4: value_acc += LINE_DIAGONAL_NEAR_CORNER; break; case 5: value_acc += LINE_DIAGONAL_CORNER; break; default: if ( debugging ) printf ( "Error in switch statement in evaluate_diagonal_lines_complete()" ); break; } horizontal++; } horizontal = 7; while ( horizontal > 3 ) /* 8 to 4 from right to left */ { int temp; vertical = 8; temp = horizontal; while ( input_board.slot[temp][vertical] == color ) { temp--; vertical--; } if ( vertical == 8 ) /* if dropped out at beginning... */ { temp--; vertical = 7; /* set to next stone */ while ( input_board.slot[temp][vertical] == color ) { temp--; vertical--; } vertical++; /* little offset for the following condition and switch statement */ } if ( horizontal == ( 9 - vertical ) ) /* if found a valid diagonal sequence */ switch ( horizontal ) { case 7: value_acc += LINE_DIAGONAL_NEAR_MIDDLE; break; case 6: value_acc += LINE_DIAGONAL_BETWEEN_MIDDLE_AND_CORNER; break; case 5: value_acc += LINE_DIAGONAL_NEAR_CORNER; break; case 4: value_acc += LINE_DIAGONAL_CORNER; break; default: if ( debugging ) printf ( "Error in switch statement in evaluate_diagonal_lines_complete()" ); break; } horizontal--; } return value_acc; /* return the value of the accumulator */ } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* evaluate_lines - calculates the value of the line occupancy for color */ /* gap in a given board */ /* inputs: the board that is dealt with */ /* the color for which the value is calculated */ /* returns: the value required */ /* */ /* */ int evaluate_lines ( board_map input_board, int color ) { int value_acc; /* the score accumulator */ value_acc = 0; /* initialise that */ if ( STRAIGHT_COMPLETE_LINES_ACTIVE ) /* if this is defined to be included in computation */ value_acc += LINING_COEFFICIENT_STRAIGHT_COMPLETE * evaluate_straight_lines_complete ( input_board, color ); if ( DIAGONAL_COMPLETE_LINES_ACTIVE ) /* if this is defined to be included in computation */ value_acc += LINING_COEFFICIENT_DIAGONAL_COMPLETE * evaluate_diagonal_lines_complete ( input_board, color ); if ( STRAIGHT_INCOMPLETE_LINES_ACTIVE ) /* if this is defined to be included in computation */ value_acc += LINING_COEFFICIENT_STRAIGHT_INCOMPLETE * evaluate_straight_lines_incomplete ( input_board, color ); if ( DIAGONAL_INCOMPLETE_LINES_ACTIVE ) /* if this is defined to be included in computation */ value_acc += LINING_COEFFICIENT_DIAGONAL_INCOMPLETE * evaluate_diagonal_lines_incomplete ( input_board, color ); return value_acc; } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* calculate_mobility_difference_of_board - calculates the mobility value */ /* gap in a given board */ /* inputs: the board that is dealt with */ /* the color for which the advantage is calculated */ /* returns: the mobility gap in board (positive if color's mobility is */ /* higher) */ /* */ /* */ int calculate_mobility_difference_of_board ( board_map inputboard, int color ) { int i, j; int red_mobility = 0; int black_mobility = 0; for ( i = 1; i < 9; i++ ) for ( j = 1; j < 9; j++ ) { if ( reducible ( i, j, RED, inputboard ) ) red_mobility++; /* set up red mobility in input board */ if ( reducible ( i, j, BLACK, inputboard ) ) black_mobility++; /* and same for black */ } if ( color == RED ) return ( red_mobility - black_mobility ); // positive for advantage if ( color == BLACK ) return ( black_mobility - red_mobility ); // positive for advantage if ( VERBOSE ) printf ( "Reached an illegal state in calculate_mobility_difference_of_board()\n" ); return 0; } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* calculate_score_difference_of_board - calculates the score gap in a board */ /* inputs: the board that is dealt with */ /* the color for which the advantage is calculated */ /* returns: the score gap in board (positive if color's score is higher) */ /* */ /* */ int calculate_score_difference_of_board ( board_map inputboard, int color ) { int i, j; int redscore = 0; int blackscore = 0; for ( i = 1; i < 9; i++ ) for ( j = 1; j < 9; j++ ) { if ( inputboard.slot[i][j] == BLACK ) /* set up black score in input board */ blackscore++; if ( inputboard.slot[i][j] == RED ) redscore++; /* and same for red */ } if ( color == RED ) return ( redscore - blackscore ); // positive for advantage if ( color == BLACK ) return ( blackscore - redscore ); // positive for advantage if ( VERBOSE ) printf ( "Reached an illegal state in calculate_score_difference_of_board()\n" ); return 0; } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* find_value_of_position - finds the value of position i,j standing for A-H */ /* and 1-8. */ /* inputs - the board coordinates ranging from 1-8 */ /* the current color for randomisation reasons */ /* returns - the value of the position inquired */ /* */ /* */ /* note conditional ordering for efficiency */ int find_value_of_position ( int i, int j, int color ) { float evaluation_randomisation_factor = 1; /* the coefficient of evaluation value */ if ( non_determinism == TRUE ) /* if random move is requested */ { int randomisation_factor_source; int current_difficulty = BEGINNER; if ( color == BLACK ) current_difficulty = difficulty; if ( color == RED ) /* when (gathering_statistics==TRUE) */ current_difficulty = stat_mode_difficulty; /* get the difficulty of current player */ switch ( current_difficulty ) /* this is handled as integer here for readability */ { /* could be 'else if' sequence with strcmp() */ case 0: randomisation_factor_source = BEGINNER_RANDOMISATION_KEY; /* currently unreachable */ break; case 1: randomisation_factor_source = NOVICE_RANDOMISATION_KEY; /* set the randomisation key according to the difficulty */ break; case 2: randomisation_factor_source = EXPERT_RANDOMISATION_KEY; break; case 3: randomisation_factor_source = PRE_MASTER_RANDOMISATION_KEY; break; case 4: randomisation_factor_source = MASTER_RANDOMISATION_KEY; break; default: if ( VERBOSE ) printf ( "Difficulty state is invalid.\n" ); randomisation_factor_source = NOVICE_RANDOMISATION_KEY; break; } evaluation_randomisation_factor = ( ( float ) random_number ( randomisation_factor_source ) / 100.0 ) + 1.0; } /* confer computation.c for visual record of the following */ if ( ( ( ( i == 1 ) || ( i == 8 ) ) && ( ( j == 4 ) || ( j == 5 ) ) ) || ( ( ( j == 1 ) || ( j == 8 ) ) && ( ( i == 4 ) || ( i == 5 ) ) ) ) return SIDE_MIDDLE_POS * evaluation_randomisation_factor; if ( ( ( ( i == 1 ) || ( i == 8 ) ) && ( ( j == 3 ) || ( j == 6 ) ) ) || ( ( ( j == 1 ) || ( j == 8 ) ) && ( ( i == 3 ) || ( i == 6 ) ) ) ) return SIDE_FAR_POS * evaluation_randomisation_factor; if ( ( ( ( i == 2 ) || ( i == 7 ) ) && ( ( j == 4 ) || ( j == 5 ) ) ) || ( ( ( j == 2 ) || ( j == 7 ) ) && ( ( i == 4 ) || ( i == 5 ) ) ) ) return NEAR_SIDES_MIDDLE_POS * evaluation_randomisation_factor; if ( ( ( ( i == 2 ) || ( i == 7 ) ) && ( ( j == 3 ) || ( j == 6 ) ) ) || ( ( ( j == 2 ) || ( j == 7 ) ) && ( ( i == 3 ) || ( i == 6 ) ) ) ) return NEAR_SIDES_FAR_POS * evaluation_randomisation_factor; if ( ( ( ( i == 2 ) || ( i == 7 ) ) && ( ( j == 1 ) || ( j == 8 ) ) ) || ( ( ( j == 2 ) || ( j == 7 ) ) && ( ( i == 1 ) || ( i == 8 ) ) ) ) return SIDES_NEAR_CORNER_POS * evaluation_randomisation_factor; if ( ( ( ( i == 4 ) || ( i == 5 ) ) && ( ( j == 3 ) || ( j == 6 ) ) ) || ( ( ( j == 4 ) || ( j == 5 ) ) && ( ( i == 3 ) || ( i == 6 ) ) ) ) return MIDDLE_8_POS * evaluation_randomisation_factor; if ( ( ( ( i == 2 ) || ( i == 7 ) ) && ( ( j == 2 ) || ( j == 7 ) ) ) ) return DIAGONAL_NEAR_CORNER_POS * evaluation_randomisation_factor; if ( ( ( ( i == 3 ) || ( i == 6 ) ) && ( ( j == 3 ) || ( j == 6 ) ) ) ) return MIDDLE_DIAGONAL_4_POS * evaluation_randomisation_factor; if ( ( ( ( i == 4 ) || ( i == 5 ) ) && ( ( j == 4 ) || ( j == 5 ) ) ) ) return MIDDLE_4_POS * evaluation_randomisation_factor; if ( ( ( ( i == 1 ) || ( i == 8 ) ) && ( ( j == 1 ) || ( j == 8 ) ) ) ) return CORNER_POS * evaluation_randomisation_factor; /* if not case was caught */ if ( debugging ) printf ( "Inexsistent board position evaluated. the coordinates are %d, %d\n", i, j ); exit ( 1 ); } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* evaluate - evaluates the current position of the board from the point of */ /* view of color and assumes that color is currently up */ /* inputs - the color for which the evaluation is carried out and the state */ /* of the board */ /* output - the evaluation value */ /* */ /* */ int evaluate ( int color, board_map input_board ) { int player_color = RED; /* the color of the side */ /* that requests evaluation */ int opponent_color; /* the color of the opponent */ int evaluation_acc = 0; /* evaluation accumulator */ int i, j; /* to index the input board */ if ( color == BLACK ) /* initialise the above values */ { player_color = BLACK; opponent_color = RED; } if ( color == RED ) { opponent_color = BLACK; player_color = RED; } if ( EVALUATE_POSITION_ACTIVE && enable_position_eval ) { for ( i = 1; i < 9; i++ ) /* excluding the empty borders */ for ( j = 1; j < 9; j++ ) /* excluding the empty borders */ { switch ( input_board.slot[i][j] ) /* inspect color in position i,j */ { case NONE: break; case RED: if ( player_color == RED ) evaluation_acc += POSITION_VALUE_COEFFICIENT * find_value_of_position ( i, j, color ); /* inspect position value */ if ( player_color == BLACK ) evaluation_acc -= POSITION_VALUE_COEFFICIENT * find_value_of_position ( i, j, color ); /* add value if player's colour, subtract if opponent's */ break; case BLACK: if ( player_color == BLACK ) evaluation_acc += POSITION_VALUE_COEFFICIENT * find_value_of_position ( i, j, color ); /* inspect position value */ if ( player_color == RED ) evaluation_acc -= POSITION_VALUE_COEFFICIENT * find_value_of_position ( i, j, color ); /* add value if player's colour, subtract if opponent's */ break; } } } if ( EVALUATE_MOBILITY_ACTIVE && enable_mobility_eval ) /* if both definition and user's choice require that */ evaluation_acc += MOBILITY_COEFFICIENT * calculate_mobility_difference_of_board ( input_board, color ); if ( EVALUATE_SCORE_ACTIVE && enable_score_eval ) /* if both definition and user's choice require that */ evaluation_acc += SCORE_COEFFICIENT * ( -0.5 + ( ( float ) movecount / 64 ) ) * /* more of an advantage towards end of game */ calculate_score_difference_of_board ( input_board, color ); if ( EVALUATE_LINES_ACTIVE && enable_line_eval ) /* if both definition and user's choice require that */ evaluation_acc += LINE_STATE_COEFFICIENT * evaluate_lines ( input_board, color ); /* check for protected lines (protected diagonally or by sides */ return evaluation_acc; /* return the total value calculated */ } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* compute_move_for_color - computes a complex move for a given colour */ /* inputs: the colour of player whose turn it is, input board */ /* returns: the board with the new stone put */ /* */ board_map compute_move_for_color ( board_map inputboard, int color ) { int i, j; int best_i = 1; int best_j = 1; int best_score_so_far = SCORE_LOWER_BOUND; // cannot currently be lower for ( i = 1; i < 9; i++ ) { for ( j = 1; j < 9; j++ ) { if ( reducible ( i, j, color, inputboard ) ) /* if legal move */ { board_map temp_board; int current_score; temp_board = inputboard; // copy of current board temp_board.slot[i][j] = color; /* put stone */ temp_board = reduce ( i, j, temp_board ); if ( ( current_score = evaluate ( color, temp_board ) ) > best_score_so_far ) /* if this is the best score found so far */ { best_score_so_far = current_score; /* record it */ best_i = i; best_j = j; } } } } inputboard.slot[best_i][best_j] = color; /* final placement */ inputboard = reduce ( best_i, best_j, inputboard ); /* and reduction */ return inputboard; /* return the new board */ } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* random_number - returns a random integer between 0 and N */ /* */ /* */ int random_number ( int N ) { return ( ( ( int ) random ( ) ) % ( N + 1 ) ); } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* zero_one_random - returns 0 or 1 randomly */ /* */ /* */ int zero_one_random ( void ) { return random_number ( 1 ); } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* load_opening_library_file - load an opening library of Othello Master */ /* from a file given a filename */ /* On entry: filename is a pointer to the characters of the file to open */ /* returns: true if save operation was successful, false otherwise */ /* */ /* */ int load_opening_library_file ( char *filename ) { FILE *loaded_opening_library_file; /* the loaded file pointer */ int data[OPENING_LIB_LENGTH]; /* data buffer */ unsigned int length_read; /* length of file read */ int i, /* loop index */ x, /* horizontal coordinate of the board */ y; /* vertical coordinate of the board */ char boardstate[66]; /* the 128 bits necessary to store board state */ loaded_opening_library_file = fopen ( filename, "r" ); /* open the file for reading */ if ( loaded_opening_library_file == NULL ) /* if unable to open it */ { if ( VERBOSE ) printf ( "Could not open the file %s.\n", filename ); return FALSE; } length_read = fread ( data, 4, OPENING_LIB_LENGTH, loaded_opening_library_file ); /* read the data */ /* read data from file, a word per slot and save length onto length_read */ if ( VERBOSE ) printf ( "length of opening library %s: %d bytes\n", filename, length_read ); for ( i = 0; i < OPENING_LIB_LENGTH / 68; i++ ) /* for each entry */ { int j; /* internal index */ for ( j = 0; j < 66; j++ ) boardstate[j] = data[i * 68 + ( j + 1 )]; /* load global variables one by one */ x = data[i * 68 + 4]; y = data[i * 68 + 5]; insert ( boardstate, movesHashTable, x, y ); } fclose ( loaded_opening_library_file ); return TRUE; } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* init_opening_library - initialises the opening hashtable library */ /* */ /* */ void init_opening_library ( void ) { movesHashTable = initialize_table ( OPENING_LIBRARY_HASH_SIZE ); if ( load_opening_library_file ( "OpenLib.lib" ) == FALSE ) { if ( VERBOSE ) printf ( "Opening Library failure detected.\n" ); } } /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* find_board_state_ident - assigns the distinct identifier to a board state */ /* */ /* */ char * find_board_state_ident ( void ) { char boardstate[66]; /* board state */ int i, /* index for board rows */ j; /* index for board columns */ for ( i = 0; i < 66; i++ ) boardstate[i] = '\0'; /* initialise the board state */ for ( i = 1; i < 9; i++ ) for ( j = 1; j < 9; j++ ) { if ( board.slot[i][j] == BLACK ) boardstate[( ( i - 1 ) * 8 + j ) - 1] = ( char ) BLACK; /* corresponds to the linear position of the board */ if ( board.slot[i][j] == RED ) boardstate[( ( i - 1 ) * 8 + j ) - 1] = ( char ) RED; if ( board.slot[i][j] == NONE ) boardstate[( ( i - 1 ) * 8 + j ) - 1] = ( char ) NONE; } boardstate[64] = ( char ) turn; /* retain the turn data as well */ boardstate[66] = '\0'; /* closing character */ //return &boardstate; /* returns a string */ return "a"; } /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /******************************************************************************/ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /* cpu_move - makes a move on behalf of color using the CPU */ /* */ /* */ void cpu_move ( int color ) { if ( playing_against_cpu ) /* only in case cpu is indeed requested to make move */ { int i = 0; int j = 0; /* loop indices */ int log_i = 0; /* records the move made */ int log_j = 0; /* records the move made */ int player_color = RED; /* the color of the object just put */ int opponent_color = BLACK; /* the color of the opponent */ int current_difficulty = BEGINNER; /* the inner difficulty which is applicable in this call */ int used_library; /* indicates if opening library was used */ if ( color == BLACK ) /* initialise the above values */ { player_color = BLACK; opponent_color = RED; current_difficulty = difficulty; } if ( color == RED ) /* when (gathering_statistics==TRUE) */ { opponent_color = BLACK; player_color = RED; current_difficulty = stat_mode_difficulty; } /* the following will make a move depending on the difficulty level */ used_library = FALSE; /* indicate that mive has not been made by library yet */ if ( use_opening_library && movecount < 10 ) { int lib_i = 1, lib_j = 1; /* record the coordinates of opening library placements */ char *board_state_ident; board_state_ident = find_board_state_ident ( ); if ( find ( board_state_ident, movesHashTable ) ) /* If Entry exists */ { lib_i = getX ( board_state_ident, movesHashTable ); lib_j = getY ( board_state_ident, movesHashTable ); board.slot[lib_i][lib_j] = player_color; /* place stone */ log_i = lib_i; log_j = lib_j; board = reduce ( lib_i, lib_j, board ); used_library = TRUE; /* indicate that move has been made */ } } if ( !used_library ) { if ( current_difficulty == BEGINNER ) { int foundflag = FALSE; /* says if item already put */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ void place_stone_for_beginner ( ) { board.slot[i][j] = player_color; log_i = i; log_j = j; board = reduce ( i, j, board ); foundflag = TRUE; } /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ while ( foundflag == FALSE ) { for ( i = 1; i < 9; i++ ) { if ( foundflag == FALSE ) { for ( j = 1; j < 9; j++ ) { if ( foundflag == FALSE ) { if ( reducible ( i, j, player_color, board ) ) { if ( non_determinism == FALSE ) place_stone_for_beginner ( ); /* place in first available */ else /* do not take the first possibility necessarily */ if ( random_number ( BEGINNER_RANDOMISATION_KEY ) == 0 ) /* according to random value */ place_stone_for_beginner ( ); /* decide if placement takes place */ } } } } } } /* repeat until move made */ } if ( current_difficulty == NOVICE ) { int best_i = 1; int best_j = 1; int best_score_so_far = SCORE_LOWER_BOUND; // cannot currently be lower int *vertical, *horizontal; if ( zero_one_random ( ) ) /* randomize these so scan lines can */ { /* vary */ vertical = &i; horizontal = &j; } else { vertical = &j; horizontal = &i; } for ( i = 1; i < 9; i++ ) { for ( j = 1; j < 9; j++ ) { if ( reducible ( *vertical, *horizontal, player_color, board ) ) /* if legal move */ { board_map temp_board; int current_score; temp_board = board; // copy of current board temp_board.slot[*vertical][*horizontal] = player_color; /* try placing a stone */ temp_board = reduce ( *vertical, *horizontal, temp_board ); /* reduce the temporary board */ if ( ( current_score = evaluate ( player_color, temp_board ) ) > best_score_so_far ) /* evaluate it */ { /* if that is the best choice so far record it */ best_score_so_far = current_score; best_i = *vertical; best_j = *horizontal; } } } } board.slot[best_i][best_j] = player_color; /* make the final move */ log_i = best_i; log_j = best_j; board = reduce ( best_i, best_j, board ); } // end NOVICE if ( current_difficulty == EXPERT ) // looks ahead 3 moves - assumes only best choice - depth 3 currently */ { int best_i = 1; int best_j = 1; int best_score_so_far = SCORE_LOWER_BOUND; // cannot currently be lower int *vertical, *horizontal; if ( zero_one_random ( ) ) /* randomize these */ { /* SEE ABOVE FOR MORE COMMENTS */ vertical = &i; horizontal = &j; } else { vertical = &j; horizontal = &i; } for ( i = 1; i < 9; i++ ) { for ( j = 1; j < 9; j++ ) { if ( reducible ( *vertical, *horizontal, player_color, board ) ) { board_map temp_board; int current_score; temp_board = board; // copy of current board temp_board.slot[*vertical][*horizontal] = player_color; temp_board = reduce ( *vertical, *horizontal, temp_board ); if ( ( current_score = evaluate ( player_color, compute_move_for_color ( compute_move_for_color ( temp_board, opponent_color ), player_color ) ) ) > best_score_so_far ) /* evaluate the board after 3 moves took place */ // depth 3: 3 moves ahead { best_score_so_far = current_score; best_i = *vertical; best_j = *horizontal; } } } } board.slot[best_i][best_j] = player_color; log_i = best_i; log_j = best_j; board = reduce ( best_i, best_j, board ); } // end EXPERT if ( current_difficulty == PRE_MASTER ) // looks ahead 14 moves - assuming only best choice - depth 14 currently */ { int best_i = 1; int best_j = 1; int best_score_so_far = SCORE_LOWER_BOUND; // cannot currently be lower for ( i = 1; i < 9; i++ ) { for ( j = 1; j < 9; j++ ) { if ( reducible ( i, j, player_color, board ) ) /* SEE NOVICE FOR COMMENTS */ { board_map temp_board; int current_score; temp_board = board; // copy of current board temp_board.slot[i][j] = player_color; temp_board = reduce ( i, j, temp_board ); if ( ( current_score = evaluate ( player_color, compute_move_for_color ( compute_move_for_color ( compute_move_for_color ( compute_move_for_color ( compute_move_for_color ( compute_move_for_color ( compute_move_for_color ( compute_move_for_color ( compute_move_for_color ( compute_move_for_color ( compute_move_for_color ( compute_move_for_color ( compute_move_for_color ( temp_board, opponent_color ), player_color ), opponent_color ), player_color ), opponent_color ), player_color ), opponent_color ), player_color ), opponent_color ), player_color ), opponent_color ), player_color ), opponent_color ) ) ) > best_score_so_far ) { // depth 14: 14 moves ahead best_score_so_far = current_score; /* record best choice so far */ best_i = i; best_j = j; } } } } //if ((best_i==1) && (best_j==1)) exit(1); /* &&& debugging */ board.slot[best_i][best_j] = player_color; /* make the placement */ log_i = best_i; log_j = best_j; board = reduce ( best_i, best_j, board ); } // end MASTER if ( current_difficulty == MASTER ) // looks ahead 3 moves - checks all choices of opponent { int best_i = 1; int best_j = 1; int best_score_so_far = SCORE_LOWER_BOUND; // cannot currently be lower for ( i = 1; i < 9; i++ ) { for ( j = 1; j < 9; j++ ) { if ( reducible ( i, j, player_color, board ) ) { board_map temp_board; int opponent_number_of_moves; int k; int score_acc; int move_factor; move_factor = MOVE_FACTOR; /* the coefficient of a board value */ score_acc = 0; temp_board = board; // copy of current board temp_board.slot[i][j] = player_color; temp_board = reduce ( i, j, temp_board ); opponent_number_of_moves = get_mobility_of_color ( temp_board, opponent_color ); /* find number of moves to evaluate */ for ( k = 1; k <= opponent_number_of_moves; k++ ) /* for all valid moves */ { board_map intermediate_board; /* another temp. board */ intermediate_board = make_nth_best_move ( temp_board, opponent_color, k ); /* make the Kth best move */ score_acc += MOVE_FACTOR * evaluate ( player_color, ( compute_move_for_color ( intermediate_board, player_color ) ) ); /* add it to the evaluation */ move_factor = move_factor / MOVE_FACTOR_DIVIDER; /* and update the score coefficient */ } if ( score_acc > best_score_so_far ) /* check if this score is the best so far */ { best_score_so_far = score_acc; /* record it if so */ best_i = i; best_j = j; } } } } board.slot[best_i][best_j] = player_color; /* place stone */ log_i = best_i; log_j = best_j; board = reduce ( best_i, best_j, board ); } //end MASTER } /* logging section */ if ( keep_log_file ) /* for all difficulties, if log file is kept */ { if ( player_color == BLACK ) fprintf ( log_file, "BLACK " ); if ( player_color == RED ) fprintf ( log_file, "RED " ); switch ( log_j ) { case 1: fprintf ( log_file, "A " ); break; case 2: fprintf ( log_file, "B " ); break; case 3: fprintf ( log_file, "C " ); break; case 4: fprintf ( log_file, "D " ); break; case 5: fprintf ( log_file, "E " ); break; case 6: fprintf ( log_file, "F " ); break; case 7: fprintf ( log_file, "G " ); break; case 8: fprintf ( log_file, "H " ); break; default: if ( debugging ) printf ( "stones put in invalid position on board\n" ); } switch ( log_i ) { case 1: fprintf ( log_file, "1\n" ); break; case 2: fprintf ( log_file, "2\n" ); break; case 3: fprintf ( log_file, "3\n" ); break; case 4: fprintf ( log_file, "4\n" ); break; case 5: fprintf ( log_file, "5\n" ); break; case 6: fprintf ( log_file, "6\n" ); break; case 7: fprintf ( log_file, "7\n" ); break; case 8: fprintf ( log_file, "8\n" ); break; default: if ( debugging ) printf ( "stones put in invalid position on board" ); } } cpuflag = !cpuflag; /* inverse this when passing turn */ movecount++; /* increment move number */ turn = opponent_color; /* pass turn */ calculate_mobility ( ); /* get new mobility */ check_deadlock ( ); /* and see if a deadlock has occured */ calculatescore ( ); /* update those score globals */ } //end if (playing_against_cpu) } /* */ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ /******************************************************************************/ /* */ /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ /* end of computation.c */ /************************************************************************/