Разработка и ромхакинг > Разработка игр
[SMD] ИИ-эксперимент с Русскими шашками
Vlad666:
Я тут уже выкладывал браузерную игру "Русские шашки" против ИИ, написанную нейронкой (сам я в программировании вообще не разбираюсь). Теперь пришла в голову идея написать такую же игру, но только уже для Sega Genesis. Пока сделал базу: сам ИИ, правила и основную информационную индикацию
Что умеет SMD вариант ИИ:
Знает правила шашек: ИИ понимает, как ходят простые шашки и дамки. Он также знает строгое правило — если есть возможность "съесть" фигуру противника, он обязан это сделать (и понимает двойные/тройные прыжки).
Продумывает ходы наперед: ИИ умеет заглядывать в будущее. Он просчитывает игру на 4 шага вперед (учитывая свои действия и ваши возможные ответы). Прежде чем сделать реальный ход на экране, он виртуально расставляет шашки по-разному, сравнивает результаты этих действий и выбирает тот ход, который принесет ему больше всего очков (или нанесет вам наибольший урон). ИИ знает, что дамка в 4 раза ценнее обычной шашки, поэтому старается сохранить своих дамок и быстрее уничтожить ваших.
Стремится в дамки: ИИ запрограммирован так, что ему "выгодно" двигать свои простые шашки как можно дальше вперед, к вашему краю доски, чтобы превратить их в дамок.
Из-за аппаратных ограничений консоли ИИ все же намного слабее браузерного варианта и часто делает глупые ходы. Но играет он все же не плохо для новичка. Меня он обыграл раз 10, а я его только 1. Но, скорее всего, это по причине моего неумения играть в шашки.
Потом попробую сделать алгоритм ИИ быстрее и умнее. Но сначала нужно сделать его быстрее, чтобы освободить процессорное время для новых тактических навыков.
Код ИИ написан нейронкой Gemini 3.5 Flash.
Делаю это игрушку не ради какой-то ее финальной, суперкрутой версии, а ради эксперимента. Мне интересно посмотреть, на что способны нейросети и на что способна Sega Genesis, как можно из ее железа выжать максимум соков.
Выкладываю SMD вариант с исходным кодом в архиве.
ghostdog3:
Спасибо, шашек и правда не хватает на ретро-приставках.
Было бы славно добавить уровни трудности, для таких игр это важно.
Vlad666:
--- Цитата: ghostdog3 от 15 Июнь 2026, 17:00:45 ---Спасибо, шашек и правда не хватает на ретро-приставках.
Было бы славно добавить уровни трудности, для таких игр это важно.
--- Конец цитаты ---
Да, не помешало бы. Потом попробую добавить. Уровень сложности будет регулироваться изменением глубины поиска ИИ. А пока порция обновления алгоритма ИИ, как и обещал.
Сделал ИИ быстрее в более чем 4 раза. Для этого задействовал тяжелую артиллерию в лице Gemini 3.1 Pro.
Вот список основных архитектурных и логических изменений:
1. Переход от полного копирования доски к инкрементальным ходам (структура UndoInfo, функции aiApplyMove и aiUndoMove)
Что дает: Колоссальный прирост производительности ИИ. В оригинале функция alphaBeta создавала полные копии массивов доски (sBoard, sMask) на каждом уровне рекурсии. В обновленном коде ИИ делает ход, сохраняет только минимально необходимые изменения в память (дельту) и после оценки просто "откатывает" их назад. Это сильно экономит такты процессора и оперативную память Sega Genesis.
2. Инкрементальная оценка позиции (currentAiScore и scoreDelta)
Что дает: Ускорение работы древа поиска ИИ. Вместо того чтобы пересчитывать стоимость всех фигур на доске с нуля (функция evaluateBoard) на каждом "листе" дерева вариантов, счетчик очков обновляется на лету: прибавляет очки за съеденные фигуры врага или продвижение пешки и отнимает при потерях.
3. Сортировка ходов (Move Ordering) на базе эвристики (heuristicScore)
Что дает: Значительное повышение эффективности алгоритма Alpha-Beta отсечения. Код теперь сначала собирает все доступные ходы в массив AIMove, присваивает им базовый вес (взятие или превращение в дамку ценятся выше) и сортирует их. Рассматривая сначала "лучшие" ходы, алгоритм быстрее отсекает заведомо проигрышные ветки вычислений (pruning), позволяя ИИ думать быстрее или "глубже" при тех же затратах времени.
4. Позиционная оценка пешек (массивы pawnScoresBlack и pawnScoresWhite)
Что дает: Более умное поведение ИИ. Теперь ИИ понимает, что пешка, продвинутая ближе к краю противника (ближе к превращению в дамку), стоит дороже. Это мотивирует компьютер активнее двигать фигуры вперед, а не просто держать их на базе.
5. Замена типов данных int и int8_t на аппаратно-зависимый s16
Что дает: Оптимизация под целевое "железо". Процессор Motorola 68000 наиболее эффективно оперирует 16-битными числами. Использование s16 вместо 32-битного int и 8-битного int8_t (который требует дополнительных команд для расширения знака) ускоряет вычисления на уровне ассемблерных инструкций.
6. Оптимизация циклов перебора клеток доски (startX = (y & 1) ? 0 : 1; x += 2)
Что дает: Сокращение количества итераций в циклах ровно в 2 раза. Поскольку шашки могут находиться только на черных клетках, обновленный алгоритм сразу перепрыгивает белые клетки, игнорируя их при генерации ходов, оценке позиций и поиске обязательных взятий.
7. Замена операции взятия остатка от деления % 2 на побитовое И & 1
Что дает: Микрооптимизация работы процессора. Побитовые операции выполняются процессором гораздо быстрее, чем математические операции деления или взятия остатка.
8. Выравнивание памяти в массивах (__attribute__((aligned(4))))
Что дает: Ускоренный доступ к оперативной памяти. Указание компилятору выровнять массивы board и capturedMask по 4-байтовой границе делает чтение и запись данных процессором более оптимальными, избегая штрафов за невыровненный доступ к памяти.
----------
Благодаря всем этим оптимизациям ИИ думает, например, вместо 17 секунд всего 4 секунды. Это позволило увеличить глубину поиска с 4 до 5 ходов. Но даже при увеличении глубины поиска ИИ думает не 17, а 10 секунд.
Потом попробую научить его некоторым тактическим приемам, чтобы он не просто был умнее в плане глубины поиска хороших ходов, но и умел хитрить.
ROM и исходный код в архиве.
Vlad666:
Основные обновления в новой версии и их преимущества:
1. Переход на битборды (Bitboards): Внедрена структура BoardState с использованием 32-битных чисел (поля WP, BP, WK, BK) для просчета ходов ИИ вместо двумерного массива.
Что дает: Радикальное ускорение генерации ходов и работы ИИ благодаря быстрым побитовым операциям.
2. Форсированный поиск (Quiescence Search): Добавлена функция дорасчета цепочек взятий (fastQuiescence).
Что дает: Устраняет "эффект горизонта". Теперь ИИ не делает глупых ходов только потому, что у него закончилась глубина просчета прямо посреди серии рубок.
3. Улучшенная оценка позиций (Dynamic Evaluation): Добавлен анализ позиционных преимуществ (evaluateDynamic), оценка проходных шашек (passedMask), контроль центра (centerPenalty) и новые матрицы весов для шашек и дамок.
Что дает: ИИ стал играть стратегически умнее, оценивая позицию на доске, а не просто подсчитывая количество своих и чужих фигур.
4. Оптимизация рекурсии (Отказ от Undo): Убрана сложная структура UndoInfo и функции отката ходов (aiUndoMove).
Что дает: Упрощение и ускорение кода. Теперь новое состояние доски просто копируется и передается на следующий уровень глубины поиска (BoardState nextBs = bs).
5. Интерактивное главное меню: Добавлен экран showMenu().
Что дает: Игрок может перед стартом настроить сложность: выбрать глубину поиска (Depth Search) и лимит форсированного поиска (Quiescence Search). Чем выше значения, тем умнее ИИ, но и медленнее. Теперь можно выставить значение Depth Search до 6 ходов, а не ограничиваться 5, как в предыдущей версии. При глубине основного поиска в 6 ходов и форсированного поиска в 12 ходов ИИ думает примерно 1 минуту.
6. Правило ничьей: Внедрен счетчик ходов без взятий и движения простых шашек (drawMovesCounter, MAX_DRAW_MOVES).
Что дает: Игра корректно завершается статусом "DRAW" (Ничья), предотвращая бесконечную партию, если у обоих игроков остались только дамки.
----------
Алгоритм ИИ стал в разы быстрее, но при этом думает дольше из-за обновления из третьего пункта. Даже если отключить Quiescence Search, компьютер все равно будет делать ход примерно 11 секунд вместо 10 (при глубине основного поиска в 5 ходов). И если бы не крутая оптимизация из первого пункта, то он думал бы еще дольше.
Потом попробую сделать ИИ еще быстрее. Интересно посмотреть справится ли нейронка с такой задачей. А с его мозгами пока хватит, иначе процессор консоли не справится :biggrin:.
ROM и исходный код в архиве. Из-за сложности алгоритмов игру лучше запускать на оригинальной консоли или на эмуляторе BlastEm, иначе могут возникнуть неочевидные ошибки в действиях ИИ.
ww:
выложи хоть пару скриншотов штоль...
Vlad666:
Очередное обновление. На этот раз попросил нейронку сделать графику.
Ultimate Genesis Edition придумала нейронка :biggrin:.
Guyver(X.B.M.):
А обратные шашки будут? Было бы прикольно, редко кто их делает... И можно хотя бы 1 простейший звук сделать...
Vlad666:
--- Цитата: Guyver(X.B.M.) от 16 Июнь 2026, 18:21:07 ---А обратные шашки будут? Было бы прикольно, редко кто их делает... И можно хотя бы 1 простейший звук сделать...
--- Конец цитаты ---
Посмотрим. Может быть и добавлю. А на SMD, если я не ошибаюсь, нет даже обычных шашек, а уж про русский вариант и говорить не стоит.
ghostdog3:
--- Цитата: Vlad666 от 16 Июнь 2026, 18:57:02 ---А на SMD, если я не ошибаюсь, нет даже обычных шашек
--- Конец цитаты ---
Что вы понимаете под обычными? Международные (поле 10*10 + немного другие правила), английские (назад не бьют; дамка ходит и бьёт во все стороны, но на одно поле), бразильские/польские (поле 8*8, по правилам международных)?
Тоже не встречал на SMD шашек, на NES видел китайские шашки (доска в форме звезды).
--- Цитата: Vlad666 от 16 Июнь 2026, 14:45:27 ---На этот раз попросил нейронку сделать графику.
--- Конец цитаты ---
Над дизайном и цветами бы ещё поработать.
Было бы славно добавить на шашки круги, как у Агафонова (Agafonov's Draughts Club).
Vlad666:
--- Цитата: ghostdog3 от 16 Июнь 2026, 20:26:13 ---Что вы понимаете под обычными?
--- Конец цитаты ---
Я имел ввиду шашки с обычными правилами для каждого вида, а не экзотика.
Добавлено позже:
Еще одно обновление.
Что нового:
1. Возможность играть за черных.
2. Теперь два режима: классика и реверс (поддавки).
3. Улучшение эвристики ИИ: Функция fastQuiescence теперь сразу учитывает динамическую оценку позиции (evaluateDynamic), а в самой evaluateDynamic упрощен и исправлен расчет штрафов/бонусов за контроль центра в эндшпиле.
HayaoYokogawa:
Осталось еще режим игры "Чапаев" добавить и тогда будет круто. :thumbup:
Vlad666:
--- Цитата: HayaoYokogawa от 17 Июнь 2026, 13:11:53 ---Осталось еще режим игры "Чапаев" добавить и тогда будет круто. :thumbup:
--- Конец цитаты ---
Это что за режим такой :biggrin:?
SeregaZ:
это бильярд-режим для шашек :)
Vlad666:
Нейронка выдала еще одно обновление.
Что нового:
1. До этого игрок и компьютер во время множественного взятия дамкой могли при рубке первой шашки проскочить пересекающую диагональ, на которой стоит доступная для рубки вторая шашка противника. Это является нарушением правил Русских шашек. Теперь в движок добавлена строгая проверка: если на линии приземления есть возможность продолжить бой, игра просто не позволит выбрать тупиковую клетку. Фильтр внедрен на уровне базового генератора ходов, поэтому поисковые алгоритмы ИИ теперь тоже учитывают это правило и строят свои ловушки абсолютно честно.
2. Добавил анимацию движения шашек, чтобы они не перескакивали от клетки к клетке моментально.
3. И САМОЕ ГЛАВНОЕ: Gemini 3.1 Pro переписал базовую функцию поиска фигур на доске (в битбордах): полностью отказался от тяжелой математики с 32-битным умножением и длинными битовыми сдвигами в пользу простой предвычисленной таблицы (LUT) на 256 байт.
Вот так код выглядел до:
--- Код: ---const u8 multiplyDeBruijnBitPosition[32] = {
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
static inline u8 getLSB(u32 v) {
return multiplyDeBruijnBitPosition[((u32)((v & -v) * 0x077CB531U)) >> 27];
}
--- Конец кода ---
Теперь он выглядит так:
--- Код: ---// Таблица: для каждого байта (от 0 до 255) хранит индекс самого младшего установленного бита (0-7).
// Для 0 значение неважно, так как getLSB вызывается только для v != 0.
static const u8 LSB_TABLE_8BIT[256] = {
0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};
static inline u8 getLSB(u32 v) {
// Разбиваем 32-битное число на части и ищем первый ненулевой байт, начиная с младшего.
// Это избавляет процессор от необходимости делать (v & -v) и умножение.
u32 lo = v & 0xFFFF;
if (lo) {
if (lo & 0xFF) {
return LSB_TABLE_8BIT[lo & 0xFF];
} else {
return 8 + LSB_TABLE_8BIT[lo >> 8];
}
} else {
u32 hi = v >> 16;
if (hi & 0xFF) {
return 16 + LSB_TABLE_8BIT[hi & 0xFF];
} else {
return 24 + LSB_TABLE_8BIT[hi >> 8];
}
}
}
--- Конец кода ---
Я ничего не понял, но это работает настолько круто, что до обновления ИИ думал, например, 12 секунд, то теперь он думает 7 секунд на глубине основного поиска в 5 ходов и на глубине форсированного поиска в 12 ходов. А если отключить форсированный поиск, то ИИ будет думать всего 4 секунды. Я в шоке. Нейросеть продолжает меня удивлять. Потом попробую попросить нейронку ускорить ИИ еще больше. Сможет ли она что-нибудь придумать? Если да, то можно будет смело увеличивать максимальную глубину основного поиска до 7 ходов, а не до 6, как сейчас.
Кстати, интересно, можно ли с помощью нейросети так же круто оптимизировать уже существующие игры, страдающие тормозами? Если она такой сложный алгоритм может настолько круто ускорять для слабого процессора раз за разом, то почему бы ей не ускорить обычную игрушку с простейшей логикой?
Dyons:
--- Цитата: Vlad666 от 17 Июнь 2026, 15:07:35 ---Кстати, интересно, можно ли с помощью нейросети так же круто оптимизировать уже существующие игры, страдающие тормозами?
--- Конец цитаты ---
Ну вперед, оптимизируй нам SotC для ПС2 :lol:
dusha6613:
--- Цитата: Vlad666 от 17 Июнь 2026, 15:07:35 ---почему бы ей не ускорить обычную игрушку с простейшей логикой?
--- Конец цитаты ---
Contra force.
Беларус:
--- Цитата: Vlad666 от 17 Июнь 2026, 15:07:35 ---можно ли с помощью нейросети так же круто оптимизировать уже существующие игры, страдающие тормозами?
--- Конец цитаты ---
Вряд ли. Для распространённых игр типа шахмат и шашек человечество придумало кучу разных оптимизацый и все они в сети, а для других игр нет - у каждой своя уникальная ситуацыя.
Vlad666:
Есть ли какая-нибудь тормозная игра на Genesis, которая разобрана и ее можно собрать в SGDK?
Werton:
--- Цитата: Vlad666 от 17 Июнь 2026, 19:59:16 ---Есть ли какая-нибудь тормозная игра на Genesis, которая разобрана и ее можно собрать в SGDK?
--- Конец цитаты ---
"Собрать" в sgdk ты можешь только то, что написано на sgdk, и если у тебя есть исходники. И как ты догадываешься, ни одна из лицензионных игр не написана на sgdk, да и доступных ассемблерных исходников официальных игр наверное можно по пальцам одной руки пересчитать. Если говорить о играх написаных на sgdk, то индюки тоже не спешат делиться исходниками своих игр, а те что доступны это просто мало кому нужные демки, нет никакого смысла их оптимизировать.
Vlad666:
--- Цитата: Werton от 18 Июнь 2026, 01:53:24 ---...нет никакого смысла их оптимизировать.
--- Конец цитаты ---
Чисто ради интереса.
Навигация
Перейти к полной версии