крестики-нолики с использованием альфа-бета-сокращения в Java - PullRequest
Новая
       14

крестики-нолики с использованием альфа-бета-сокращения в Java

5 голосов
/ 16 февраля 2010

Я пытаюсь играть в крестики-нолики, используя итеративное сокращение альфа-бета, У меня есть один второй предел на ход, но по какой-то причине не работает хорошо.

Я изменил обычный альфа-бета-код, чтобы вместо возврата альфа или бета, возвращает состояние (то есть доска с следующим ходом)

Каждый раз, когда я создаю детей, я обновляю их глубину.

Но опять же по какой-то причине я продолжаю проигрывать и вижу, что моя альфа-бета не видит лучшего хода.

Вот мой код:

Внешний цикл: 

while (watch.get_ElapsedMilliseconds() < 900 && d <= board.length * board[0].length - 1)
        {
            s = maxiMin(beginSt, d, watch);
            if (s.getNextMove().getIsWin() == true)
            {
                break;
            }
            d++;
        }
        return new location(s.getNextMove().getRow(), s.getNextMove().getCol());

Альфа-бета: 

public State maxiMin(State s, int depth, Stopwatch timer)
    {
        if (s.getDepth() == 7)
        {
            Console.WriteLine();
        }
        if (timer.get_ElapsedMilliseconds() > 850 || s.getDepth() == depth || goalTest(s.getBoard()) != 0)
        {
            s.evaluationFunc(line_length, PlayerShape);
            s.setAlpha(s.getEvaluation());
            s.setBeta(s.getEvaluation());
            return s;
        }
        LinkedList<State> children = createChildren(s, true);
        // No winner, the board is full
        if (children.get_Count() == 0)
        {
            s.evaluationFunc(line_length, PlayerShape);
            s.setAlpha(s.getEvaluation());
            s.setBeta(s.getEvaluation());
            return s;
        }
        while (children.get_Count() > 0)
        {
            State firstChild = children.get_First().get_Value();
            children.RemoveFirst();
            State tmp = miniMax(firstChild, depth, timer);
            int value = tmp.getBeta();
            if (value > s.getAlpha())
            {
                s.setAlpha(value);
                s.setNextMove(tmp);
            }
            if (s.getAlpha() >= s.getBeta())
            {
                return s;
            }
        }
        return s;
    }

    public State miniMax(State s, int depth, Stopwatch timer)
    {
        if (s.getDepth() == 7)
        {
            Console.WriteLine();
        }
        if (timer.get_ElapsedMilliseconds() > 850 || s.getDepth() == depth || goalTest(s.getBoard()) != 0)
        {
            s.evaluationFunc(line_length, PlayerShape);
            s.setAlpha(s.getEvaluation());
            s.setBeta(s.getEvaluation());
            return s;
        }
        LinkedList<State> children = createChildren(s, false);
        // No winner, the board is full
        if (children.get_Count() == 0)
        {
            s.evaluationFunc(line_length, PlayerShape);
            s.setAlpha(s.getEvaluation());
            s.setBeta(s.getEvaluation());
            return s;
        }
        while (children.get_Count() > 0)
        {
            State firstChild = children.get_First().get_Value();
            children.RemoveFirst();
            State tmp = maxiMin(firstChild, depth, timer);
            int value = tmp.getAlpha();
            if (value < s.getBeta())
            {
                s.setBeta(value);
                s.setNextMove(tmp);
            }
            if (s.getAlpha() >= s.getBeta())
            {
                return s;
            }
        }
        return s;
    }

Будет много ценить, если кто-нибудь скажет мне, если что-то не так. Я подозреваю, что может быть это как-то связано с тем, что я возвращаю "S" вместо обычной альфа-бета который возвращает оценку, но мне не удалось найти ошибку.

Заранее спасибо,

Lena

1 Ответ

5 голосов
/ 16 февраля 2010

Во-первых, крестики-нолики - очень простая игра, и я считаю, что ее можно решить с помощью гораздо более простого кода, в основном потому, что мы знаем, что всегда есть опция связывания, а общее число состояний меньше 3 ^ 9 включая симметричные и многие невозможные состояния).

Что касается вашего кода, я считаю, что одной из ваших проблем является то, что вы, похоже, не увеличиваете глубину рекурсивных вызовов.

у вас также есть много проблем с плохим стилем в вашем коде, вы разделили miniMax и MaxiMin на две функции, хотя они в основном одинаковы. вы перебираете коллекцию, удаляя из нее элементы, а не используете for-each или итератор (или даже int итератор).

...