IT Notes

Игровой искусственный интеллект: Простейшие алгоритмы

Предыдущие части:

  1. Игровой искусственный интеллект: Введение
  2. Игровой искусственный интеллект: Тестовая площадка

Что нового

Чтобы получить исходники обновленного тестового приложения, вы можете скачать архив с github, или взять их из git-репозитория (тег v1.1).

ai-testbed-application

Отличия от предыдущей версии:

  1. Представление расширено виджетом-оберткой, который содержит элементы управления для сброса состояния Модели и переключения между алгоритмами ИИИ "на лету";
  2. Модель больше не является владельцем объекта-ИИИ. Вместо std::unique_ptr используется std::shared_ptr;
  3. Реализовано и интегрировано несколько алгоритмов ИИИ;
  4. Для алгоритмов ИИИ добавлена функция-член reset(), предназначенная для сброса состояния. Она требуется в тех случаях, когда ИИИ имеет внутреннюю память;
  5. Проведены мелкие улучшения кода для упрощения работы с ним.

Более подробно о всех изменениях вы можете узнать из комментариев в git-репозитории.

Наиболее интересным изменением здесь является возможность регистрации и выбора алгоритмов ИИИ. Эти функции реализованы в главном виджете (оборачивающем Представление):

void MainWidget::registerAI( const QString& name, BotAI* ai ) {
    if( m_aiCmb ) {
        // Если комбо-бокс инициализирован

        // Добавляем в него название ИИИ
        m_aiCmb->addItem( name );

        // И сохраняем сам объект ИИИ
        m_ais.push_back( std::shared_ptr< BotAI >( ai ) );
    }

    if( m_ais.size() == 1 ) {
        // Если добавлен первый ИИИ, то активируем его
        onAIChanged( 0 );
    }
}

// Этот слот привязан к сигналу currentIndexChanged() комбо-бокса m_aiCmb
void MainWidget::onAIChanged( int i ) {
    if( 0 <= i && static_cast< size_t >( i ) < m_ais.size() ) {
        // Устанавливаем i-ый зарегистрированный ИИИ
        m_model.setAI( m_ais[ i ] );
    }
}

Тогда инициализация ИИИ в main() выглядит так:

int main( int argc, char* argv[] ) {
    QApplication a( argc, argv );

    MainWidget w;
    w.registerAI( "EasyRandomAI", new EasyRandomAI );
    w.registerAI( "SmartRandomAI", new SmartRandomAI );
    w.registerAI( "SingleMemRandomAI", new SingleMemRandomAI );
    w.registerAI( "AccumulatingRandomAI", new AccumulatingRandomAI );
    w.registerAI( "SmartSingleMemRandomAI", new SmartSingleMemRandomAI );
    w.show();

    return a.exec();
}

Из этих ИИИ нам пока что знаком только первый - EasyRandomAI, который мы создали в прошлый раз. Теперь разберемся с остальными.

SmartRandomAI

Визуально EasyRandomAI вел себя уж слишком примитивно. Сделаем его "умную" версию, запретив биться об стену. Для этого добавим в Модель функцию, которая находит допустимые направления (не в стену):

std::vector< Bot::Direction > AIModel::findValidDirections( const Bot& bot ) const {
    std::vector< Bot::Direction > directions;
    for( int i = 0; i < Bot::DIRECTION_COUNT; ++i ) {
        // Для каждого направления (вверх, вниз, влево, вправо)

        // Делаем копию Бота
        Bot botCopy = bot;

        // Устанавливаем его направление
        Bot::Direction d = Bot::Direction( i );
        botCopy.setDirection( d );

        // Пробуем сдвинуть Бота на одну точку в проверяемом направлении
        botCopy.move( 1 );

        if( !hasCollisions( botCopy ) ) {
            // Направление допустимо, если столкновения со стеной не произошло
            directions.push_back( d  );
        }
    }

    return directions;
}

С такой функцией реализация SmartRandomAI становится тривиальной:

void SmartRandomAI::doStep( const AIModel& model, Bot* bot ) {
    auto directions = model.findValidDirections( *bot );
    bot->startMoving();
    bot->setDirection( directions[ rand() % directions.size() ] );
}

Стоит признать, что такой ИИИ выглядит не очень умно. Но разница в поведении по сравнению с Easy-версией все же заметна. Главное, что мы получили при реализации этого ИИИ, - крайне полезная функция findValidDirections().

SingleMemRandomAI

Создадим ИИИ, который берет решение не просто с потолка (по рандому), а на основе хоть какого-то анализа своих предыдущих действий. Идея следующая: если на прошлом шаге Бот шел в направлении, которое допустимо и на текущем шаге, то пусть так и идет (ничего не трогаем), иначе выбираем одно из допустимых направлений случайным образом (как в SmartRandomAI). Реализовать такой ИИИ очень просто:

ai-singlememrandomai-cycle

