Функція Шпрага — Гранді

Функція Шпрага — Гранді — математична функція, яка використовується для визначення виграшної стратегії в комбінаційних іграх, де програє той гравець, який не має можливості зробити черговий крок з певної позиції.

Визначення

Функція Шпрага — Гранді для гри G позначається як g(G) і визначається наступним рекурсивним співвідношенням:

• g(G) = 0 якщо гравець, який починає гру в позиції G, має виграшну стратегію
• g(G) = mex({g(G') | G' є позицією, яка може бути досягнута з позиції G}) інакше

Де mex позначає функцію найменшого виключеного числа, тобто найменшого цілого невід'ємного числа, яке не входить у задану множину.

Властивості

Функція Шпрага — Гранді має такі властивості:

• Вона визначається однозначно для всіх комбінаційних ігор.
• Вона є монотонно неспадною, тобто g(G1) ≤ g(G2) для будь-яких позицій G1 і G2, таких що G1 можна досягти з G2.
• Гравець, який починає гру в позиції з нульовим значенням функції Шпрага — Гранді, має виграшну стратегію.

Застосування

Функція Шпрага — Гранді широко застосовується в теорії ігор для:

• Визначення виграшних стратегій: Вона дозволяє визначити виграшну стратегію для комбінаційних ігор, таких як Нім, де програє гравець, який не може зробити черговий крок.
• Аналіз складності ігор: Вона може бути використана для аналізу складності комбінаційних ігор та визначення кількості кроків до виграшу.
• Доведення теорем про ігри: Вона була використана для доведення ряду теорем про комбінаційні ігри, таких як теорема про впорядкованість ігор.

Історія

Теорема Шпрага — Гранді була незалежно сформульована та доведена Р. Шпрагом у 1935 році та П. М. Гранді у 1939 році.

Функція Шпрага — Гранді є потужним інструментом для аналізу та вирішення комбінаційних ігор. Вона дозволяє визначити виграшні стратегії, аналізувати складність ігор та доводити теореми про них. Її широке застосування зробило її важливим поняттям у теорії ігор.

Поширені запитання

1. Що таке функція Шпрага — Гранді?
2. Як визначається функція Шпрага — Гранді?
3. Які властивості функції Шпрага — Гранді?
4. Де застосовується функція Шпрага — Гранді?
5. Хто і коли сформулював та довів теорему Шпрага — Гранді?

Залишити коментар

Опубліковано Максим на 10 05 2024. Поданий під Вікі. Ви можете слідкувати за будь-якими відповідями через RSS 2.0. Ви можете подивитись до кінця і залишити відповідь.