Программа "GiveAway" в преверие возможного возрожд

[Loosseer]

Доброго Всем времени суток. 🙄

Достал из старых архивов свои наработки и думал стирать или нет.
Решил-таки разузнать кому вообще это может быть надо.

Вот резюме:

программа: GiveAway (игра в поддавки)
начало разработки: март 2001
цель разработки: выход из депрессии
использовалась как консультат во 2 и 3 матчах по переписке
осенью 2003 разработка заморожена

реализация: Delphi 5 (7759 строк 255K)
размер 36.3 Mb (30.2Mb в архиве)
системные требования :128 Mb памяти, Windows 9x,2k,XP

краткие характеристики интерфейса
игра с компьютером ( задание от 1 до 100 секунд на ход)
ведение протокола партии
расчет за время оппонента отключен
анализ позиции (оценка всех дочерних позиций 1 уровня)
типы анализа: поиск победы, защита, расчет позиций
сохранение/загрузка позиции
установка позиции кликами мышки на доске
анализ идет до полного расчета либо до нажатия кнопки останова
возможна автоматическая игра с опонентом через Буфер обмена (текстовый протокол)

характеристики алгоритма
каскадный PVS с глубиной N тихих ходов
Предварительное упорядочивание: на верхних частях дерева
Хэш: 5-10 млн позиций 64-128Мб( ключ+шаг — спец очистка при заполнении 70%)
Оценочная функция: 4 стадии игры, веса полей, материал, подвижность,2-3 шашечные сочетания
Расчет коэффициэтов на основе метода мин. квадр. для базы данных 600 Млн решенных позиций
Оптимизация: на основе профилирования кода

Глубиное отсечение: реализация не эффективна — отключено
Ходы-убийцы : реализация не эффективна — отключено
История : реализация не эффективна — отключено
Пустой ход: реализация неудачна — отключено
Выборочные продления: реализация не эффективна — отключено

База окончаний:
360 Млн «вменяемых» позиций 2-9 шашек (безранговая) — размер 36Мб
Индексация похожа на реализацию от NS
Сжатие блоками по 512 позиций алгоритмом LZ с фиксированным словарем
Доступ 7 млн. поз/сек (Атлон 1500ХР)

Общая производительность 1 млн поз/сек (Атлон 1500ХР)

Сила игры: GiveAway vs Каллистo Demo +1-5=1(—=+—)
конечно же КаллистоDemo порвал как тузик грелку 😉

====================
Если набереться некая суммарная потребность в прграмме, то оставлю жить и развиваться 👿

[NS]

А много прибавки (силы) дал метод наименьшей суммы квадратов?
Использовался для решенных позиций — то есть для позиций с известным результатом?
Если не секрет, откуда база на 600 000 000 позиций? Это позиции из
ЭБ?

[Loosseer]

600 000 000 позиций с расчитанным окончанием были взяты из 1000 000 000 позиций наиболеечастовстречаемых при анализе реальных партий по переписке (расчет примерно 6 месяцев)
критерий оценки эффективности и сама эффективность реализованы не были — просто статистика и результат по мин квадр — программа стаоа играть сильнее и все ( никаких оценок рейтинга ЭЛО не проводилось)

P.S.
special for NS ручная геннетика присутсвовала

[NS]

А можно саму программу куда-нибудь выложить? Хочется посмотреть в какую силу она играет.
«ручная генетика» — это как? Ручная корректировка коэффициентов в ОФ после их расчета?

[Loosseer]

1) Саму программу выложить? (а исходники на родном Вам паскале не нужны?) — ответ прост — смотрим голосование
2) ручная генетика» — это как?
расчет 4-5 сложных компонентов Оф, а потом ручная доводка «полным сканированием » их весовых К
типа
считае веса полей
считаем веса еще что-то
….
потом эти компоненты меж собой комбинируем с взвешиванием коээфицентов ( да ты ж знаешь все это )

[AlexanderS]

21% результат конено неудовлетворительный. Хотя для игры вполне может подойти — поддавочныму монстраму мало кому хочется постоянно проигрывать

Меня заинтересовала база окончаний. Каким образом строил фиксированный словарь для LZ? И какой коэффициент сжатия получился? У меня RLE на более быстром проце медленнее работает… Тоже была мысль LZ с фиксированным словарем попользовать, но на построении эфеективного словаря стух

[Kallisto]

База окончаний:
360 Млн «вменяемых» позиций 2-9 шашек (безранговая) — размер 36Мб

И мне тоже интересно как удалось 9-фигурку запихнуть в 36 Мб. А в несжатом виде какой размер?

А насчет 21%. Семь партий — это слишком мало, чтобы делать какие-то выводы о силе игры..

[NS]

Я всё-таки никак не могу себе представить миллиард позиций.
Даже если на получение каждой позиции тратилась секунда —
Это 1000000000/3600/24/365=32 года…
Откуда взялся миллиард позиций с точной оценкой (решенных) ?

[Loosseer]

Я всё-таки никак не могу себе представить миллиард позиций.
Даже если на получение каждой позиции тратилась секунда —
Это 1000000000/3600/24/365=32 года…
Откуда взялся миллиард позиций с точной оценкой (решенных) ?

