Шашки в России :: Просмотреть тему - Программа "GiveAway" в преверие возможного возрожд

Шашки в России

Шашечные программы - Программа "GiveAway" в преверие возможного возрожд

Loosseer - Нояб 04, 2007 - 03:21 PM
Тема сообщения: Программа "GiveAway" в преверие возможного возрожд

Доброго Всем времени суток. 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

NS - Нояб 04, 2007 - 05:37 PM
Тема сообщения:

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

Loosseer - Нояб 04, 2007 - 06:03 PM
Тема сообщения:

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

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

NS - Нояб 04, 2007 - 06:50 PM
Тема сообщения:

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

Loosseer - Нояб 04, 2007 - 07:48 PM
Тема сообщения:

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

AlexanderS - Нояб 05, 2007 - 03:01 AM
Тема сообщения:

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

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

Kallisto - Нояб 05, 2007 - 06:32 AM
Тема сообщения: Re: Программа "GiveAway" в преверие возможного воз

Loosseer писал(а):

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

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

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

NS - Нояб 05, 2007 - 12:57 PM
Тема сообщения:

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

Loosseer - Нояб 05, 2007 - 01:51 PM
Тема сообщения:

NS писал(а):

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

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

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

Loosseer - Нояб 05, 2007 - 02:02 PM
Тема сообщения: Re: Программа "GiveAway" в преверие возможного воз

Kallisto писал(а):

Loosseer писал(а):

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

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

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

NS - Нояб 05, 2007 - 02:34 PM
Тема сообщения:

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

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

Цитата:

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

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

Kallisto - Нояб 05, 2007 - 03:31 PM
Тема сообщения: Re: Программа "GiveAway" в преверие возможного воз

Loosseer писал(а):

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

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

Loosseer - Нояб 06, 2007 - 07:34 PM
Тема сообщения:

Насчет словаря окончаний:
Каков был бюджет - таков и результат
при 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

- а потом подумал и правда же он важнее был

Loosseer - Нояб 06, 2007 - 08:10 PM
Тема сообщения:

Цитата:

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

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

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

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

NS - Нояб 06, 2007 - 09:13 PM
Тема сообщения:

Цитата:

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

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

Loosseer - Нояб 06, 2007 - 10:18 PM
Тема сообщения:

ну если обращение матрица размера 75х75 происходит мнгновенно , то значит тормозило что-то еще - я лично не замерял и профилированием кода не занимался в этом расчете
например перемножение матриц
я брал по 10 млн тестов (все 600 млн не получалось явно из-за памяти и скорости)
считал несеолько раз и откинув крайние результаты остальные усреднял

P.S. а вот многие дальнейшие события в этой ветке уже мне очевидны

Kallisto - Нояб 07, 2007 - 05:40 AM
Тема сообщения:

Loosseer писал(а):

есть небольшая - дык тока вот Каллисто демо вообще почти без баз обходится

Нет никакой демо.
А базы можно до 6 шашек строить. С ними должно лучше быть.

NS - Нояб 07, 2007 - 07:03 AM
Тема сообщения:

Loosseer писал(а):

Опять не понимаю. Что такое "крайние результаты"?
Подставив для каждой позиции количества признаков и оценку получаем выражение:
(k1*x1+k2*x2+...kn*xn-eval)^2
где k1 - количество признаков в позиции, x1 - искомый вес признака.
Раскрыв скобки и сложив по всем позициям получим полином второй степени. Взяв частные производные по каждому xi получим систему уравнений. Вероятность что матрица вырождена равна практически нулю. Решили уравнение (а решение одно - матрица то не вырождена Smile

), получили веса признаков.
А "крайние результаты" откуда взялись?

Loosseer - Нояб 07, 2007 - 11:15 AM
Тема сообщения:

Насчет мнгновенно расчета root2:
я лично считал 2 суток
брал несколько раз по 10 млн позиций из 600 млн и считал для каждого набора
из результатов откинул наборы с плохой корреляцией
опять не понятно ?

Вообще то вы можете перемножить мнгновенно 2 матрицы 10Мбх75 вещественных чисел двойной точности мнгновенно даже на современном компьютере, а не PIII-650 с 128 Мб где они даже в память не умещаются и надо постоянно со свопом работать?

