Google
 

Сайт Андрея Иванова

Андрей Иванов - все секреты шашек и шашистов

Login





 


 Забыли пароль?
 или новый пользователь? Зарегистрируйся!

Кто с нами

Пользователей:  На сайте
Пользователей:  Пользователей: 0
Гостей:  Гостей: 5
Всего:  Всего: 5
Пользователей:  Зарегистрированные
No members connected


Новая тема   Ответить
Предыдущая тема Версия для печати Войти и проверить личные сообщения Следующая тема
Poll
Казнить?
Удалить предварительно сделав копию
9%
 9%  [ 1 ]
Отдать народу для опытов
90%
 90%  [ 10 ]
Всего голосовало : 11


Автор Сообщение
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. прикольно написал кэш вместо хэш Very Happy - а потом подумал и правда же он важнее был
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Kallisto
Тема сообщения: Re: Программа "GiveAway" в преверие возможного воз  СообщениеОтправлено: Нояб 05, 2007 - 03:31 PM



Зарегистрирован: Авг 18, 2003
Сообщений: 747

Loosseer писал(а):

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

И насколько эти позиции помогают? Мне кажется, что их слишком мало.
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
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%. Семь партий - это слишком мало, чтобы делать какие-то выводы о силе игры..
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
AlexanderS
Тема сообщения:   СообщениеОтправлено: Нояб 05, 2007 - 03:01 AM



Зарегистрирован: Авг 29, 2002
Сообщений: 845
Откуда : Якутск
21% результат конено неудовлетворительный. Хотя для игры вполне может подойти - поддавочныму монстраму мало кому хочется постоянно проигрывать Smile

Меня заинтересовала база окончаний. Каким образом строил фиксированный словарь для LZ? И какой коэффициент сжатия получился? У меня RLE на более быстром проце медленнее работает... Тоже была мысль LZ с фиксированным словарем попользовать, но на построении эфеективного словаря стух Smile
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
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
8 Тема сообщения: Программа "GiveAway" в преверие возможного возрожд  СообщениеОтправлено: Нояб 04, 2007 - 03:21 PM



Зарегистрирован: Нояб 03, 2007
Сообщений: 27

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

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

Вот резюме:

программа: 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 порвал как тузик грелку Wink

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



shot.PNG
 Описание:
вот картинка
 Размер:  23.76 KB
 Просмотрено:  7382 Раз(а)

shot.PNG


 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Показать:     
Перейти к:  
Время в формате GMT + 3
Новая тема   Ответить
Предыдущая тема Версия для печати Войти и проверить личные сообщения Следующая тема
PNphpBB2 © 2003-2007 
 
Page created in 0.69683194160461 seconds.