Автор |
Сообщение |
Loosseer |
|
Тема сообщения:
Отправлено: Нояб 06, 2007 - 08:10 PM
|
|
Зарегистрирован: Нояб 03, 2007
Сообщений: 27
|
|
Цитата:
Если в словарь помещать только последовательности одного результата, то сжатие однозначно будет лучше чем у RLE.
Не согласен - будет равная, а не лучше - просто выявится структура рядомлежащих позиций (механизм индексаци важен тут)
А вот за счет комбинирования выявится структура небольших отклонений, что и даст небольшой выигрыш
Вообще еще раз замечу, что сжатие шашек с 90% ничиьих и поддавков с их почти полным отсутствие совсем разные вещи
Пример: Сортируем позиции по балансу фигур и получаем в шашках монотонные последовательности, а в поддавки все равно будет чехарда
Сжатие шашек однозначно сильнее выходит |
|
|
|
|
|
Loosseer |
|
Тема сообщения:
Отправлено: Нояб 06, 2007 - 07:34 PM
|
|
Зарегистрирован: Нояб 03, 2007
Сообщений: 27
|
|
Насчет словаря окончаний:
Каков был бюджет - таков и результат
при 128 Мб оперативки в 2001 супротив 2Гб у чинок еще в 1991 ловить было можно только здравый смысл
Сделал классификацию окончаний
Запустил прогон расчетов реальных позиций
Взял наиболее восстребованные классы, остальные выбросил
правило 20 - 80 еще никто не отменял
Сегодня можно посильнее базу протолкнуть - только ИМХО кэш тогда был важнее
Насчет полезности (потерял свои тесты) - есть небольшая - дык тока вот Каллисто демо вообще почти без баз обходится
Насчет ОФ:
Моя реализация мет мин квадр требовала обращения матрицы размерности числа параметров
При размерности более 75 расчет занимал более часа
пришлось остановиться на разбиении параметров в группы и расчет внутри групп
Потом пытался уже соединить группы меж собой в окончательную сумму с коэффициентами
Тут уж коэффициэнты не считались через Root2 пришлось ручной генетикой
многи просто ушли в 0
Некоторые мешали друг другу (типа +101 -100.8 вместо ожидаемого диапазона внутри 0..1)
Как-то на глаз все равно вышло
Сейчас есть 32*2*(4стадии игры)+14+1+1+1 ~ 300
P.S. прикольно написал кэш вместо хэш - а потом подумал и правда же он важнее был |
|
|
|
|
|
Kallisto |
|
Тема сообщения: Re: Программа "GiveAway" в преверие возможного воз
Отправлено: Нояб 05, 2007 - 03:31 PM
|
|
Зарегистрирован: Авг 18, 2003
Сообщений: 747
|
|
Loosseer писал(а):
полной девяткой там не пахнет
360 Млн позиций указано же
И насколько эти позиции помогают? Мне кажется, что их слишком мало. |
|
|
|
|
|
NS |
|
Тема сообщения:
Отправлено: Нояб 05, 2007 - 02:34 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
Так как с программой? Похоже всё-таки исходники большинство интересуют, но пока голосование не закончилось интересно пощупать саму программу...
Насколько в ней большая ОФ? Сколько суммарно в ней коэффициентов?
Цитата: фиксированный словарь как раз генетикой и делал
взял наглаз начальный набор (256 кодов)
Если в словарь помещать только последовательности одного результата, то сжатие однозначно будет лучше чем у RLE, и хороший словарь достаточно легко посчитать. Скорость доступа есно будет такая-же как и у RLE. |
|
|
|
|
|
Loosseer |
|
Тема сообщения: Re: Программа "GiveAway" в преверие возможного воз
Отправлено: Нояб 05, 2007 - 02:02 PM
|
|
Зарегистрирован: Нояб 03, 2007
Сообщений: 27
|
|
Kallisto писал(а): Loosseer писал(а):
База окончаний:
360 Млн "вменяемых" позиций 2-9 шашек (безранговая) - размер 36Мб
И мне тоже интересно как удалось 9-фигурку запихнуть в 36 Мб. А в несжатом виде какой размер?
А насчет 21%. Семь партий - это слишком мало, чтобы делать какие-то выводы о силе игры..
полной девяткой там не пахнет
360 Млн позиций указано же
несжатый размер сами можете посчитать, с учетом того что в поддавках ничьих менее 1%, а в шашках скорее все 90%
фиксированный словарь как раз генетикой и делал
взял наглаз начальный набор (256 кодов)
посчитал статистику всякую и сделал набор кодов-кандидатов (2000 шт)
ну и стал паковать словарь с попыткой замены избраного кода на алтернативный случайным образом
через месяц глянул результат, ну 10% был лучше первоначального
Хотя мне сжатие не особо и нужно было 36Мб вместо 75
Просто я под Хэш больше памяти смог забрать 64 вместо 32
а внаши дни вообще вопрос не стоит о таких цифрах
Доступ стал в 2 раза медленнее, но общая скорость упала только на 0.3%
Rar сжимает несжатый словарь до 29Мб, так что меня 36 с линейным доступом устраивает |
|
|
|
|
|
Loosseer |
|
Тема сообщения:
Отправлено: Нояб 05, 2007 - 01:51 PM
|
|
Зарегистрирован: Нояб 03, 2007
Сообщений: 27
|
|
NS писал(а): Я всё-таки никак не могу себе представить миллиард позиций.
Даже если на получение каждой позиции тратилась секунда -
Это 1000000000/3600/24/365=32 года...
Откуда взялся миллиард позиций с точной оценкой (решенных) ?
Я взял первый и второй турнир по переписке
все партии загнал в список позиций до 15 хода
Получилось не помню точно , но порядка 1000
Запустил расчет для каждой на 10 секунд
И сохранял просто хеш на диск
Потом склеил все с удалением одинаковых + отрезал редкивстречающиеся = получил миллиард
Ну а потом полгода расчетов на глубине 3,4,5,6
Посчиталось 60%
Шашки это огромной ничейное поле с микоскопическими ямками результативных позиций
Поддавки это тоненкое лезвия ничейного ножа (причем далеко не прямое лезвие) - шаг вправо, шаг влево и ты проиграл |
Последний раз редактировалось Loosseer в Нояб 05, 2007 - 02:21 PM; всего редактировалось 1 раз
|
|
|
|
|
NS |
|
Тема сообщения:
Отправлено: Нояб 05, 2007 - 12:57 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
Я всё-таки никак не могу себе представить миллиард позиций.
Даже если на получение каждой позиции тратилась секунда -
Это 1000000000/3600/24/365=32 года...
Откуда взялся миллиард позиций с точной оценкой (решенных) ? |
|
|
|
|
|
Kallisto |
|
Тема сообщения: Re: Программа "GiveAway" в преверие возможного воз
Отправлено: Нояб 05, 2007 - 06:32 AM
|
|
Зарегистрирован: Авг 18, 2003
Сообщений: 747
|
|
Loosseer писал(а):
База окончаний:
360 Млн "вменяемых" позиций 2-9 шашек (безранговая) - размер 36Мб
И мне тоже интересно как удалось 9-фигурку запихнуть в 36 Мб. А в несжатом виде какой размер?
А насчет 21%. Семь партий - это слишком мало, чтобы делать какие-то выводы о силе игры.. |
|
|
|
|
|
AlexanderS |
|
Тема сообщения:
Отправлено: Нояб 05, 2007 - 03:01 AM
|
|
Зарегистрирован: Авг 29, 2002
Сообщений: 845
Откуда : Якутск
|
|
21% результат конено неудовлетворительный. Хотя для игры вполне может подойти - поддавочныму монстраму мало кому хочется постоянно проигрывать
Меня заинтересовала база окончаний. Каким образом строил фиксированный словарь для LZ? И какой коэффициент сжатия получился? У меня RLE на более быстром проце медленнее работает... Тоже была мысль LZ с фиксированным словарем попользовать, но на построении эфеективного словаря стух |
|
|
|
|
|
Loosseer |
|
Тема сообщения:
Отправлено: Нояб 04, 2007 - 07:48 PM
|
|
Зарегистрирован: Нояб 03, 2007
Сообщений: 27
|
|
1) Саму программу выложить? (а исходники на родном Вам паскале не нужны?) - ответ прост - смотрим голосование
2) ручная генетика" - это как?
расчет 4-5 сложных компонентов Оф, а потом ручная доводка "полным сканированием " их весовых К
типа
считае веса полей
считаем веса еще что-то
....
потом эти компоненты меж собой комбинируем с взвешиванием коээфицентов ( да ты ж знаешь все это ) |
|
|
|
|
|
NS |
|
Тема сообщения:
Отправлено: Нояб 04, 2007 - 06:50 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
А можно саму программу куда-нибудь выложить? Хочется посмотреть в какую силу она играет.
"ручная генетика" - это как? Ручная корректировка коэффициентов в ОФ после их расчета? |
|
|
|
|
|
Loosseer |
|
Тема сообщения:
Отправлено: Нояб 04, 2007 - 06:03 PM
|
|
Зарегистрирован: Нояб 03, 2007
Сообщений: 27
|
|
600 000 000 позиций с расчитанным окончанием были взяты из 1000 000 000 позиций наиболеечастовстречаемых при анализе реальных партий по переписке (расчет примерно 6 месяцев)
критерий оценки эффективности и сама эффективность реализованы не были - просто статистика и результат по мин квадр - программа стаоа играть сильнее и все ( никаких оценок рейтинга ЭЛО не проводилось)
P.S.
special for NS ручная геннетика присутсвовала |
|
|
|
|
|
NS |
|
Тема сообщения:
Отправлено: Нояб 04, 2007 - 05:37 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
А много прибавки (силы) дал метод наименьшей суммы квадратов?
Использовался для решенных позиций - то есть для позиций с известным результатом?
Если не секрет, откуда база на 600 000 000 позиций? Это позиции из
ЭБ? |
|
|
|
|
|
Loosseer |
|
|
Тема сообщения: Программа "GiveAway" в преверие возможного возрожд
Отправлено: Нояб 04, 2007 - 03:21 PM
|
|
Зарегистрирован: Нояб 03, 2007
Сообщений: 27
|
|
Доброго Всем времени суток.
Достал из старых архивов свои наработки и думал стирать или нет.
Решил-таки разузнать кому вообще это может быть надо.
Вот резюме:
программа: 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 порвал как тузик грелку
====================
Если набереться некая суммарная потребность в прграмме, то оставлю жить и развиваться |
Описание: |
|
Размер: |
23.76 KB |
Просмотрено: |
7382 Раз(а) |
|
|
|
|
|
|
|