А вот двойной точности даже не хватало на таких матрицах - вырождались в 90% случаев из-за погрешности (отбрасовались мелкие слагаемые в конце суммирования). Пришлось юзать библиотеку с большей точностью.

А вот мне непонятно зачем выдвигать какие-то суждения как это должно б было быть? Какие-то 32 года на расчет миллиарда позиций и мнгновенное решение root2 для 10000000х75. Question

6 месяцев и 1 час - вот реальные результаты реального эксперимента реализованного на практике.

Если Тузик шел по мосту, упал в воду и утонул. Зачем обсуждать удельную массу тузика, закон Архимеда, психологическое состояние пса и возможность суицида?
Тузик утонул - вот факт и все!
Теперь можно только завести нового пса (лучше породы Водолаз)

P.S. запускал расчет дебютных позиций на глубине 5 сегодня ночью
Скорость 99.14 решенных поз.сек - дальше считайте сами 32 года или сколько надо на миллиард

NS - Нояб 07, 2007 - 11:31 AM
Тема сообщения:

Цитата:

Вообще то вы можете перемножить мнгновенно 2 матрицы 10Мбх75 вещественных чисел двойной точности мнгновенно даже на современном компьютере, а не PIII-650 с 128 Мб где они даже в память не умещаются и надо постоянно со свопом работать?

Это шутка? Нет никакого перемножения матриц в методе наименьших квадратов.
Есть сумма 600 000 000 (по количеству позиций) матриц 75x75, и сумма такого-же количества векторов 1x75. А потом решение уравнения Ax+b=0, где A матрица 75x75.

Квадрат разницы по каждой позиции Это xA(i)x'-xb(i)
Нам всего-лишь надо проссумировать все A(i) и все b(i), получим выражение для суммы квадратов.

Чтоб не выводить готовую формулу - вот она:
http://ru.wikipedia.org/wiki/%D0%9C%D0% ... 0%BE%D0%B2

Решение системы уравнений - моментально. Для составления время тратится на подсчет количества (если PST - то сам факт есть на этом поле/нет шашки) признаков в каждой позиции. 600 миллионов позиций, миллион позиций в секунду - 10 минут.

Потом составление матрицы - 600 000 000* 76 *76 / 2 умножений - несколько минут.

матрицу 600 000 000 хранить в памяти не нужно - достаточно сразу плюсовать посчитав количество признаков по конкретной позиции. И грузить их можно хоть по одной, хоть по 1000, хоть по 1000000.

С погрешностью бороться совсем легко - Разделили позиции на две равные части (по 300 миллионов), посчитали матрицу и вектор в каждой части,и потом сложили. В каждой части аналогично.

Loosseer - Нояб 07, 2007 - 01:24 PM
Тема сообщения:

NS писал(а):

Это шутка? Нет никакого перемножения матриц в методе наименьших квадратов.
Есть сумма 600 000 000 (по количеству позиций) матриц 75x75, и сумма такого-же количества векторов 1x75. А потом решение уравнения Ax+b=0, где A матрица 75x75.

Квадрат разницы по каждой позиции Это xA(i)x'-xb(i)
Нам всего-лишь надо проссумировать все A(i) и все b(i), получим выражение для суммы квадратов.

Чтоб не выводить готовую формулу - вот она:
.....

Решение системы уравнений - моментально. Для составления время тратится на подсчет количества (если PST - то сам факт есть на этом поле/нет шашки) признаков в каждой позиции. 600 миллионов позиций, миллион позиций в секунду - 10 минут.

Потом составление матрицы - 600 000 000* 76 *76 / 2 умножений - несколько минут.

матрицу 600 000 000 хранить в памяти не нужно - достаточно сразу плюсовать посчитав количество признаков по конкретной позиции. И грузить их можно хоть по одной, хоть по 1000, хоть по 1000000.

С погрешностью бороться совсем легко - Разделили позиции на две равные части (по 300 миллионов), посчитали матрицу и вектор в каждой части,и потом сложили. В каждой части аналогично.

Уважаемый NS, думаю Вы сами найдете "мелкие" неточности в вышеуказаном.
Остальным же "неолимпиадникам" это мало интересно.
Тот путь куда скатывается обсуждение в этом форуме меня нисколько не удивило (я был готов)
Ваше мнение многие читали здесь http://www.kasparovchess.crestbook.com/ ... 07&p=1