Я взял первый и второй турнир по переписке
все партии загнал в список позиций до 15 хода
Получилось не помню точно , но порядка 1000
Запустил расчет для каждой на 10 секунд
И сохранял просто хеш на диск
Потом склеил все с удалением одинаковых + отрезал редкивстречающиеся = получил миллиард
Ну а потом полгода расчетов на глубине 3,4,5,6

Посчиталось 60%

Шашки это огромной ничейное поле с микоскопическими ямками результативных позиций
Поддавки это тоненкое лезвия ничейного ножа (причем далеко не прямое лезвие) — шаг вправо, шаг влево и ты проиграл

[Loosseer]

База окончаний:
360 Млн «вменяемых» позиций 2-9 шашек (безранговая) — размер 36Мб

И мне тоже интересно как удалось 9-фигурку запихнуть в 36 Мб. А в несжатом виде какой размер?

А насчет 21%. Семь партий — это слишком мало, чтобы делать какие-то выводы о силе игры..

полной девяткой там не пахнет
360 Млн позиций указано же
несжатый размер сами можете посчитать, с учетом того что в поддавках ничьих менее 1%, а в шашках скорее все 90%

фиксированный словарь как раз генетикой и делал
взял наглаз начальный набор (256 кодов)
посчитал статистику всякую и сделал набор кодов-кандидатов (2000 шт)
ну и стал паковать словарь с попыткой замены избраного кода на алтернативный случайным образом
через месяц глянул результат, ну 10% был лучше первоначального
Хотя мне сжатие не особо и нужно было 36Мб вместо 75
Просто я под Хэш больше памяти смог забрать 64 вместо 32
а внаши дни вообще вопрос не стоит о таких цифрах
Доступ стал в 2 раза медленнее, но общая скорость упала только на 0.3%
Rar сжимает несжатый словарь до 29Мб, так что меня 36 с линейным доступом устраивает

[NS]

Так как с программой? Похоже всё-таки исходники большинство интересуют, но пока голосование не закончилось интересно пощупать саму программу…

Насколько в ней большая ОФ? Сколько суммарно в ней коэффициентов?

фиксированный словарь как раз генетикой и делал
взял наглаз начальный набор (256 кодов)

Если в словарь помещать только последовательности одного результата, то сжатие однозначно будет лучше чем у RLE, и хороший словарь достаточно легко посчитать. Скорость доступа есно будет такая-же как и у RLE.

[Kallisto]

полной девяткой там не пахнет
360 Млн позиций указано же

И насколько эти позиции помогают? Мне кажется, что их слишком мало.

[Loosseer]

Насчет словаря окончаний:
Каков был бюджет — таков и результат
при 128 Мб оперативки в 2001 супротив 2Гб у чинок еще в 1991 ловить было можно только здравый смысл
Сделал классификацию окончаний
Запустил прогон расчетов реальных позиций
Взял наиболее восстребованные классы, остальные выбросил
правило 20 — 80 еще никто не отменял
Сегодня можно посильнее базу протолкнуть — только ИМХО кэш тогда был важнее
Насчет полезности (потерял свои тесты) — есть небольшая — дык тока вот Каллисто демо вообще почти без баз обходится

Насчет ОФ:
Моя реализация мет мин квадр требовала обращения матрицы размерности числа параметров
При размерности более 75 расчет занимал более часа
пришлось остановиться на разбиении параметров в группы и расчет внутри групп
Потом пытался уже соединить группы меж собой в окончательную сумму с коэффициентами
Тут уж коэффициэнты не считались через Root2 пришлось ручной генетикой
многи просто ушли в 0
Некоторые мешали друг другу (типа +101 -100.8 вместо ожидаемого диапазона внутри 0..1)
Как-то на глаз все равно вышло
Сейчас есть 32*2*(4стадии игры)+14+1+1+1 ~ 300

P.S. прикольно написал кэш вместо хэш — а потом подумал и правда же он важнее был

[Loosseer]

Если в словарь помещать только последовательности одного результата, то сжатие однозначно будет лучше чем у RLE.

Не согласен — будет равная, а не лучше — просто выявится структура рядомлежащих позиций (механизм индексаци важен тут)

А вот за счет комбинирования выявится структура небольших отклонений, что и даст небольшой выигрыш

Вообще еще раз замечу, что сжатие шашек с 90% ничиьих и поддавков с их почти полным отсутствие совсем разные вещи
Пример: Сортируем позиции по балансу фигур и получаем в шашках монотонные последовательности, а в поддавки все равно будет чехарда
Сжатие шашек однозначно сильнее выходит

[NS]

Моя реализация мет мин квадр требовала обращения матрицы размерности числа параметров
При размерности более 75 расчет занимал более часа

Если линейная ОФ, то расчет 75 коэффициентов методом наименьшей суммы квадратов это решение линейной системы уравнений. 75 неизвестных, 75 уравнений. Решается хотя-бы методом гаусса. Считается моментально.

[Автор]

Сообщения