void SingleMemRandomAI::doStep( const AIModel& model, Bot* bot ) {
    bot->startMoving();
    auto directions = model.findValidDirections( *bot );
    if(
        std::find(
            directions.begin(),
            directions.end(),
            bot->getDirection()
        ) == directions.end()
    ) {
        // Меняем направление лишь тогда,
        // когда текущего нет в списке допустимых на этом шаге
        bot->setDirection( directions[ rand() % directions.size() ] );
    }
}

Поведение этого ИИИ интереснее, чем то, что мы рассматривали до этого. Он водит Ботов по линейным траекториям, которые выглядят намного "разумнее", чем неуверенные дерганья его предшественников.

Однако он не лишен недостатков. Основная претензия к этому ИИИ заключается в том, что он уж слишком линейный. Пока Бот во что-то не врежется, он никуда не свернет. Это может привести к появлению замкнутых кругов, как на скриншоте (область, выделенная красным цветом).

Поэтому такой ИИИ не подойдет для случаев, когда игровой мир слишком ровный. Чем больше препятствий, тем интереснее поведение этого алгоритма.

AccumulatingRandomAI

При разработке предыдущего ИИИ мы немного схитрили. На самом деле у него не было своей памяти. Для анализа предшествующего шага он использовал лишь состояние Бота. В этот раз мы пойдем другим путем. Создадим улучшенную версию SmartRandomAI, добавив эффект накопления:

  1. Пусть изначально все допустимые направления имеют равную вероятность выбора (то же самое, что и для SmartRandomAI);
  2. Когда мы выбираем какое-то направление, то наращиваем вероятность его выбора для следующего раза. Идея схожа с SingleMemRandomAI, однако ИИИ теперь не столь доверчив. Логика достаточно разумна - если обычно слева все хорошо, то скорее всего, и в следующий раз там будет все замечательно, но не факт;
  3. Учитываем, что нельзя допускать, чтобы вероятность выбора какого-то направления была нулевой, иначе больше Бот в эту сторону ходить не будет;
  4. Теперь нам не обойтись без внутренней памяти ИИИ, в которой будем хранить 4 вероятности (на каждое направление) для всех Ботов. Сама память представляется собой простую Хэш-карту, ключом которой является идентификатор Бота.

Реализовать такой ИИИ можно следующим образом:

static const int MAX_CHANCE = 100;
static const int MIN_CHANCE = 5;

void AccumulatingRandomAI::doStep( const AIModel& model, Bot* bot ) {
    bot->startMoving();

    if( !m_memory.contains( bot->getID() ) ) {
        // Если ИИИ ничего не знает о Боте, то заводим новую ячейку в памяти
        // Шанс выбора любого направления один и тот же (25 из 100)
        m_memory[ bot->getID() ].resize( Bot::DIRECTION_COUNT, MAX_CHANCE / Bot::DIRECTION_COUNT );
    }

    auto directions = model.findValidDirections( *bot );

    // Нам нужны шансы для допустимых на данном шаге направлений
    // chances[ 0 ] = chances[ Bot::LEFT ] - шанс, что Бот пойдет налево
    // chances[ 1 ] = chances[ Bot::RIGHT ] - шанс, что Бот пойдет направо
    // и т.д.
    std::vector< double > chances( Bot::DIRECTION_COUNT, 0 );
    for( auto d : directions ) {
        // Для каждого допустимого направления добавляем
        chances[ d ] = m_memory[ bot->getID() ][ d ];
    }

    // Выбираем случайное число от нуля до суммарного значения шансов для текущего шага
    // Суммарное значение не обязательно будет сотней, поскольку не все направления могут оказаться допустимыми
    const int p = rand() % std::accumulate( chances.begin(), chances.end(), 0 );

    // Выбираем направление, исходя из распределения вероятностей
    // В какую из областей попало случайное число p, туда и идем:
    // 0                 25                 50               75             100
    // |== Идем налево ==|== Идем направо ==|== Идем вверх ==|== Идем вниз ==|
    //                             ^ - например, p попало сюда, поэтому идем направо
    double sum = 0;
    size_t i = 0;
    for( ; i < chances.size(); ++i ) {
        sum += chances[ i ];
        if( p < sum ) {
            break;
        }
    }
    const Bot::Direction direction = Bot::Direction( i );
    bot->setDirection( direction );

    // Перераспределяем шансы для следующего шага
    for( int i = 0; i < Bot::DIRECTION_COUNT; ++i ) {
        // Для каждого направления
        if( i == direction ) {
            // Пропускаем выбранное на текущем шаге направление
            continue;
        }
        if( MIN_CHANCE < m_memory[ bot->getID() ][ i ] ) {
            // Если шансы по направлению больше минимума (5 в данной реализации), то производим
            // перераспределение
            m_memory[ bot->getID() ][ i ]--;
            m_memory[ bot->getID() ][ direction ]++;
        }
    }
}

