Асосҳои ҳолатҳои бозиро омӯзед
Бозиро бо як тӯдаи чӯбча баррасӣ кунед. Алис ва Боб навбат ба навбат бозӣ мекунанд, бо он ки Алис аввал ҳаракат мекунад. Дар ҳар навбат, бозигар бояд аз тӯда , , ё чӯбчаро гирад. Бозигаре, ки чӯбчаи охиринро мегирад, ғолиб мешавад.
Мо ҳолати бозиро ҳамчун ифода мекунем, ки дар он шумораи чӯбчаҳои боқимонда аст.
Мувофиқи шарти масъала:
Ҳолати бурд ҳолатест, ки аз он бозигари ҷорӣ метавонад бурдро маҷбур кунад, агар ҳар ду бозигар ба таври оптималӣ бозӣ кунанд.
Ҳолати бохт ҳолатест, ки аз он бозигари ҷорӣ мебозад, агар рақиб низ ба таври оптималӣ бозӣ кунад.
Пас ҳар як ҳолати бозӣ метавонад ҳамчун ё бурд ё бохт тасниф карда шавад.
Биёед ба бозии боло назар кунем:
Ин қоидаи асосиро медиҳад:
Бо истифода аз ин идея, мо метавонем ҳамаи ҳолатҳоро як ба як тасниф кунем, аз ҳолатҳое оғоз карда, ки дар онҳо ҳеҷ ҳаракат имконпазир нест.
Барои бозии боло, ҳолатҳо аз то чунин тасниф мешаванд:
| Ҳолатҳо | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Натиҷа | L | W | W | W | L | W | W | W | L | W | W | W | L |
Дар ин ҷо, W маънои ҳолати бурдро дорад ва L маънои ҳолати бохтро дорад.
Акнун бозии дигареро бо чӯбчаҳо баррасӣ кунед.
Дар ҳолати , бозигар метавонад ҳар шумораи -и чӯбчаҳоро гирад, ба шарте ки:
Масалан:
Мо метавонем бозиро ҳамчун граф ифода кунем:
Дар ин бозӣ, раванд ҳамеша дар ҳолати анҷом меёбад, зеро дар он ҷо ҳеҷ ҳаракат имконпазир нест. Пас ҳолати ҳолати бохт аст.
Пас аз тасниф кардани ҳамаи ҳолатҳо, мо тасвири зеринро мегирем, ки дар он ҳолатҳои бохт бо ранги сурх ва ҳолатҳои бурд бо ранги сабз нишон дода шудаанд:
N = 7 -> Ҳолати ибтидоӣ (n = 7)
Алис 3 чӯбча мегирад -> Ҳолати нав (n = 4)
Боб 2 чӯбча мегирад -> Ҳолати нав (n = 2)
Алис 2 чӯбча мегирад -> Ҳолати нав (n = 0)