Ворожцов Артём Викторович
Кандидат физико-математических наук, преподаватель кафедры информатики Московского физико-технического института (МФТИ), тренер сборной команды МФТИ по программированию.
Теория игр: нимберы
Теория игр – одна из самых привлекательных теорий, и это неудивительно, вся наша жизнь – игра, и всем хотелось бы в этой игре выиграть. Математика и хитроумные алгоритмы иногда могут помочь в этом. В данной статье рассмотрены нимберы – загадочные числа, которые позволяют во много раз облегчить поиск выигрышной стратегии в определённом классе игр. Красивая теория, связанная с этими числами, довольна сложна. Здесь сделана попытка просто изложить основной результат этой теории, который поможет программистам конструировать выигрышные стратегии для простых логических игр. Однажды мы уже касались это темы (см. №2 2005 г.). По многочисленным просьбам читателей мы снова возвращаемся к этой теме, на этот раз в контексте языка программирования Ruby, о котором много рассказывалось в последних номерах журнала. Нимберы – это целые неотрицательные числа, которые можно поставить в соответствие игровым позициям в некоторых играх. Эти числа были придуманы в результате изучения игры Ним.