Subversion Repositories connect-6

/*

connectk -- a program to play the connect-k family of games

Copyright (C) 2007 Jeff Deitch

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 <glib.h>

#include "../shared.h"

#define MONTE_N 10

#define MONTE_NUM_RUNS 1000

// sequences.c

AIMoves *move_utilities(const Board *b);

AIMoves *empty_cells(Board *b)

/* returns an array of the empty locations on board b */

{

        int i, j;

        AIMoves *empties = aimoves_new();

        AIMove move;

        for (i = 0; i < board_size; i++) {

                for (j = 0; j < board_size; j++) {

                        if (piece_at(b, i, j) == PIECE_NONE) {

                                move.x = i;

                                move.y = j;

                                move.weight = 0.f;

                                aimoves_add(empties, &move);

                        }

                }

        }

        return empties;

}

int mc_run(Board *b)

/* plays a random game on board b, returns 1 if the current player wins

and 0 otherwise */

{

        Board *new_board = board_new();

        board_copy(b, new_board);

        AIMove move;

        AIMoves *empties;

        empties = empty_cells(new_board);

        int tries = 0;

        int i;

        while ( TRUE ) {

                /* if the board filled up, start over */

                if (empties->len == 0) {

                        board_copy(b, new_board);

                        empties = empty_cells(new_board);

                        tries++;

                        if (tries == 10) {

                                g_debug("bailing");

                                board_free(new_board);

                                aimoves_free(empties);

                                return 0;

                        }

                }

                i = g_random_int_range(0, empties->len);

                move = empties->data[i];

                aimoves_remove_index_fast(empties, i);

                place_piece(new_board, move.x, move.y);

                if (check_win(new_board, move.x, move.y)) {

                        if (new_board->turn == board->turn) {

                                board_free(new_board);

                                aimoves_free(empties);

                                return 1;

                        }

                        else {

                                board_free(new_board);

                                aimoves_free(empties);

                                return 0;

                        }

                }

                new_board->moves_left--;

                if (new_board->moves_left == 0) {

                        new_board->turn = other_player(new_board->turn);

                        new_board->moves_left = place_p;

                }

        }

}

AIMoves *ai_monte_carlo(const Board *b)

/* chooses the best move based on which one wins the most random games */

{

        int i, k, wins, len;

        Board *new_board = board_new();

        AIMove move;

        AIMoves *moves = move_utilities(b);

        moves->utility = 0;

        aimoves_crop(moves, MONTE_N);

        len = moves->len;

        for (i = 0; i < len; i++) {

                move = moves->data[i];

                board_copy(b, new_board);

                place_piece(new_board, move.x, move.y);

                if (check_win(new_board, move.x, move.y)) {

                        move.weight = MONTE_NUM_RUNS;

                        moves->data[i] = move;

                        moves->utility += MONTE_NUM_RUNS;

                } else {

                        /* run the monte carlo trials */

                        wins = 0;

                        for (k = 0; k < MONTE_NUM_RUNS; k++) {

                                wins += mc_run(new_board);

                        }

                        move.weight = wins;

                        moves->data[i] = move;

                        moves->utility += wins;

                }

        }

        board_free(new_board);

        return moves;

}