Форум программистов, компьютерный форум CyberForum.ru

Слишком медленный алгоритм искусственного интеллекта игры Балда - Android

Восстановить пароль Регистрация
 
Paket236
2 / 2 / 0
Регистрация: 16.08.2013
Сообщений: 48
03.11.2016, 18:48     Слишком медленный алгоритм искусственного интеллекта игры Балда #1
Здравствуйте!
Столкнулся с одной сложностью при создании искусственного интеллекта (ИИ) для своей игры Балда. Сначала опишу алгоритм словами, затем приведу код.

Итак, мой алгоритм ИИ можно разделить на 4 этапа (попытаюсь описать максимально понятно):
• [1] Рекурсивно анализируется каждая клетка до заданной глубины. Результат (буква/пустая клетка, координаты и глубина рекурсии соответственно) сохраняется в переменные.
• [2] Из полученного результата (отдельные буквы/пустые клетки) на основе глубины рекурсии формируются последовательности букв/пустых клеток и сохраняются в новые переменные, предварительно отсекаются последовательности с дублированными клетками, с 2-мя и более пустыми клетками и без пустых клеток (т.е. проходят только с одной пустой клеткой).
• [3] В каждой полученной последовательности пустые клетки заменяются на каждую букву алфавита и результат сравнивается с каждым словом словаря (т.е. 3 цикла). Совпавшие слова (и другие данные) записываются в новые переменные.
• [4] Из совпавших слов выбирается 1 слово.

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

Проблема же заключается в том, что на эмуляторе Genymotion данный алгоритм выполняется около 30 секунд, на реальном устройстве - больше минуты. Это слишком долго. Если же проверить на чистой Java, то выполняется быстро - 0,8 секунд.

Возникает вопрос: что нужно сделать, чтобы на Android-устройствах или -эмуляторах выполнялось хотя бы за 1-2 секунды? Ведь в приложениях-аналогах ИИ работает почти мгновенно. Пока что я без понятия, что в алгоритме можно улучшить.

Теперь приведу код. Т.к. он большой (не помещается в посту) - прикрепил файлами.
Вложения
Тип файла: zip Java.zip (44.1 Кб, 2 просмотров)
Тип файла: zip Android.zip (44.7 Кб, 1 просмотров)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2016, 18:48     Слишком медленный алгоритм искусственного интеллекта игры Балда
Посмотрите здесь:

Android Оптимизация приложения. Слишком часто вызывается GC
Android Ищу сотоварища для разработки не слишком сложного приложения
Написание игры Android
Android Разработка игры
Android Sdk занимает слишком много места
Android Медленный XmlPullParser
Android IntelliJ IDEA. Слишком умный редактор
Посоветуйте монетизацию игры Android

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Паблито
не спать!
1786 / 1520 / 472
Регистрация: 12.05.2014
Сообщений: 5,552
Завершенные тесты: 1
03.11.2016, 18:52     Слишком медленный алгоритм искусственного интеллекта игры Балда #2
много букв, ниасилил
к тому же надо что-то качать

раскидать логи по методам (или воспользоваться профайлером) и отловить какой участок кода выполняется долго - вот его можно сюда и показать, а не два архива
Paket236
2 / 2 / 0
Регистрация: 16.08.2013
Сообщений: 48
03.11.2016, 19:20  [ТС]     Слишком медленный алгоритм искусственного интеллекта игры Балда #3
Паблито, самый долгий участок, который несравнимо дольше других выполняется, находится на 3-ем этапе (который я описал выше). Привожу код:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
        StringBuilder sb = new StringBuilder();
        String[] русскийАлфавит = new String[] {"А", "Б", "В", "Г", "Д", "Е", "Ж", "З", "И", "Й", "К",
                                                "Л", "М", "Н", "О", "П", "Р", "С", "Т", "У", "Ф", "Х",
                                                "Ц", "Ч", "Ш", "Щ", "Ъ", "Ы", "Ь", "Э", "Ю", "Я"};
        int pos = -1;
        // перебираем "слова"(последовательности) и определяем позицию пустой клетки
        for(int i=0; i<alСлова.size(); ++i) {
            pos = alСлова.get(i).indexOf(" ");
            sb = new StringBuilder(alСлова.get(i));
            // заполняем пустую клетку буквами из алфавита
            for(int j=0; j<русскийАлфавит.length; ++j) {
                sb.replace(pos, pos+1, русскийАлфавит[j]);
                // сравниваем слово с заполненной буквой со словами из словаря
                for(int k=0; k<словарь.length; ++k) {
                    // добавляем найденное в словаре слово
                    if(sb.toString().equals(словарь[k]) && отсутствуетВСпискеИспользованных(sb.toString())) {
                        alКоорд1ЗаполненныхБукв.add(alКоорд1ПустыхКлеток.get(i));
                        alКоорд2ЗаполненныхБукв.add(alКоорд2ПустыхКлеток.get(i));
                        alЗаполненныеБуквы.add(русскийАлфавит[j]);
                        alНайдСлова.add(sb.toString());
                        alКоордНайдСлова.add(alКоордСлова.get(i));
                    }
                }
            }
        }
Но мне кажется, здесь вряд ли что-то можно оптимизировать, хотя кто знает...

upd: в словаре 11880 слов.

Добавлено через 11 минут
upd2: если закомментировать внутри if() - по скорости ничего не изменится. А вот если сам if(), т.е. не сравнивать со словарём - то скорость сразу становится приемлемой, около секунды.
vanchous
1 / 0 / 0
Регистрация: 06.11.2016
Сообщений: 22
06.11.2016, 03:12     Слишком медленный алгоритм искусственного интеллекта игры Балда #4
может не стоит sb.toString() 24к раз вызывать?
Rube
904 / 552 / 86
Регистрация: 13.02.2014
Сообщений: 2,040
09.11.2016, 07:22     Слишком медленный алгоритм искусственного интеллекта игры Балда #5
Да тут как ни крути долго ждать. Логику надо другую, нейросети сейчас в тренде.
ExFau$t
55 / 55 / 4
Регистрация: 08.05.2012
Сообщений: 448
09.11.2016, 11:55     Слишком медленный алгоритм искусственного интеллекта игры Балда #6
Алгоритм и правда никакой, в лоб искать тоже уметь надо. Я, конечно, не шибко понял, что там происходит, но 1) если идёт поиск в чём -то большом, и if выполняется только однажды, зачем проходить потом ещё 100500 раз, используй break/continue. 2) я не знаю, что у тебя в словаре, но почти наверняка его можно упорядочить или разбить на части. 3) опять же для меня загадка зачем проходить словарь в трёх циклах ("добавляем найденное в словаре слово"), ну и добавь всё сразу в одном цикле 1 раз.
Yandex
Объявления
09.11.2016, 11:55     Слишком медленный алгоритм искусственного интеллекта игры Балда
Ответ Создать тему
Опции темы

Текущее время: 06:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru