Комментарии 37
Добро пожаловать в безжалостный мир алгоритмической сложности :)
При вашей скорости 10^20 комбинаций будут обсчитываться порядка 13 миллионов лет. Я бы не рассчитывал дожить до момента, когда это можно будет сделать в разумное время на машине, доступной простому обывателю. Судя по тому, что игра до сих пор не просчитана полностью, это даже на кластере невозможно сделать.
Разве что случится революция в виде квантовых вычислений, но до этого момента можно смело изучать нейронные сети.
При вашей скорости 10^20 комбинаций будут обсчитываться порядка 13 миллионов лет. Я бы не рассчитывал дожить до момента, когда это можно будет сделать в разумное время на машине, доступной простому обывателю. Судя по тому, что игра до сих пор не просчитана полностью, это даже на кластере невозможно сделать.
Разве что случится революция в виде квантовых вычислений, но до этого момента можно смело изучать нейронные сети.
Пора уже поговорить об этом!
Вообще говоря, не все позиции достижимы. Так что шансы на перебор есть. Хотя оценки допустимых позиций я не встречал.
Классические шашки были решены слабо ещё в 2007 году. При правильной игре обоих игроков — ничья. Также это доказательство гарантирует, что любую партию можно свести к ничьей, к сожалению даже выигрышную для кого-то.
Считать ли чекерс, достаточно урезанную комбинаторно версию шашек, классической — это вопрос терминологии. А вот то, что решена была одна-единственная позиция, а именно начальная — это как раз то, что отличает решение в слабом смысле от полного.
Ни в русских, ни тем паче в международных шашках, комбинаторного решения пока не видно даже на горизонте.
Нет, я понимаю, что за диском и памятью давно не гонятся, но шашки размером «лишь» 60 МБ?
Модельки, анимации, менюшки, дебюты…
Для шахматных программ гигабайты — это нормально :)
И при этом они рассчитывают очень мало (по сравнению с тем что хочет автор).
И при этом они рассчитывают очень мало (по сравнению с тем что хочет автор).
Ассемблерная версия Стокфиша весит порядка 100-150 КИЛОбайт. Это без интерфейса, понятное дело. Но вся логика шахмат туда помещается, и играет на 3200 Эло.
3D шутер .kkrieger — 96kb (с интерфейсом, понятное дело).
Но я об базе данных эндшпиля, с некоторыми программами они идут вместе, некоторые их генерируют (загружая CPU на часы работы), а некоторые не используют.
Но я об базе данных эндшпиля, с некоторыми программами они идут вместе, некоторые их генерируют (загружая CPU на часы работы), а некоторые не используют.
Вопреки расхожему мнению, основной источник силы программ — не дебютные и эндшпильные базы данных, а чрезвычайно оптимизированный расчёт вариантов + хорошо настроенная оценочная функция. Дебюты и эндшпили в сумме дадут порядка 50-100 пунктов Эло. Может даже и меньше. У супергроссмейстеров вроде Накамуры программы выигрывают вообще безо всякого дебюта, давая из начальной позиции фору в два хода.
Тоже ради интереса писал шашки на втором курсе — правда, подход был менее серьёзным. Как оказалось, алгоритм, который просчитывает вперёд на 3-4 хода, уже играет лучше меня. (4 моих и 4 хода программы, при съедении кого-нибудь глубина перебора конкретной ветки увеличивалась на 1).
Вы бы сделали на основе своего алгоритма шашки, которые будут просчитывать ходы на столько глубоко, насколько позволяет таймаут на ход, и поиграли с ними. А потом рассказали на сколько он лучше/хуже других.
Это несерьезно.
Должно быть предобучение.
Человек знает что та или иная ситуация вигрышная или проигрышная. И считает «только» то что не знает.
Опять же — считают не только таймаут, а и время когда думает оппонент, потом просто очищая уже невозможные ветки.
Развивать надо в сторону «топологии», какое-то сходство, классификация и т.п., чтобы схожие ситуации повторно не считать. Из банального это отзеркаливание «черные меняем на белые», аналогично поменяв и ход.
Должно быть предобучение.
Человек знает что та или иная ситуация вигрышная или проигрышная. И считает «только» то что не знает.
Опять же — считают не только таймаут, а и время когда думает оппонент, потом просто очищая уже невозможные ветки.
Развивать надо в сторону «топологии», какое-то сходство, классификация и т.п., чтобы схожие ситуации повторно не считать. Из банального это отзеркаливание «черные меняем на белые», аналогично поменяв и ход.
Я в поиске тактики, которая на первый взгляд лишь проигрышная и лишь спустя десяток ходов, а может несколько десятков, ведёт к победе. Или ведёт хотя бы к сложной для противника ничье.
Например, все дебюты основываются на равенстве количества шашек у игроков. Так, просто, проще играть. Но это же не единственно верный путь.
А сравнивать программу с другими… есть ли смысл?
Например, все дебюты основываются на равенстве количества шашек у игроков. Так, просто, проще играть. Но это же не единственно верный путь.
А сравнивать программу с другими… есть ли смысл?
Если вы ставите в качестве сверхзадачи полный просчёт шашечной игры, логично двигаться с конца — от позиций с минимальным числом шашек на доске вверх по дереву. Создатели эндшпильных баз так дошли сейчас, кажется, до 8-9 фигурных позиций. Осталось всего ничего: добавить ещё 15-16 шашек, причём добавление каждой следующей увеличивает сложность по экспоненте :)
Да, и глагол "выиграть" в значении "победить" требует предлога "у". Победил программу, но выиграл У программы.
А так статья захватывающая! Удачи!
Спортивная игра «Шашки» является одной из игр человечества, которые компьютер ещё не просчитал полностьюВыше привели ссылку, программа Chinook не может проиграть (если верить создателям). А значит, не может и выиграть у соперника максимальной силы. Поэтому качество непроигрышного кода можно оценивать только исходя из особенностей неидеального соперника типа психология, максимальная глубина=8, дамка=3пешки всегда и т.д.
Для улучшения перебора можно обратить внимание на шахматные эндшпильные таблицы (формат хранения, учет симметрии) и на топовые шахматные движки с открытым кодом (код российского производства gull3 состоит из единственного файла cpp 8к строк). Можно обратить так же внимание на библиотеку stl и структуры данных которые там реализованы, сравнить со своими.
А чтобы сделать просто сильный движок и проверить на нем корректность перебора, дополнительно достаточно добавить нормальную оценочную функцию позиций для альфа-бетты, а не просто суммарное качество.
Возможно хватит и трёх битбордов:
- белые фигуры
- черные фигуры
- дамки
Из 8 сочетаний битов 3 являются некорректными. При этом в ячейке А1 не может находится черная обычная фигура.
Признак хода можно хранить в виде корректного / некорректного сочетания битов в ячейке А1: f = b ^ (!w & d)
Функция возвращает единицу для некорректного сочетания.
В таком варианте смена хода делается сменой первого бита списка черных фигур.
Получение корректного сочетания — применить XOR первого бита доски черных фигур и результата функции, что не требует ветвлений
Таким образом полное состояние игры укладывается в 12 байт, который можно хранить в файле напрямую в бинарном виде, не занимаясь переконвертацией в строковое представление и обратно.
Здорово! Действительно, можно использовать 12 байт. Спасибо!
Десять лет назад на шахматном форуме было достаточно содержательное обсуждение программирования шашек. Вдруг пригодится…
12 байт много.
4 байта на «есть ли в этой ячейке хоть какая-то шашка».
шашек не более 16. На каждую из 16 по два бита — какая именно шашка.
Это 8 байт. При этом у нас дофига «лишнего места» остается под метаданные — чей ход можно определять цветом 16-й шашки. Если у нас меньше 16-ти шашек на доске, то это поле неопределено, и можно спокойно использовать. Если шашек таки 16, то ее цвет очевиден из цветов остальных.
Если на доске нет ни одной дамки, то повторы невозможны. Если есть хоть одна дамка, то кто-то был съеден (проверить математически, но чисто интуитивно так кажется), а значит есть место и под колво повторов. Наверняка можно лучше «утрамбовать». Но так оно еще остается «читаемым». Дальше мне только Хаффман в голову приходит, а там и сложность сильно возрастет и на индексах за счет переменной длины — больше можем потерять.
4 байта на «есть ли в этой ячейке хоть какая-то шашка».
шашек не более 16. На каждую из 16 по два бита — какая именно шашка.
Это 8 байт. При этом у нас дофига «лишнего места» остается под метаданные — чей ход можно определять цветом 16-й шашки. Если у нас меньше 16-ти шашек на доске, то это поле неопределено, и можно спокойно использовать. Если шашек таки 16, то ее цвет очевиден из цветов остальных.
Если на доске нет ни одной дамки, то повторы невозможны. Если есть хоть одна дамка, то кто-то был съеден (проверить математически, но чисто интуитивно так кажется), а значит есть место и под колво повторов. Наверняка можно лучше «утрамбовать». Но так оно еще остается «читаемым». Дальше мне только Хаффман в голову приходит, а там и сложность сильно возрастет и на индексах за счет переменной длины — больше можем потерять.
Стоп, стоп.
1) Стартовая позиция 12 белых, 12 чёрных. *шашек не более 32
2) Как в 2 бита занести следующие 5 состояний?
белая шашка, чёрная шашка, белая дамка, чёрная дамка, шашка отсутствует.
Я не понимаю, что ты пытаешься донести в последнем абзаце. Можешь по подробней описать?
1) Стартовая позиция 12 белых, 12 чёрных. *шашек не более 32
2) Как в 2 бита занести следующие 5 состояний?
белая шашка, чёрная шашка, белая дамка, чёрная дамка, шашка отсутствует.
Я не понимаю, что ты пытаешься донести в последнем абзаце. Можешь по подробней описать?
Черт, три ряда а не два. Вот что значит что нельзя нести в паблик мысли появившиеся в момент просыпания или засыпания))
Смотри.
У нас 8*4 клетки на поле.
Каждой клетке соответствует один бит. Это 4 байта.
Если в ячейке есть шашка (любая, черная, белая, дамка, не важно) — у нас стоит единичка.
Если ничего нет, то нолик.
Максимальное количество единичек — 24.
Нумеруем эти единички (и только их, нули не нумеруем) от нуля до 24.
Т.е. каждую шашку на поле вне зависимости от того какого она цвета и является ли она дамкой — нумеруем. Каждой шашке соответствует ячейка памяти в два бита.
Уже в этой ячейке мы определяем что это за шашка — черная, белая, черная шашка, белая шашка.
Четыре варианта. Пятый вариант не нужен. Пустые не попадут в наш список.
24*2 = 6 байт. Тут я ошибся, да. Думал что 4. У нас 4 бита на определение занятых ячеек и 6 байт на определение того что в этих занятых находится. Итого 10 байт.
Думаю после этого объяснения остальной текст будет понятен.
Вообще есть идеи как запихнуть еще плотнее. Думаю в 7 байт уложусь, может еще меньше, но там будет еще более закручено. Пробовать или сложность кода не оправдает экономию памяти?
Смотри.
У нас 8*4 клетки на поле.
Каждой клетке соответствует один бит. Это 4 байта.
Если в ячейке есть шашка (любая, черная, белая, дамка, не важно) — у нас стоит единичка.
Если ничего нет, то нолик.
Максимальное количество единичек — 24.
Нумеруем эти единички (и только их, нули не нумеруем) от нуля до 24.
Т.е. каждую шашку на поле вне зависимости от того какого она цвета и является ли она дамкой — нумеруем. Каждой шашке соответствует ячейка памяти в два бита.
Уже в этой ячейке мы определяем что это за шашка — черная, белая, черная шашка, белая шашка.
Четыре варианта. Пятый вариант не нужен. Пустые не попадут в наш список.
24*2 = 6 байт. Тут я ошибся, да. Думал что 4. У нас 4 бита на определение занятых ячеек и 6 байт на определение того что в этих занятых находится. Итого 10 байт.
Думаю после этого объяснения остальной текст будет понятен.
Вообще есть идеи как запихнуть еще плотнее. Думаю в 7 байт уложусь, может еще меньше, но там будет еще более закручено. Пробовать или сложность кода не оправдает экономию памяти?
Я смог запихнуть в 9 байт, но не влезла информация, о том, чей сейчас ход.
Также можно хранить состояния не отдельно, а цепочками, тогда можно кодировать не само состояние, а ход, приводящий в него из предыдущего: 4 бита на выбор шагающей шашки и от 1 до 4 бит на выбор варианта хода, составные ходы хранить в виде цепочки выборов хода. Тогда на один ход уйдет от 1 до 7 байт (наихудший случай: дамка за один ход рубит все 12 шашек)
Еще можно прикрутить арифметическое кодирование с динамическими вероятностями (учесть, что: количество шашек не увеличивается, меняется редко, количество дамок за ход не увеличивается больше, чем на одну, и т.д.)
Но при подобном хранении сильно просядет скорость перебора состояний.
Также можно хранить состояния не отдельно, а цепочками, тогда можно кодировать не само состояние, а ход, приводящий в него из предыдущего: 4 бита на выбор шагающей шашки и от 1 до 4 бит на выбор варианта хода, составные ходы хранить в виде цепочки выборов хода. Тогда на один ход уйдет от 1 до 7 байт (наихудший случай: дамка за один ход рубит все 12 шашек)
Еще можно прикрутить арифметическое кодирование с динамическими вероятностями (учесть, что: количество шашек не увеличивается, меняется редко, количество дамок за ход не увеличивается больше, чем на одну, и т.д.)
Но при подобном хранении сильно просядет скорость перебора состояний.
Дамка за один ход никак не сможет срубить 12 шашек, потому что не получится найти такую цепочку ходов, чтобы на поле была дамка одного цвета, и осталось 12 шашек другого цвета.
Хотя могу ошибаться. Я прикидывал только вопрос «не сбито ни одной шашки, а уже дамка», такое точно не возможно, а так чтобы не сбить вражеского ни одного, то надо считать. Но сомневаюсь.
Вообще если в лоб пробовать улучшать, без хитрых манипуляций, так чтобы колво бит на позицию было целым и фиксированным, то я бы попробовал посчитать сколько максимум шашек (всего, обоих цветов, включая дамку) может быть на поле при условии что есть хоть одна дамка. ИМХО это не сложно будет пересчелкать перебором. Обрубаем все ветвления где уже есть дамка или колво фигур стало равно уже известному нам максимуму. Если мои ощущения верны, то формат будет относительно простой — 4 байта сетка «где есть шашки».
Дальше если шашек больше чем наше «максимальное колво шашек при дамке», то у нас только таблица цветов наших шашек. Если меньше или равно, то таблица цветов и таблица «дамка/мужЫк». Допустим (было бы круто) максимум шашек на столе при дамке — 12, т.е. половина должна быть съедена чтобы появилась дамка. Тогда длина записи будет 7 байт. При 16-ти это будет 8 байт.
Хотя могу ошибаться. Я прикидывал только вопрос «не сбито ни одной шашки, а уже дамка», такое точно не возможно, а так чтобы не сбить вражеского ни одного, то надо считать. Но сомневаюсь.
Вообще если в лоб пробовать улучшать, без хитрых манипуляций, так чтобы колво бит на позицию было целым и фиксированным, то я бы попробовал посчитать сколько максимум шашек (всего, обоих цветов, включая дамку) может быть на поле при условии что есть хоть одна дамка. ИМХО это не сложно будет пересчелкать перебором. Обрубаем все ветвления где уже есть дамка или колво фигур стало равно уже известному нам максимуму. Если мои ощущения верны, то формат будет относительно простой — 4 байта сетка «где есть шашки».
Дальше если шашек больше чем наше «максимальное колво шашек при дамке», то у нас только таблица цветов наших шашек. Если меньше или равно, то таблица цветов и таблица «дамка/мужЫк». Допустим (было бы круто) максимум шашек на столе при дамке — 12, т.е. половина должна быть съедена чтобы появилась дамка. Тогда длина записи будет 7 байт. При 16-ти это будет 8 байт.
Как ты запихнул в 9 байт? Можешь расписать?
Пусть белые начинают игру снизу и нижняя линия имеет номер 1.
Тогда, дойдя до линии 8 белая шашка сразу становится дамкой.
Поэтому для клетки на 8 линии может быть только 4 состояния: пусто, белая дамка, черная шашка, черная дамка. Их можно закодировать 2 битами. На всю 8 линию уйдет один байт.
Для 1 линии симметрично один байт.
Для клеток линий 2-7 есть 5 возможных состояний: П, БШ, БД, ЧШ, ЧД.
Три клетки имеют 125 возможных состояний, что кодируется 7 битами (128 вариантов, 3 не используются)
На линиях 2-7 ровно 24 клетки (3*8), которые кодируются 7*8 битами или 7 байтами.
Итого 1 байт на линию 1 + 7 байт на линии 2-7 + 1 байт на линию 8 = 9 байт.
Тогда, дойдя до линии 8 белая шашка сразу становится дамкой.
Поэтому для клетки на 8 линии может быть только 4 состояния: пусто, белая дамка, черная шашка, черная дамка. Их можно закодировать 2 битами. На всю 8 линию уйдет один байт.
Для 1 линии симметрично один байт.
Для клеток линий 2-7 есть 5 возможных состояний: П, БШ, БД, ЧШ, ЧД.
Три клетки имеют 125 возможных состояний, что кодируется 7 битами (128 вариантов, 3 не используются)
На линиях 2-7 ровно 24 клетки (3*8), которые кодируются 7*8 битами или 7 байтами.
Итого 1 байт на линию 1 + 7 байт на линии 2-7 + 1 байт на линию 8 = 9 байт.
Так же можно битовые поля хранить отдельно, а состояние сделать в виде индексов.
Для большей экономии поле для черных шашек поворачивать на 180.
Тогда на начальное состояние понадобится:
4 байта на пустое поле + 4 байта на начальное состояние белых шашек + 2 байта на индексы (пятибитные) = 10 байт.
Есть 7 вариантов первого хода, тогда на хранение начального и 7 вариантов:
4 байта на пустое поле + 4 байта на начальное состояние белых шашек + 4 байта * 7 вариантов + 2 байта * 8 хранимых состояний = 52 байта (примерно 7 байт на состояние)
Черные тоже имеют 7 вариантов первого хода.
Тогда после первого хода черных будет уже 49 возможных состояний, но количество хранимых досок не изменится, поэтому:
9*4 байтов на доски + 57 * 2 байтов на индексы = 150 байт (около 3 байт на состояние)
Дальше придется использовать трёх- и 4-х-байтовые состояния, но все равно выигрыш будет существенным.
Для большей экономии поле для черных шашек поворачивать на 180.
Тогда на начальное состояние понадобится:
4 байта на пустое поле + 4 байта на начальное состояние белых шашек + 2 байта на индексы (пятибитные) = 10 байт.
Есть 7 вариантов первого хода, тогда на хранение начального и 7 вариантов:
4 байта на пустое поле + 4 байта на начальное состояние белых шашек + 4 байта * 7 вариантов + 2 байта * 8 хранимых состояний = 52 байта (примерно 7 байт на состояние)
Черные тоже имеют 7 вариантов первого хода.
Тогда после первого хода черных будет уже 49 возможных состояний, но количество хранимых досок не изменится, поэтому:
9*4 байтов на доски + 57 * 2 байтов на индексы = 150 байт (около 3 байт на состояние)
Дальше придется использовать трёх- и 4-х-байтовые состояния, но все равно выигрыш будет существенным.
Для большей экономии поле для черных шашек поворачивать на 180.
Вот это дело хорошее.
Не столько даже для экономии одного бита «чей ход» сколько для уменьшения колва самих записей. Если мы храним только доски «ход белых», а когда нужны ход черных, то отражаем зеркально, то если черные попали в такую же ситуацию как была «вчера» у белых, то лучшие ходы у них будут те же, все исходы будут такие же и т.п. А значит зачем их еще раз считать?
Хорошо бы еще сделать другие топологически эквивалентные отражения. В голову приходит пока только отражение по горизонтали. Но тут нужна какая-то функция определения «нужно отражать». Можно конечно проверять в базе оба варианта, если поиск в базе дешевый. Но у меня пока нет хорошего стройного предложения.
Остальной текст я понял плохо если честно.
Можно пример для доски 3*3 как я писал выше?
Не знаю как ТС, но лично мне кажутся важными следующие ограничения:
1 — длина записи должна быть фиксированной.
2 — везде используем целое колво бит.
3 — сущности должны нести дополнительный смысл (отсутствие недамок на чужой дальней линии это доп.смысл, таблица «есть ли фигура» — доп.смысл, а совокупность трех клеток шифруется 7 битами — не есть доп.смысл и просто «дробное колво бит».
4 — позиция должна полностью определяться информацией из самой позиции, и не требовать информации от соседних позиций (сохранять цепочку ходов можно в ограниченном количестве кейсов).
Ок, а как тогда вычислять местоположение шашки?
Давай на уменьшенном примере распишу.
У нас есть доска 3*3 клетки. На доске может быть максимум 5 фигур.
1 * * *
2 * * *
3 * * *
А Б В
Допустим у нас есть на доске четыре шашки (из пяти возможных):
А1 — черная шашка
А2 — белая шашка
А3 — белая шашка
Б3 — белая дамка
тогда первая таблица на 9 бит будет выглядеть так:
1 0 0
1 0 0
1 1 0
Ну или в одну строчку
1 0 0 1 0 0 1 1 0
Вторая таблица содержит информацию о том какие именно шашки у нас стоят в нужных позициях:
черная шашка, белая шашка, белая шашка, белая дамка, *любое_значение*
Примем такое обозначение фигур:
00 — белая шашка,
01 — черная шашка,
10 — белая дамка,
11 — черная дамка
тогда таблица видов фигур будет выглядеть так:
01, 00, 00, 10, ??
где вопросы это произвольное значение.
Итого вся наша позиция выглядит так:
1 0 0 1 0 0 1 1 0
01, 00, 00, 10, ??
Теперь расшифровываем.
Первая позиция у нас единица. Она соответствует А1.
Значит в А1 есть шашка. Поскольку у нас это первая единичка, то смотрим в первую ячейку видов фигур. Там 01.
Значит
А1 Черная шашка.
Следующая ячейка у нас ноль, значит в Б1 у нас ничего нет, дальше тоже ноль, значит и в В1 пустая, дальше единичка, это ячейка А2, она у нас вторая единичка, так что смотрим ее значение во второй ячейке. Это два нуля, т.е. Белая шашка,
А2 Белая шашка,
дальше два нуля — Б2 и В2 пустые,
А3 у нас единичка, значит что-то есть. Раз это у нас третья единичка, то смотрим третью ячейку.
Там два нуля, значит опять белая шашка,
А3 — белая шашка,
Б3 у нас единичка, значит там что-то есть. Смотрим четвертую ячейку, видим 10 т.е. белая дамка,
Б3 — белая дамка,
ну и в конце ноль — в В3 ничего нет.
Итак — мы восстановили исходную позицию.
На это нам ушло 9 бит карты занятости и 18 бит расшифровки, итого 27 бит. При этом два последних не использовались, так что если 4 шашки на поле это максимум, то нам бы хватило 25 бит.
27 бит это не выгодно — так мы можем втупую по 3 бита на клетку выделить, но 25 — уже экономия.
Или я плохо объясняю, или дальше жать явно не стоит, раз уже тут начинаются путанницы)
У нас есть доска 3*3 клетки. На доске может быть максимум 5 фигур.
1 * * *
2 * * *
3 * * *
А Б В
Допустим у нас есть на доске четыре шашки (из пяти возможных):
А1 — черная шашка
А2 — белая шашка
А3 — белая шашка
Б3 — белая дамка
тогда первая таблица на 9 бит будет выглядеть так:
1 0 0
1 0 0
1 1 0
Ну или в одну строчку
1 0 0 1 0 0 1 1 0
Вторая таблица содержит информацию о том какие именно шашки у нас стоят в нужных позициях:
черная шашка, белая шашка, белая шашка, белая дамка, *любое_значение*
Примем такое обозначение фигур:
00 — белая шашка,
01 — черная шашка,
10 — белая дамка,
11 — черная дамка
тогда таблица видов фигур будет выглядеть так:
01, 00, 00, 10, ??
где вопросы это произвольное значение.
Итого вся наша позиция выглядит так:
1 0 0 1 0 0 1 1 0
01, 00, 00, 10, ??
Теперь расшифровываем.
Первая позиция у нас единица. Она соответствует А1.
Значит в А1 есть шашка. Поскольку у нас это первая единичка, то смотрим в первую ячейку видов фигур. Там 01.
Значит
А1 Черная шашка.
Следующая ячейка у нас ноль, значит в Б1 у нас ничего нет, дальше тоже ноль, значит и в В1 пустая, дальше единичка, это ячейка А2, она у нас вторая единичка, так что смотрим ее значение во второй ячейке. Это два нуля, т.е. Белая шашка,
А2 Белая шашка,
дальше два нуля — Б2 и В2 пустые,
А3 у нас единичка, значит что-то есть. Раз это у нас третья единичка, то смотрим третью ячейку.
Там два нуля, значит опять белая шашка,
А3 — белая шашка,
Б3 у нас единичка, значит там что-то есть. Смотрим четвертую ячейку, видим 10 т.е. белая дамка,
Б3 — белая дамка,
ну и в конце ноль — в В3 ничего нет.
Итак — мы восстановили исходную позицию.
На это нам ушло 9 бит карты занятости и 18 бит расшифровки, итого 27 бит. При этом два последних не использовались, так что если 4 шашки на поле это максимум, то нам бы хватило 25 бит.
27 бит это не выгодно — так мы можем втупую по 3 бита на клетку выделить, но 25 — уже экономия.
Или я плохо объясняю, или дальше жать явно не стоит, раз уже тут начинаются путанницы)
Спасибо! Понял! Здорово!
Подумаю, как это лучше реализовать.
Сжимать, думаю, что не нужно. Так как в cache-памяти у меня лежат данные о позициях. И для того, чтобы проверить, рассматривалась ли данная позиция ранее, придётся сжимать данные и только после этого проверять. А это мне кажется повлияет на скорость.
Подумаю, как это лучше реализовать.
Сжимать, думаю, что не нужно. Так как в cache-памяти у меня лежат данные о позициях. И для того, чтобы проверить, рассматривалась ли данная позиция ранее, придётся сжимать данные и только после этого проверять. А это мне кажется повлияет на скорость.
для игры программы лучше топовых профессиональных игроков не требуется просчитывать всю игру. Яркий пример — alphaGo
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Попытки открытия новой шашечной тактики или Что делать с несбыточной мечтой