Я не только был готов, но и знаю как это решается. Cool

NS - Нояб 07, 2007 - 01:31 PM
Тема сообщения:

Теперь уже совсем ничего не понял в вашем сообщении. Нет неточностей, нет никаких проблем в методе наименьших квадратов - не только с тем что коэффициенты (количества признаков) по 600 000 000 позициям не лезут в память, но и проблем с округлением.
И есно имея готовые позиции с оценками нет никаких проблем очень быстро получить веса признаков. Хоть тысяча позиций, хоть миллион,хоть миллиард.

Ссылку кривую дали. Через
http://kasparovchess.crestbook.com/viewforum.php?id=13
Можно нормально зайти на форум.

Loosseer - Нояб 07, 2007 - 01:38 PM
Тема сообщения:

Kallisto писал(а):

Loosseer писал(а):

есть небольшая - дык тока вот Каллисто демо вообще почти без баз обходится

Нет никакой демо.
А базы можно до 6 шашек строить. С ними должно лучше быть.

Т.е. то что я скачл с описанием как демо версия с 3-х шашечными окончаниями является полной версией!
Это радует Smile

Я посмотрел свой код - нашел несколько косяков. Подправлю и выложу ту версию что получше будет играть после турнира в выходные.

Kallisto - Нояб 07, 2007 - 01:57 PM
Тема сообщения:

Loosseer писал(а):

О чем вообще речь? Нет там никаких "3-х". И откуда взялось "демо версия"?
Меня терзают смутные сомнения что это все про какую-то другую программу. Smile

Loosseer - Нояб 17, 2007 - 05:49 PM
Тема сообщения:

В прошлые выходные пытался анализировать эффективность различных механизмов программы в ракурсе текущих вычислительных возможностей
Наткнулся на низкую эффективность хеша
Для пробы отключил его и провел матч из 10 партий
Без vs Хеш - +8-0=2
Немного опешил
Всю неделю переделывал
Отключил все вызовы хэша
Полностью поменял его внутреннюю реализацию
(12 байт на позицию = доска+тип хэширования+глубина+стоимость+лучший ход)
Стал потихоньку подключать обратно
Подключил пока не все
С хешем считает в 2 раза быстрее
Коэффициэнт ветвления 1.8 (это не шашки однако с 1.5)
Думаю выложить 2 варианта программы в адном орхиве
2003 год и 2007 beta - скоро будет на рапиде

Loosseer - Дек 17, 2007 - 11:18 PM
Тема сообщения:

программа будет выложена в 2007 году
объем порядка 40Мб
идут перетурбации с алгоритмами расчета - есть усиление игры
потому и не выкладываю пока ничего
юнешеский максимализм пока мну не покинул

Loosseer - Дек 17, 2007 - 11:29 PM
Тема сообщения:

Kallisto писал(а):

Однако жестко играет Ваша программа
перед партией грузится с заметной задержкой
Забирает под себя 50-99% процессора во время расчета
С памятью таже история
Играть на одном компе можно только первую партию - дальше все вообще уходит во владение каллисто (хотя пока у меня выбора другого нет)
реально у меня на AMD 1500XP RAM 1024 обычно на 10-13 глубину считает, а против каллисто тока 6-8

P.S.
Сыграл 9 партий счет пока 5-4 (в чью пользу сами понимаете не важно)

plus600 - Дек 18, 2007 - 07:54 AM
Тема сообщения:

Loosseer писал(а):

реально у меня на AMD 1500XP RAM 1024 обычно на 10-13 глубину считает, а против каллисто тока 6-8

Ходов или полуходов?

Kallisto - Дек 18, 2007 - 09:01 AM
Тема сообщения:

[quote=Loosseer]
Однако жестко играет Ваша программа
перед партией грузится с заметной задержкой
Забирает под себя 50-99% процессора во время расчета
С памятью таже история
[/quote]
Вся ЭБ грузится в память. Расчет во время хода противника можно отключить.

А вообще лучше бы тебе было сделать движок под мою оболочку. Тогда можно было бы провести матч из нескольких сотен партий без проблем.
[quote=plus600]
Ходов или полуходов?
[/quote]
Полуходов, конечно.