- В этой теме 47 ответов, 10 участников, последнее обновление 17 лет, 1 месяц назад сделано
.
-
Сообщения
-
На силу игры программы влияет в первую очередь хорошая дебютная библиотека. И, чем меньше времени на ход, тем сильнее это влияние.
Я отношусь отрицательно к сжатию ЭБ. Считаю, что лучше иметь несжатую 5-ку, чем сжатую 6-ку (у меня это было ~80 Мб). Сжимал я алгоритмом, который Мартин Фиерц использует в Cake.
Скорее всего превосходство 6-ки над 5-кой настолько мало, что сжатие его просто убивает.А что это за алгоритм? Сжатие без потерь?
Если медленный доступ к сжатой, то никто не мешает иметь в памяти одновременно сжатую шестерку, и несжатую пятерку.
К сжатой базе обращаться при Depth большем определенного значения, а к несжатой до самого конца перебора.А что это за алгоритм? Сжатие без потерь?
Если медленный доступ к сжатой, то никто не мешает иметь в памяти одновременно сжатую шестерку, и несжатую пятерку.
К сжатой базе обращаться при Depth большем определенного значения, а к несжатой до самого конца перебора.[/quote]Думается более эффективным было бы не держать в памяти (если ее мало) не все классы окончаний. Вроде одна простая против пяти дамок.
Одна простая против пяти дамок сжимается до… Нулевого размера с моментальным доступом
По схеме исключения позиций со взятием — остается один результат…
Поэтому такие экстремальные случаи можно даже не выделять в отдельную схему (не исключать вручную, они будут исключены алгоритмом сжатия)То есть возможен варинат сжатия только классов позиций с перекошенным результатом (например если при сжатии влезает больше 30 позиций в байт) — получается что эти позиции и ОФ неплохо оценит, а до опеределенной глубины можно получить их точную оценку (так как есть ограничение на Depth — мы этим не замедлим перебор).
При этом места в памяти они займут немного.Да и порядок построения 1,2,3,4,5,6,7… можно изменить —
3+3, 2+4, 3+4, 4+4, 1+5, 2+5, 3+5, 4+5, 5+5…
Насколько я понял, в Checkers максимально построены 5+5, причем в 2004-ом году. (Полностью достоверные — то есть с построением всех младших классов)
А что это за алгоритм? Сжатие без потерь?
Если медленный доступ к сжатой, то никто не мешает иметь в памяти одновременно сжатую шестерку, и несжатую пятерку.
К сжатой базе обращаться при Depth большем определенного значения, а к несжатой до самого конца перебора.Сжатие с потерей всех позиций в которых возможны взятия.
А алгоритм какой? Исключаемым позициям — наиболее частую оценку,
Страничный механизм, арифметическое кодирование?Алгоритм самый простой (чтобы очень быстро разжималось). Сжимаются только повторяющиеся символы. Удаленные позиции заменяются на такие, чтобы увеличить число повторений.
RLE — по сравнению с аримфметическим кодированием сжимает хуже,
а доступ с RLE, при страничном механизме (раскрутка до нужной позиции) медленней, чем с арифметическим кодированием…
Есно Арифметическое кодирование должно использовать не просто вероятность результата, а вероятности цепочек (у нас рядом идут похожие позиции), Для лучшего сжатия возможно задание параметров сжатия для каждой страницы отдельно.Меня никогда не интересовали создание и использование ЭБ. Если тебе это интересно, то делай получше и для всех. Тогда все проги получат возможность использовать твои алгоритмы. А может даже найдутся желающие помочь тебе в этом нелегком деле
Меня тогда всё-таки интересуют сроки проведения чемпионата —
Ноябрьские праздники, или Январские?
А то я кучу времени потрачу на ЭБ, в итоге не успею написать прилично играющую программу.А RLE (кодирование повторяющихся символов) — ленивый алгоритм, единственное преимущество которого над арифметическим кодированием — быстрое сжатие. Но скорость сжатия нас же не должна интересовать — главное скорость доступа и степень сжатия,
А по этому параметру RLE проигрывает очень многим алгоритмам.Суть предлагаемого статистического метода сжатия данных.
Отображаем разные последовательности результатов (различной длины) в исходном фале в [0..255]
То есть имеем для сжатого файла вспомогательный массив на 256 элементов.
В каждом элементе хранится длина исходной последовательности результатов и сама последовательность.
Для раскручивания — получаем адрес в сжатом массиве кратного значения (из индексной таблицы), затем раскручиваем — берем значение из сжатого массива, и по вспогательной таблице к счетчику прибавляем хранимое значение.
То есть раскрутка достаточно быстра, сжатие практически максимальное для статистических методов (лучше чем RLE)Сам алгоритм сжатия весьма трудоемок, но алгоритм получения информации из сжатого массива весьма прост.
Сам алгоритм сжатия:
Алгоритм формирования словаря
Сначала в словаре Два слова
0
1
Потом делим значение с большей частотой на два, Допустим это «1» — тогда новый словарь —
0
10
11
Теперь сжимаем исходную последовательность, считаем частоту слов из словаря в сжатой последовательности, значение с наибольшей частотой делим. Например это 11, Тогда новый словарь0
10
110
111И так продолжаем до тех пор пока в словаре не будет 256 элементов (пока его не заполним полностью)
Это для варианта двух возможных результатов, для трех аналогично.При сжатии при помощи словаря, в момент его построения (Так как есть позиции значения которых нас не интересуют) Может возникнуть Вариант что возможна подстановка нескольких разных слов.
Тогда при первом проходе в частоту каждого из N возможных вариантов пишем 1/N, а при повторном проходе просто выбираем вариант с большей частотой на первом проходе.Создал ветку на форуме по алгоритмам сжатия, но там пока тишина…
http://forum.compression.ru/viewtopic.php?t=684Меня тогда всё-таки интересуют сроки проведения чемпионата —
Ноябрьские праздники, или Январские?
А то я кучу времени потрачу на ЭБ, в итоге не успею написать прилично играющую программу.К сожалению к ноябрьским уже не успею. Давайте ориентироваться на январские каникулы. Свирин вроде уже опрос сделал по срокам. В другом топике.
- Для ответа в этой теме необходимо авторизоваться.