/* This file is part of MINPANTU. See file `COPYRIGHT' for pertinent copyright notices. Ask the computer to make a move. */ #include #include #include #include "defs.h" #include "motion.h" #include "computer_player.h" #define INFINITY 1E6 /* Any sufficiently large value that won't ever come up during evaluation. */ #define OPPONENT(player) (1 - (player)) #define MAX_EFFORT 30 /* B */ #define MAX_DEPTH (MAX_EFFORT/4 + 1) #define NUMBER_OF_KILLER_MOVES 5 /* B */ #define MAX_GRID 13 /* B */ #define MAX_MOVES SQR(MAX_GRID) /* These control how `effort' is interpreted as search depth/width control. */ #define GRID_SIZE(effort) \ (((effort) <= 3) ? (2 * (effort) + 1) \ : MIN(2 * (effort) - 1, MAX_GRID)) #define EFFORT_LEFT(effort) \ ((effort) <= 3 ? 0 : (effort) - 3) /* Assuming there has been `tm' seconds ago a change in the velocity of a hit ball located at `hx,hy', then guesstimate how likely it is unable to affect the location of the goal ball in location `x,y'. */ static double probability(double x, double y, double hx, double hy, double tm) { double required_intercept_speed; if (tm <= 0) /* It's still fully deterministic. */ return 0; /* The constants below may need some tuning. */ #define PROBABILITY_MIN_CHANGE_DISTANCE 20 #define PROBABILITY_MIN_CHANGE_SPEED 50 #define PROBABILITY_MAX_CHANGE_SPEED 800 required_intercept_speed = (DISTANCE(x, y, hx, hy) - PROBABILITY_MIN_CHANGE_DISTANCE) / tm; if (required_intercept_speed <= PROBABILITY_MIN_CHANGE_SPEED) return 0; else if (required_intercept_speed >= PROBABILITY_MAX_CHANGE_SPEED) return 1; else return (1.0 / (PROBABILITY_MAX_CHANGE_SPEED - PROBABILITY_MIN_CHANGE_SPEED)) * (required_intercept_speed - PROBABILITY_MIN_CHANGE_SPEED); } /* We use two basic methods to choose a move for the computer: classic minimax/alpha-beta search as described in the AI literature, and positional evaluation by following the trajectories of the balls far into the future and assessing heuristically their probabilities of passing through the goals. The routine below does the latter; it computes the motion the given state `ball_state_in' to `2 * MOVE_TIME' into the future (two moves for both players) and assesses how beneficial the initial state is for the players. */ static double inexact_follow_move(int player, double *ball_state_in, int *ball_is_in_base_in, int player_goals, int opponent_goals) { double time, credit; double opponent_gains_control_x, opponent_gains_control_y; double player_gains_control_x, player_gains_control_y; double ball_state[BALL_STATE_VECTOR_LENGTH]; int ball_is_in_base[NUMBER_OF_BALLS]; int step, i, opponent = OPPONENT(player); assert(player == 1 || player == 0); memcpy(ball_state, ball_state_in, sizeof(ball_state)); memcpy(ball_is_in_base, ball_is_in_base_in, sizeof(ball_is_in_base)); opponent_gains_control_x = player_gains_control_x = -1; credit = 0; for (time = step = 0; step < 2 * STEPS_PER_MOVE; step++, time += INTEGRATE_STEP) { /* Compute the next positions of the balls. */ if (step >= STEPS_PER_MOVE) integrate_step(ball_state, sloppy_derive_state, INTEGRATE_STEP); else integrate_step(ball_state, derive_state, INTEGRATE_STEP); /* Memorize where the opponent and the player regain control and the positions become increasingly unpredictable. */ if (step >= STEPS_PER_PLY && opponent_gains_control_x == -1) { opponent_gains_control_x = BALL_X_LOCATION(ball_state, opponent); opponent_gains_control_y = BALL_Y_LOCATION(ball_state, opponent); } if (step >= STEPS_PER_MOVE && player_gains_control_x == -1) { player_gains_control_x = BALL_X_LOCATION(ball_state, player); player_gains_control_y = BALL_Y_LOCATION(ball_state, player); } /* Check for goals, or near goals, and credit the moves accordinly. The further away the potential goal is, the more likely it is that the opponent has a chance to intercept the goal ball, and the less the goal (or a near goal) will affect the assessment. */ for (i = 0; i < NUMBER_OF_BALLS; i++) if (IS_GOAL_BALL(i)) { double distance_from_player_base, distance_from_opponent_base; double effect_of_opponent, effect_of_player; distance_from_player_base = DISTANCE(BALL_X_LOCATION(ball_state, i), BALL_Y_LOCATION(ball_state, i), base[player].x, base[player].y); distance_from_opponent_base = DISTANCE(BALL_X_LOCATION(ball_state, i), BALL_Y_LOCATION(ball_state, i), base[opponent].x, base[opponent].y); effect_of_player = 1 - probability(BALL_X_LOCATION(ball_state, i), BALL_Y_LOCATION(ball_state, i), player_gains_control_x, player_gains_control_y, time - MOVE_TIME); effect_of_opponent = 1 - probability(BALL_X_LOCATION(ball_state, i), BALL_Y_LOCATION(ball_state, i), opponent_gains_control_x, opponent_gains_control_y, time - PLY_TIME); /* Check for goals. The further in future the */ if (distance_from_player_base < base[player].radius) { if (!ball_is_in_base[i]) { ball_is_in_base[i] = 1; credit -= 1100 * (1 - 0.7 * effect_of_player); } } else if (distance_from_opponent_base < base[opponent].radius) { if (!ball_is_in_base[i]) { ball_is_in_base[i] = 1; credit += 1000.0 * (1 - 0.8 * effect_of_opponent); } } else if (ball_is_in_base[i]) ball_is_in_base[i] = 0; /* Positional evaluations; reward for being close to the opponent's base and punish for being close to own base. */ if (distance_from_opponent_base < base[opponent].radius + 10 * effect_of_player) credit += 0.5 * (base[opponent].radius - distance_from_opponent_base + 10) * effect_of_player; if (distance_from_player_base < base[player].radius + 10 * effect_of_opponent) credit -= 0.3 * (base[player].radius - distance_from_player_base + 10) * effect_of_opponent; } } return 1000 * (player_goals - opponent_goals) + credit; } /* Forward declaration. */ static double exact_follow_move(int effort, int depth, int player, double *ball_state_in, int *ball_is_in_base_in, double alpha, double beta, int player_goals, int opponent_goals); /* The killer move buffer should survive over function calls, so we make it static. The idea of killer moves is to cause the alpha-beta cutoff as early as possible by trying first moves that earlier had proven strong. The killer-move heuristic used here has been able to reduce the branching factor of the search tree from approximately ~5.5 to ~3.25 on the second level of a (9x9)x(5x5) search. */ static struct { int x_i, y_i; } killer_move_table[MAX_DEPTH][NUMBER_OF_KILLER_MOVES]; static void clear_killer_moves(void) { int i, j; for (i = 0; i <= MAX_DEPTH; i++) for (j = 0; j < NUMBER_OF_KILLER_MOVES; j++) killer_move_table[i][j].x_i = killer_move_table[i][j].y_i = -1; } static void insert_killer_move(int depth, int x_i, int y_i) { int i; assert(depth < MAX_DEPTH); /* Check whether the killer move is already in the killer move table, if it is, put its index in `i'. If the killer move was not in the table, assign `i' `NUMBER_OF_KILLER_MOVES-1' */ for (i = 0; i < NUMBER_OF_KILLER_MOVES - 1; i++) if (killer_move_table[depth][i].x_i == x_i && killer_move_table[depth][i].y_i == y_i) break; /* Move the older killer moves upwards, stomping the new killer if it was already in the table. */ for (; i > 0; i--) { killer_move_table[depth][i].x_i = killer_move_table[depth][i-1].x_i; killer_move_table[depth][i].y_i = killer_move_table[depth][i-1].y_i; } /* Put the new killer move first. */ killer_move_table[depth][0].x_i = x_i; killer_move_table[depth][0].y_i = y_i; } typedef struct { int x_i, y_i, killer_value; } move_t; /* A function passed to `qsort' from `min_max_choose_move'. */ static int killer_value_cmp(const move_t *m1, const move_t *m2) { return m2->killer_value - m1->killer_value; } static double min_max_choose_move(int effort, int depth, int player, double *ball_state, int *ball_is_in_base, double alpha, double beta, int player_goals, int opponent_goals) { int x_i, y_i, max_i, i; double grid_x_size, grid_y_size, credit, best_so_far; double x_speed_backup, y_speed_backup; move_t move[MAX_MOVES]; /* Instead of making a full copy of `ball_state', as in `exact_follow_move', we take a backup only of the two values of `ball_state' that this routine will change. */ x_speed_backup = BALL_X_SPEED(ball_state, player); y_speed_backup = BALL_Y_SPEED(ball_state, player); assert(effort > 0); max_i = GRID_SIZE(effort); assert(SQR(max_i) <= MAX_MOVES); grid_x_size = (2 * MAX_X_SPEED) / (double) (max_i - 1); grid_y_size = (2 * MAX_Y_SPEED) / (double) (max_i - 1); /* Fill in the move table with a set of plausible moves. */ for (x_i = 0; x_i < max_i; x_i++) { for (y_i = 0; y_i < max_i; y_i++) { move[x_i * max_i + y_i].x_i = x_i; move[x_i * max_i + y_i].y_i = y_i; move[x_i * max_i + y_i].killer_value = 0; } } /* Assign moves their heuristic killer values. */ for (i = 0; i < NUMBER_OF_KILLER_MOVES; i++) if (killer_move_table[effort][i].x_i != -1) { x_i = killer_move_table[effort][i].x_i; y_i = killer_move_table[effort][i].y_i; /* Give the actual killer move a handsome bonus. */ move[x_i * max_i + y_i].killer_value += 8 * (NUMBER_OF_KILLER_MOVES - i); /* Give moves close to killer moves additional smaller bonuses. */ if (x_i >= 1) { if (y_i >= 1) move[(x_i-1) * max_i + (y_i-1)].killer_value++; move[(x_i-1) * max_i + y_i].killer_value += 2; if (y_i < max_i-1) move[(x_i-1) * max_i + (y_i+1)].killer_value++; } if (y_i >= 1) move[x_i * max_i + (y_i-1)].killer_value++; if (y_i < max_i-1) move[x_i * max_i + (y_i+1)].killer_value++; if (x_i < max_i-1) { if (y_i >= 1) move[(x_i+1) * max_i + (y_i-1)].killer_value++; move[(x_i+1) * max_i + y_i].killer_value += 2; if (y_i < max_i-1) move[(x_i+1) * max_i + (y_i+1)].killer_value++; } } /* Sort the move table into descending order. */ qsort(move, SQR(max_i), sizeof(move_t), killer_value_cmp); /* Traverse the moves in the presumed-best-first order performing minimaxing and alpha-beta-cutoffs where possible. */ best_so_far = -INFINITY; for (i = 0; i < SQR(max_i); i++) { BALL_X_SPEED(ball_state, player) = -MAX_X_SPEED + move[i].x_i * grid_x_size; BALL_Y_SPEED(ball_state, player) = -MAX_Y_SPEED + move[i].y_i * grid_y_size; if (EFFORT_LEFT(effort) > 0) credit = exact_follow_move(EFFORT_LEFT(effort), depth, player, ball_state, ball_is_in_base, -beta, -MAX(alpha, best_so_far), player_goals, opponent_goals); else credit = inexact_follow_move(player, ball_state, ball_is_in_base, player_goals, opponent_goals); if (credit > best_so_far) { best_so_far = credit; if (best_so_far >= beta) { insert_killer_move(effort, move[i].x_i, move[i].y_i); goto alpha_beta_cutoff; } } } alpha_beta_cutoff: /* Restore the original values to `ball_state'. */ BALL_X_SPEED(ball_state, player) = x_speed_backup; BALL_Y_SPEED(ball_state, player) = y_speed_backup; return best_so_far; } static double exact_follow_move(int effort, int depth, int player, double *ball_state_in, int *ball_is_in_base_in, double alpha, double beta, int player_goals, int opponent_goals) { int i, step; double ball_state[BALL_STATE_VECTOR_LENGTH]; int ball_is_in_base[NUMBER_OF_BALLS]; assert(effort > 0); assert(depth < MAX_DEPTH); assert(player == 1 || player == 0); memcpy(ball_state, ball_state_in, sizeof(ball_state)); memcpy(ball_is_in_base, ball_is_in_base_in, sizeof(ball_is_in_base)); for (step = 0; step < STEPS_PER_PLY; step++) { integrate_step(ball_state, derive_state, INTEGRATE_STEP); for (i = 0; i < NUMBER_OF_BALLS; i++) if (IS_GOAL_BALL(i)) if (DISTANCE_SQR(BALL_X_LOCATION(ball_state, i), BALL_Y_LOCATION(ball_state, i), base[player].x, base[player].y) < SQR(base[player].radius)) { if (!ball_is_in_base[i]) { ball_is_in_base[i] = 1; opponent_goals++; } } else if (DISTANCE_SQR(BALL_X_LOCATION(ball_state, i), BALL_Y_LOCATION(ball_state, i), base[OPPONENT(player)].x, base[OPPONENT(player)].y) < base[OPPONENT(player)].radius) { if (!ball_is_in_base[i]) { ball_is_in_base[i] = 1; player_goals++; } } else ball_is_in_base[i] = 0; } return -min_max_choose_move(effort, depth + 1, OPPONENT(player), ball_state, ball_is_in_base, alpha, beta, opponent_goals, player_goals); } void choose_move(int effort, int player, double *ball_state, int *ball_is_in_base, int player_goals, int opponent_goals) { int x_i, y_i, max_i; double x, y, grid_x_size, grid_y_size, credit, best_so_far; double best_x_speed, best_y_speed; switch (effort) { case EFFORT_NO_PLAYER: return; break; case EFFORT_RANDOM_PLAYER: BALL_X_SPEED(ball_state, player) = -MAX_X_SPEED + (rand() % (2 * MAX_X_SPEED + 1)); BALL_Y_SPEED(ball_state, player) = -MAX_Y_SPEED + (rand() % (2 * MAX_Y_SPEED + 1)); return; break; default: assert(effort > 0); max_i = GRID_SIZE(effort); break; } grid_x_size = (2 * MAX_X_SPEED) / (double) (max_i - 1); grid_y_size = (2 * MAX_Y_SPEED) / (double) (max_i - 1); clear_killer_moves(); best_so_far = -INFINITY; for (x_i = 0; x_i < max_i; x_i++) { x = -MAX_X_SPEED + x_i * grid_x_size; for (y_i = 0; y_i < max_i; y_i++) { y = -MAX_Y_SPEED + y_i * grid_y_size; BALL_X_SPEED(ball_state, player) = x; BALL_Y_SPEED(ball_state, player) = y; if (effort >= 5) credit = exact_follow_move(EFFORT_LEFT(effort), 0, player, ball_state, ball_is_in_base, -INFINITY, -best_so_far, player_goals, opponent_goals); else credit = inexact_follow_move(player, ball_state, ball_is_in_base, player_goals, opponent_goals); if (credit > best_so_far) { best_so_far = credit; best_x_speed = x; best_y_speed = y; } } } BALL_X_SPEED(ball_state, player) = best_x_speed; BALL_Y_SPEED(ball_state, player) = best_y_speed; }