void AccumulatingRandomAI::reset() {
    m_memory.clear();
}

Реализация получилась не самой простой, но думаю, что вы без труда в ней разберетесь.

ai-accumulatingrandomai

Поведение этого алгоритма не намного лучше, чем у "чисто" случайных. Однако он имеет одну интересную особенность. Этот ИИИ в какой-то мере учится обходить препятствия. Обучение это весьма условное, но оно есть. Обратите внимание на отмеченную траекторию движения на скриншоте выше. Когда ИИИ решил, что Боту нужно идти вверх (шанс движения вверх стал выше, чем у остальных направлений), то он достаточно быстро обходит простые преграды.

Объяснить такое поведение можно следующим образом: основной вектор движения Бота направлен вверх. Вниз он соберется идти не скоро. В одну сторону по горизонтали ему мешает идти стена, поэтому он постепенно "понимает", что имеет смысл попробовать пойти в противоположную сторону (при этом продолжая пытаться идти вверх), попадая в проход. В результате Бот сам находит путь от одного конца лабиринта до другого. Однако у него это не всегда получается.

Такой алгоритм сложно назвать особо полезным. Он довольно неуклюж, поскольку на переползание шансов с одного направления на другое уходит много времени (из-за этого Боты в основном просто бьются об стены). Конечно, можно поэкспериментировать с ним, но добиться приемлемого поведения будет проблематично.

SmartSingleMemRandomAI

Улучшим алгоритм SingleMemRandomAI - уберем проблему зацикливания. Для этого будем учитывать развилки в лабиринте. Бот не будет просто продолжать следовать в выбранном направлении (если оно остается допустимым), а будет отслеживать появившиеся альтернативы. К развилке будем относить допустимые пути, которые стали таковыми на данном шаге, но не были на предыдущем.

На C++ этот ИИИ реализуется следующим образом:

void SmartSingleMemRandomAI::doStep( const AIModel& model, Bot* bot ) {
    bot->startMoving();

    auto directions = model.findValidDirections( *bot );

    QVector< Bot::Direction > openedDirections;
    for( Bot::Direction d : directions ) {
        if( !m_memory[ bot->getID() ].contains( d ) ) {
            // Если этого направления не было в прошлый раз, то включаем его в развилку
            openedDirections << d;
        }
    }

    if( std::find( directions.begin(), directions.end(), bot->getDirection() ) != directions.end() ) {
        // Если текущее направление Бота допустимо, то оно тоже входит в развилку
        openedDirections << bot->getDirection();
    } else {
        // Иначе включаем в развилку все допустимые направления
        openedDirections.clear()
        for( Bot::Direction d : directions ) {
            openedDirections << d;
        }
    }

    // Направление на развилке выбирается случайным образом
    bot->setDirection( openedDirections[ rand() % openedDirections.size() ] );

    // Сохраняем в памяти те пути, которые были допустимы на этом шаге и не будут включены в
    // развилку на следующем
    m_memory[ bot->getID() ].clear();
    // Обратное направление исключается из развилки, чтобы Бот не дергался
    // Можете убрать следующую строку и посмотреть, что из этого получится
    m_memory[ bot->getID() ] << Bot::reverseDirection( bot->getDirection() );
    for( Bot::Direction d : directions ) {
        m_memory[ bot->getID() ] << d;
    }
}

void SmartSingleMemRandomAI::reset() {
    m_memory.clear();
}

Этот ИИИ все равно заставляет Ботов ходить вдоль стен. Но теперь зацикливания не происходит. Боты стали гораздо подвижнее и веселее. Если вам требуется алгоритм, моделирующий внешнюю активность без определенной цели, то из рассмотренных здесь вариантов, этот является наилучшим кандидатом.

Еще более интересного поведения для SmartSingleMemRandomAI можно добиться, если учитывать не только прошлое, но и будущее. Для этого в развилку нужно включать еще и те пути, которые сейчас допустимы, но перестанут быть таковыми на следующем шаге. Можете попробовать реализовать такое улучшение самостоятельно.

Заключение

Мы разобрали несколько простых алгоритмов ИИИ. Некоторые из них оказались лучше, другие хуже. Однако что значит лучше или хуже? По каким критериям? Я исходил исключительно из здравого смысла, когда делал вывод, что последний ИИИ выглядит привлекательнее, чем остальные.

Но цель для ИИИ у нас все же была. Она заключалась в том, чтобы обеспечить более или менее естественное поведение Ботов. То есть Боты должны:

  1. Двигаться плавно, а не по загадочным траекториям (конечно, если мы не разрабатываем симулятор алкоголика);
  2. Не упираться в стену;
  3. Не попадать в ловушки (зацикливаясь в одной области).

Таким образом, в дальнейшем мы будем подходить к разработке ИИИ исходя из конкретных целей. В качестве цели для следующей статьи выступит поиск путей в лабиринте

Похожие публикации