Код Хэмминга

Тема в разделе "Теоретические знания", создана пользователем lotterpro, 30 май 2016.

  1. lotterpro

    lotterpro Бывалый

    29 окт 2015
    1.771
    1.215
    Уфа
    Имя
    Артур
    Немногие знают, что брифы, создаваемые в популярной программе Total_wiz_mar ("лягушка"), основаны на так называемых системах покрытия (covering designs), которые чаще всего используются для игры в лотереи.

    В математике системы покрытия традиционно обозначают формулой C(v, k, t, m, L)=b, где:
    v - количество чисел, входящих в систему;
    k - количество призовых чисел в лотерейной формуле;
    t - минимальное количество чисел, которое должно совпасть;
    m - количество угаданных чисел среди выбранных в системе;
    L - минимальное требуемое количество комбинаций, имеющих совпадения;
    b - количество комбинаций в системе.

    Формула C(20,6,4,5,1)=145 означает, что если в лотерее, в которой разыгрывается 6 чисел [k], вы угадаете 5 чисел [m] из 20 выбранных чисел [v], то в системе из 145 комбинаций [.b], будет минимум одна комбинация [L], в которой совпадет 4 числа [t].
    Говоря языком тотошников, это бриф с гарантией 4.

    Основная задача системы покрытия обеспечить максимальное покрытие (гарантию) при минимальном количестве купонов.

    Карту покрытия можно наглядно увидеть в самой программе ("Окна" -> "Показать карту покрытия").

    upload_2016-5-30_22-2-13.png

    Условные обозначения на карте:
    Зеленый прямоугольник - вариант покрыт по заданной категории только одной ставкой.
    Синий прямоугольник - вариант покрывается несколькими ставками.


    Если на карте покрытия есть белые прямоугольники, значит этот пакет не имеет гарантии.

    Поэтому в брифе белых прямоугольников нет. При этом каждый купон в брифе должен иметь минимальное количество пересечений с другими вариантами. Т.е., чем меньше синих прямоугольников, тем меньше купонов потребуется для обеспечения гарантии. Если синих прямоугольников слишком много, то система избыточна, т.е. неэффективна с точки зрения затрат.

    Так вот, задача создания оптимальной системы покрытия в математике не имеет однозначного решения. Более того, если с помощью одного метода находились казалось бы самые оптимальные системы, то в последствии, применяя другие методы, рассчитывались системы, имеющие то же покрытие при меньшем количестве вариантов. Так, до недавнего времени считалось, что самой оптимальной системой покрытия для лотереи 6 из 49 была C(49,6,3)=167, т.е. пакет из 167 комбинаций, дающий гарантию тройки. Но относительно недавно была найдена система из 163 комбинаций, дающая такую же гарантию.

    хемминг01.PNG

    Исследования Хэмминга не касаются собственно систем покрытия. Основная область их применения - системы передачи, кодирования и хранения информации. Так называемое расстояние Хэмминга является функцией, определяющей расстояние в метрическом пространстве, между объектами одинаковой размерности.

    upload_2016-5-30_22-44-4.png upload_2016-5-30_22-46-44.png

    Как мы можем применить исследования Хэмминга для тотализатора? Путем создания систем с более оптимальным покрытием или, проще говоря, брифов со значительно меньшим количеством купонов.

    Вот, например, шаблон "лягушки" - два одинара, 13 двойников с гарантией 11 (файл 13-0-9-00024.txt в папке kombin).

    В шаблоне 24 купона (1200 руб.), 100% покрытие выглядит таким образом:

    toto1.png

    А вот бриф, созданный с помощью кода Хэмминга с той же гарантией:

    toto2.png

    В нем 16 купонов (800 руб.), которые также обеспечивают 100% покрытие. Даже невооруженным глазом видно, что распределение покрытия более равномерное (синих прямоугольников меньше).
    При этом бриф на 1/3 меньше по размеру и соответственно дешевле брифа "лягушки" на 600 руб.

    Не верите? Скачайте этот файл, положите в папку kombin и проверьте сами.
     

    Вложения:

    Sven1960, Lancer, nsa и 8 другим нравится это.
  2. Guarantee

    Guarantee Модераторы Администрация

    28 окт 2015
    15.352
    4.008
    Москва
    Имя
    Константин
    Реальна ли глобализация процесса для остальных схем, или, скажем, наиболее популярных? Например, бриф-14 с 4 одинарами за 9,600, или та же "говно-схема" в 4 одинара?
     
  3. InteractNurik

    InteractNurik Бывалый

    7 дек 2015
    1.339
    726
    Уфа
    Имя
    Ильнур
    Под любую системы игры есть стандартный код, Он в больших случаях совпадает с системой покрытия лягушки. В свою очередь, математически доказаны меньшие покрытия для данной схемы игры. Чем сложнее системы, т.е. чем больше перекрытий, тем труднее найти этот самый минимальный код!
     
  4. InteractNurik

    InteractNurik Бывалый

    7 дек 2015
    1.339
    726
    Уфа
    Имя
    Ильнур
    Вот некоторые коды для перекрытий событий с 3-мя исходами!

    [​IMG]
     
    DJMC и lotterpro нравится это.
  5. mikey1novo

    mikey1novo Новичок

    19 апр 2016
    42
    16
    Барнаул
    Имя
    Михаил
    Где-то встречал формулу для определения минимального значения вариантов для покрытия с определенной гарантией. Меньше которого никак не может быть. Что-то из комбинаторики.

    Вопрос знающим: для систем с 15-ю двойниками в Total Wiz Mar оптимальные системы представлены или нет?
     
  6. lotterpro

    lotterpro Бывалый

    29 окт 2015
    1.771
    1.215
    Уфа
    Имя
    Артур
    Там есть системы для любых вариантов, другое дело насколько они оптимальны.

    Как пишет сам автор программы:
    Т.е. я предполагаю, что каждый бриф-шаблон делался по своему алгоритму, и процесс поиска оптимального варианта занимал довольно много времени и вычислительных ресурсов. И не всегда выбранный вариант был до конца проработан под использование в реальной игре, т.к. цель максимального покрытия у разработчика ставилась выше логики.

    Например, внимательно посмотрите на этот шаблон (6-4-6-00012):

    6e2a7b012b8ccdb30d82750e2be2d0f9.png

    В последнем 15-м матче у нас стоит перекрытие 1Х2. А в брифе всегда будет только один из трех вариантов (отмечено красным). Можно ли играть таким брифом? Я бы не стал.

    А вот шаблон по коду Хэмминга:

    b5b500587eee38c4aa2f189d9bf1a830.png

    Все исходы в 15-м матче распределены равномерно, карта покрытия визуально также более равномерна, и купонов в брифе не 12, а 10.

    Теоретически да, но практически пока не представляю сколько потребуется ресурсов для этого.
     
    mikey1novo и Guarantee нравится это.
  7. mikey1novo

    mikey1novo Новичок

    19 апр 2016
    42
    16
    Барнаул
    Имя
    Михаил
    Я так понимаю, что только полным перебором можно найти самый оптимальный бриф. Другой вопрос, что эта задача затребует много вычислительного времени.
     
  8. mikey1novo

    mikey1novo Новичок

    19 апр 2016
    42
    16
    Барнаул
    Имя
    Михаил
    Посмотрел карту покрытия в лягушке - получается для данных страховок и категории это и есть оптимальный вариант. Поправьте, если не так.
     
  9. lotterpro

    lotterpro Бывалый

    29 окт 2015
    1.771
    1.215
    Уфа
    Имя
    Артур
    Да, лучше пока нет.

    Насчет перебора вариантов - неправильный метод, который дает слишком много вариантов (проверено).
     
  10. mikey1novo

    mikey1novo Новичок

    19 апр 2016
    42
    16
    Барнаул
    Имя
    Михаил
    Я имел ввиду не совсем то. Тут подразумевается полный перебор всех возможных подмножеств от полного множества, проверка их на покрытие полного множества по определенной категории и выбор из них множества с минимальным количеством вариантов. Но это займет очень и очень много времени.