Subversion Repositories connect-6

/*

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

Copyright (C) 2007 Michael Levin

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

#include <glib.h>

#include "../shared.h"

static int window_dir(const Board *b, BCOORD x, BCOORD y, PIECE type,

                      int dx, int dy, int *length, int *count)

{

        int i, j, min_i, max_i, min_block = 0, max_block = 0, max = 0;

        PIECE p;

        if (!dx && !dy)

                return 0;

        /* Find the lowest index i along our diagonal that is valid and is

           still a window containing (x, y) and count the number of pieces

           inside */

        for (i = 0; i > -connect_k; i--) {

                p = piece_at(b, x + dx * i, y + dy * i);

                if (p != type && p != PIECE_NONE) {

                        min_block = 1;

                        break;

                }

        }

        min_i = max_i = ++i;

        for (j = i; j < i + connect_k; j++) {

                p = piece_at(b, x + dx * j, y + dy *j);

                if (p == type)

                        max++;

                else if (p != PIECE_NONE)

                        return 0;

        }

        /* Slide out window along and find the smallest and largest maximum

           count positions */

        j = max;

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

                p = piece_at(b, x + dx * i, y + dy * i);

                if (p == type)

                        j--;

                p = piece_at(b, x + dx * (i + connect_k),

                             y + dy * (i + connect_k));

                if (p == type)

                        j++;

                else if (p != PIECE_NONE) {

                        max_block = 1;

                        break;

                }

                if (j == max)

                        max_i = i + 1;

                else if (j > max) {

                        max = j;

                        min_i = max_i = i + 1;

                }

        }

        /* Check if we have blocked multiple threats with this move */

        *count = 1;

        if (min_block || min_i > -connect_k + 1 ||

            ((p = piece_at(b, x - dx * connect_k, y - dy * connect_k)) !=

              type && p != PIECE_NONE))

                for (i = min_i; i < max_i; i++) {

                        p = piece_at(b, x + dx * i, y + dy * i);

                        if (p == PIECE_NONE)

                                (*count)++;

                        else if (p == PIECE_ERROR)

                                break;

                }

        if (max_block || max_i < 0 ||

            ((p = piece_at(b, x + dx * connect_k, y + dy * connect_k)) !=

             type && p != PIECE_NONE))

                for (i = min_i + connect_k; i < max_i + connect_k; i++) {

                        p = piece_at(b, x + dx * i, y + dy * i);

                        if (p == PIECE_NONE)

                                (*count)++;

                        else if (p == PIECE_ERROR)

                                break;

                }

        *length = max;

        return 1;

}

static AIWEIGHT window(const Board *b, BCOORD x, BCOORD y, PIECE turn)

{

        int lines[MAX_CONNECT_K], xs[] = {1, 1, 0, -1}, ys[] = {0, 1, 1, 1}, i;

        AIWEIGHT weight;

        PIECE type;

        memset(lines, 0, sizeof (lines));

        type = piece_at(b, x, y);

        if (type != PIECE_NONE)

                return AIW_NONE;

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

                int length, count;

                if (!window_dir(b, x, y, turn, xs[i], ys[i], &length, &count))

                        continue;

                lines[length] += count;

        }

        /* Bit pack the weight */

        weight = AIW_NONE;

        for (i = 1; i < connect_k; i++)

                weight += lines[i] << ((i - 1) * 6);

        return weight;

}

AIMoves *ai_windows(const Board *b)

{

        AIMoves *moves;

        AIMove move;

        PIECE opp = other_player(b->turn);

        moves = aimoves_new();

        moves->utility = AIW_NONE;

        for (move.y = 0; move.y < board_size; move.y++)

                for (move.x = 0; move.x < board_size; move.x++) {

                        move.weight = window(b, move.x, move.y, opp);

                        if (move.weight > AIW_NONE)

                                aimoves_append(moves, &move);

                }

        return moves;

}