Ответы в темах
-
Сообщения
-
Байт это Восемь бит.
Для хранения результата используется 2 бита (безранговые ЭБ) для определения результата — Выиграно, проиграно, ничья.
Хотя хранить можно 5 результатов, так как 3^5=243<256Сама позиция в ЭБ не хранится!!! По позиции вычисляется адрес в ЭБ, по которому хранится результат.
Я со всеми условиями согласен, хотелось бы сроки установить более четко (чтоб все их подтвердили)
Насчет суммы — посидеть три часа в Кафе компанией — обычно в Питере скидываемся по 1000-2000 рублей…
Неужели 3000руб. за проведение чемпионата в Москве это много????http://www.cs.ualberta.ca/~chinook/
http://www.cs.ualberta.ca/~jonathan/Papers/Papers/databases.psНо статья достаточно старая.
Но чтоб сказать точно…
Чтоб сказать точно — нужно сгенерить 7-ку и 8-ку, сжать и посмотреть что получится. Доступ к несжатой шестерке практически мгновенный, наверное в сотню раз быстрее чем вызов приличной оценочной функции. Если доступ к сжатой семерке будет производиться очень медленно то использование ее в расчете становится практически бессмысленным. Имхо сжатая семерка должна помещаться в 300-500 мегов памяти и иметь при этом скорость доступа хотя бы в сотню тысяч позиций в секунду.
Сжатая семерка влезет в такие объемы даже при использовании простого RLE
Можно спросить у Коршунова (если он посчитал семерку), сколько с его алгоритмом сжатия она занимает места.Почитал дискуссию о сжатии данных…
NS, мы с вам одной задачей занимаемся, поэтому хочу из своего опыта посоветовать вам не тратить время на то как выжать еще лишний мегабайт, а луче подумать, как можно преобразовать сами данные под сжатие: что-то удалить, где-то перегруппировать… для творчества простор!А почему у тебя один бит на позицию в безранговых? Вроде два должно быть.
Преобразование данных под сжатие — хорошо описано в статье о ЭБ в Чинуке.
//
На самом деле 5 позиций в байте для ЭБ на три результата (с удаленными позциями с возможным взятием), и 8 позиций в байте для классов ЭБ на два результата (Два результата после удаления позиций с возможным взятием)На хороших алгоритмах сжатия выигрывается не мегабайт, а сжимается в разы!
У Чинука хранится от 20 до 80 и больше позиций в Байте (и это практически полные ЭБ, исключены только некоторые классы позиций), при Этом их Сжатые ЭБ еще вдобавок сжимаются RAR-ом в пару раз.
100 000 доступов в секунду скорей всего достижимо (скорей всего можно получить бОльшую скорость доступа к сжатым ЭБ в памяти), но нужно проводить тесты.После RLE он очень сильно улучшает сжатие…
Но чтоб сказать точно — достаточно привести статистику по разной длине повторяющихся последовательностей — по ней легко считается на сколько сожмет статичный арифметик (по Формуле Шеннона)
Если вероятности разной длины последоветельности отличаются сильно — то Арифметик даст весьма много.
По статьям который я прочитал выходит что Энтропийные методы на выходе RLE являются стандартом «де факто»Еще идеи по сжатию — перед RLE применить MTF преобразование (продвинутое, основанное на предсказании очередного исхода по предыдущим), а после — статичный Арифметик (правда он не очень быстр)
Главное скорость разжатия. Время сжатия будет все равно существенно меньше времени генерации базы.
Я конечно это понимаю
Арифметик не очень быстр при расжатии (то есть какое-то замедление он даст, и замедлит сильнее чем MTF преобразование — которое практически бесплатно по времени)Еще идеи по сжатию — перед RLE применить MTF преобразование (продвинутое, основанное на предсказании очередного исхода по предыдущим), а после — статичный Арифметик (правда он не очень быстр)
Сам алгоритм сжатия:
Алгоритм формирования словаря
Сначала в словаре Два слова
0
1
Потом делим значение с большей частотой на два, Допустим это «1» — тогда новый словарь —
0
10
11
Теперь сжимаем исходную последовательность, считаем частоту слов из словаря в сжатой последовательности, значение с наибольшей частотой делим. Например это 11, Тогда новый словарь0
10
110
111И так продолжаем до тех пор пока в словаре не будет 256 элементов (пока его не заполним полностью)
Это для варианта двух возможных результатов, для трех аналогично.При сжатии при помощи словаря, в момент его построения (Так как есть позиции значения которых нас не интересуют) Может возникнуть Вариант что возможна подстановка нескольких разных слов.
Тогда при первом проходе в частоту каждого из N возможных вариантов пишем 1/N, а при повторном проходе просто выбираем вариант с большей частотой на первом проходе.Создал ветку на форуме по алгоритмам сжатия, но там пока тишина…
http://forum.compression.ru/viewtopic.php?t=684Суть предлагаемого статистического метода сжатия данных.
Отображаем разные последовательности результатов (различной длины) в исходном фале в [0..255]
То есть имеем для сжатого файла вспомогательный массив на 256 элементов.
В каждом элементе хранится длина исходной последовательности результатов и сама последовательность.
Для раскручивания — получаем адрес в сжатом массиве кратного значения (из индексной таблицы), затем раскручиваем — берем значение из сжатого массива, и по вспогательной таблице к счетчику прибавляем хранимое значение.
То есть раскрутка достаточно быстра, сжатие практически максимальное для статистических методов (лучше чем RLE)Сам алгоритм сжатия весьма трудоемок, но алгоритм получения информации из сжатого массива весьма прост.
Меня тогда всё-таки интересуют сроки проведения чемпионата —
Ноябрьские праздники, или Январские?
А то я кучу времени потрачу на ЭБ, в итоге не успею написать прилично играющую программу.А RLE (кодирование повторяющихся символов) — ленивый алгоритм, единственное преимущество которого над арифметическим кодированием — быстрое сжатие. Но скорость сжатия нас же не должна интересовать — главное скорость доступа и степень сжатия,
А по этому параметру RLE проигрывает очень многим алгоритмам.RLE — по сравнению с аримфметическим кодированием сжимает хуже,
а доступ с RLE, при страничном механизме (раскрутка до нужной позиции) медленней, чем с арифметическим кодированием…
Есно Арифметическое кодирование должно использовать не просто вероятность результата, а вероятности цепочек (у нас рядом идут похожие позиции), Для лучшего сжатия возможно задание параметров сжатия для каждой страницы отдельно.А алгоритм какой? Исключаемым позициям — наиболее частую оценку,
Страничный механизм, арифметическое кодирование?Одна простая против пяти дамок сжимается до… Нулевого размера с моментальным доступом
По схеме исключения позиций со взятием — остается один результат…
Поэтому такие экстремальные случаи можно даже не выделять в отдельную схему (не исключать вручную, они будут исключены алгоритмом сжатия)То есть возможен варинат сжатия только классов позиций с перекошенным результатом (например если при сжатии влезает больше 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-ом году. (Полностью достоверные — то есть с построением всех младших классов)
