- В этой теме 429 ответов, 20 участников, последнее обновление 13 лет, 2 месяца назад сделано
.
-
Сообщения
-
To Plus600:
Сергей, где-ж Вы были раньше? 😉Раньше я был там же
и всегда говорил, что plus полностью поддерживает PDN. Оказалось, много времени уделял основной работе и кое за чем в новой редакции стандарта не уследил… 
Последние сообщения из этой ветки куда-то пропали
Еще раз:
Вышло обновление движка KestoG 1.3: http://www.igorkorshunov.narod.ru/Draughts/
Сила игры значительно возросла. Теперь он может бороться с лучшими программами, хотя и вовсе не использует ЭБ.KestoG 1.3 по-прежнему значительно уступает Каллисто.
Игорь, у меня вопрос. Цитирую Ваш пост:
«Базы совсем несжаты. В каждом байте хранится 4 позиции,
хотя можно было хранить 5. Это делалось для того,
чтобы при сжатии лучше сжимались.
Но в конце концов я решил отказаться от сжатия совсем.»
Если это не секрет, поясните, пожалуйста, как в байт запихнули 4 позиции
: Или это касается только баз окончаний 6-ки, в которых на доске одновременно не может быть более 6 шашек :
Сколько нужно байт чтобы хранить позицию из 24 шашек: (минимум)
Байт это Восемь бит.
Для хранения результата используется 2 бита (безранговые ЭБ) для определения результата — Выиграно, проиграно, ничья.
Хотя хранить можно 5 результатов, так как 3^5=243<256Сама позиция в ЭБ не хранится!!! По позиции вычисляется адрес в ЭБ, по которому хранится результат.
В ЭБ не пишутся позиции.
Полную информацию о позиции можно писать в Хеш (вместо Зобриста)
Для этого необходимо 75 бит (Для быстрого расчета) или что то-же самое 9-10 байт.
Этого достаточно чтоб записать любое расположение любого количества шашек на 32 полях доски.Короче — на восьми полях (первая и последняя горизонталь) по 4 возможных состояния, на остальных 24 по 5.
Итого необходимое количество бит — Log2(4)*8+Log2(5)*24.
Очередь хода хранить не надо, если очередь хода черных — просто переворачиваем доску.Первая и последняя горизонталь — 256 позиций=1 байт, 2-7 — 625 позиций в горизонтали=10 бит
2*8+6*10=76 бит (10 байт)
Если считать по вертикали — 400 позиций в вертикали=9 бит
9*8=72 бит можно в 9 байт уместиться? Так наверно проще и экономичнее.Ничего не понял.
Если матиматика говорит что для однозначенго представления любой комбинации шашек на доске требуется
Log2(Число Комбинаций) бит,
А число позиций 5^24*4^8, то
Значит Формула Log2(4)*8+Log2(5)*24 верна…
2*8+2,3219280948873623478703194294894*24=71,…
То есть нужно 72 бита — 9 байт. В предыдущем посте я немного ошибся…
Если учесть что шашек каждого цвета не больше 12-ти, то потребуется чуть меньше памяти на позицию, но значительно усложнится (и станет более медленным) расчет Ключа.Интересная инфа про сжатие ЭБ есть у тундровцев. В одном байте они хранят (если не шутят 😉 ) 40 позиций!
Даже в Чинуке хранят до 80-ти и больше позиций в байте (сжатые полные ЭБ)
И алгоритмы сжатия достаточно просты…Насколько я понимаю — в Тундре неполные ранговые ЭБ.
Не вижу вообще никакого смысла в использовании ранговых ЭБ (в практической партии оно ненужно), а использование Неполных ЭБ резко снижает их эффективность.
Я имел ввиду разложить позу не по горизонтали, а по вертикали.
В вертикали может быть 400 позиций (4*5*5*4=400), т.е. 9 бит х
8 вертикалей= 9 байт (Получается, что Ваши подсчеты верны 😉 )Отчего же неполные ЭБ снижают эффективность их использования?
Нечетные базы в определенных случаях могут быть вредными, полная 6-ка с неполной базой 8-ки (4 на 4) может оказаться очень полезной.
Где-то читал, что через 4 на 4 проходит более 80% партий.
Еще более полезной может оказаться 5 на 5, но там видимо, огромные базы будут.Я говорю о другой неполности — Когда для большего сжатия, например, хранят позиции только с очередью хода одной стороны (например той у которой больше шашек) и т.д.
Именно такой неполнотой добиваются большего сжатия ЭБ, и именно такая неполнота уменьшает эффективность использования ЭБ.
- Для ответа в этой теме необходимо авторизоваться.