Да — я тут буду следовать дубнинской брошюре Пьера Деорнуа, "Комбинаторная теория игр", а более подробно это (и не только!) описано в книгах
* Berlekamp E. R., Conway J. H., Guy R. K. Winning Ways for your Mathematical
Plays
и
* Conway J. H., On Numbers and Games
Так вот — давайте рассматривать игры в математическом смысле этого слова, причём достаточно хорошие. Пусть они всегда заканчиваются за конечное число ходов, в них нет никакой случайности, скрытой информации, и так далее. Пусть игроки ходят по очереди — и пусть (это важное соглашение!) всегда проигрывает тот, кто не может сделать ход.
Иногда — как в игре ним — разрешённые ходы для игроков одни и те же; такие игры называют равноправными. Но вообще-то это не обязательно: может быть, один игрок может двигать только синие фишки, а другой только красные.
На играх есть очень естественная операция суммы. Чтобы сложить две игры A и B, нужно просто поставить доску для игры в A рядом с доской для игры в B — и договориться, что каждый игрок ходит там, где хочет. Понятно, что эта операция коммутативная (всё равно, с какой стороны какую доску ставить) и ассоциативная (что так, что так для суммы A+B+C будут стоять рядом три доски, A, B и C).
А вообще что об этой операции можно сказать? Скажем, кто будет выигрывать в сумму игр, которые мы насколько-то понимаем?
Сразу можно заметить, что игра ним с несколькими кучками камней — это сумма нимов с одной кучкой каждый. И поэтому ясно, что сумма может быть гораздо менее тривиальной, чем складываемые игры по отдельности.
Post #4407
1.67K