Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич

Кроме того, игра — это зрелище, понятное неспециалистам. Машина, которая умеет играть, произведёт впечатление даже на дилетанта. Такая машина способна пробудить в человеке дух соперничества, а значит, и интерес. Люди, далёкие от мира создателей «умных» машин, редко интересуются математическим аппаратом, используемым машиной для принятия решений. Но результат работы этого аппарата (ходы на шахматной или шашечной доске) может быть понятен даже ребёнку. Облекая свои достижения в понятную большинству людей форму, учёные таким образом поддерживают уверенность общества в том, что оно должно и дальше выделять ресурсы на разработку систем искусственного интеллекта.

С незапамятных времён игры становились мишенью для критики со стороны моралистов. «Тавлеи и шахы въ многихъ насъ ωбртаѣми сѹть, а книги ни въ кого же» («Многие из нас только и знают, что играть в тавлеи и шахматы, а книг никто не читает») [443] — написано в «Пчеле» (Μέλισσα) — сборнике назидательных изречений IX в. византийского происхождения, получившем весьма широкое распространение на Руси и Балканах. История, впрочем, показала, что моралистам не под силу истребить игры, а сами игры могут принести немалую пользу науке.

Хотя теория игр оформилась в самостоятельную дисциплину лишь в XX в., учёные уже успели придумать весьма развитую систему классификации, позволяющую разделять игры на различные типы в зависимости от их существенных особенностей.

В первую очередь все игры подразделяются на кооперативные (коалиционные) и некооперативные. В первых игроки объединяются в группы и обязаны соблюдать определённые обязательства перед другими игроками своей группы. В некооперативных играх каждый действует за себя (это не значит, что в процессе игры не могут формироваться союзы или что невозможна координация действий игроков, однако в некооперативных играх следование договорённостям не является обязательным). Можно сказать, что ключевой отличительной чертой некооперативных игр является отсутствие внешнего механизма (например, правил), обеспечивающего неукоснительное следование установленным обязательствам. В соответствии с этим подразделением футбол и бридж — кооперативные игры, а крестики-нолики и шахматы — некооперативные.

Также игры делятся на симметричные и асимметричные. В симметричных играх игроки обладают одинаковым набором возможностей (стратегий) и одна и та же стратегия обеспечивает одинаковый результат каждому из игроков. Например, в игре «камень, ножницы, бумага» каждый из игроков может показать и камень, и ножницы, и бумагу, но, скажем, ножницы всегда побеждают бумагу, вне зависимости от того, какой из игроков их показал — первый или второй. Пример асимметричной игры — прятки, в них у игроков и водящего разные наборы возможностей. Некоторые игры, например шахматы или шашки, иногда называют «почти симметричными», потому что в них существует небольшая разница между белыми и чёрными — белые ходят первыми.

Игры также делят на параллельные и последовательные. В параллельных играх игроки совершают свои ходы одновременно либо не осведомлены о выборе оппонента до тех пор, пока остальные не сделают свои ходы. В последовательных, или динамических, играх участники совершают ходы последовательно и в момент совершения хода обладают информацией о предшествующих действиях других игроков, хотя эта информация может быть и неполной. Уже упомянутая игра «камень, ножницы, бумага» — параллельная (ведь игроки действуют одновременно), а крестики-нолики — последовательная. В повседневной жизни, рассуждая о компьютерных играх, мы часто называем последовательные игры пошаговыми, а параллельные — играми реального времени.

Игры относятся к классу игр с нулевой суммой, если сумма возможных выигрышей игроков равна нулю. Например, если вы играете в орлянку, сумма вашего выигрыша всегда равна сумме проигрыша оппонента, и наоборот, то есть если вы выиграли, например, десять копеек, то ваш оппонент эти десять копеек проиграл или можно сказать, что он выиграл минус десять копеек. В сумме же ваши выигрыши дают ноль. В шахматах наблюдается точно такая же ситуация: если вы выиграли, то ваш противник проиграл, и наоборот, то есть вы с противником не можете выиграть одновременно. Если выигрышу соответствует единица, проигрышу — минус единица, а ничьей — ноль, то сумма результатов в партии всегда будет равна нулю. Игры с нулевой суммой являются частным случаем игр с постоянной суммой. Например, если вы играете в орлянку в казино, которое в каждом раунде изымает в свою пользу половину выигрыша, то раунд такой орлянки будет игрой с постоянной, но не нулевой суммой. На другом полюсе данной классификации находятся игры с непостоянной суммой, в которых стороны могут одновременно выиграть или одновременно проиграть, — например игры, в которых игроки могут сотрудничать, стремясь достичь общей цели. К этому классу игр также обычно относятся игры с одним игроком (в принципе, игру с непостоянной суммой можно представить в виде игры с нулевой суммой при помощи введения дополнительного, фиктивного игрока — например, если в версии орлянки с казино мы будем рассматривать казино как ещё одного игрока, то получим игру с нулевой суммой).

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

Игры с полной (complete) информацией не следует путать с играми с совершенной информацией (perfect), отличительной особенностью которых является тот факт, что игрокам известны все ходы друг друга (а также иные изменения состояния игры, например поступление на руки карт в результате сдачи) с момента начала игры. Если это не так, игра является игрой с несовершенной информацией. Для того чтобы лучше понять принципиальное различие двух последних способов классификации игры, приведём два примера.

В качестве примера игры с полной, но несовершенной информацией можно привести преферанс: каждый из игроков знает заранее условия выигрыша или проигрыша и может рассчитать сумму выплат каждого из сидящих за карточным столом для любой разыгранной партии, поэтому это игра с полной информацией. Однако игроки не знают, какие карты были сброшены противником в прикуп, а также какие карты были получены при сдаче, пока они ещё не раскрыты, поэтому это игра с несовершенной информацией.

Пример игры с неполной, но совершенной информацией — «Брейн-ринг»: команды осведомлены обо всех ответах, данных соперниками в предыдущих раундах (поэтому это игра с совершенной информацией), однако обычно не знают заранее правильного ответа на вопрос текущего раунда и, стало быть, не знают, каким будет результат игры в случае тех или иных действий команд (поэтому это игра с неполной информацией).

Существуют и другие способы разделения игр на классы, но мы не будем далее углубляться в этот вопрос. Итак, наша жизнь — игра. Игра некооперативная, асимметричная, параллельная, с непостоянной суммой, с неполной и несовершенной информацией.

3.1 Ним и ниматрон

При игре в ним два игрока по очереди берут предметы, разложенные на несколько кучек (обычно на три). За один ход можно взять любое количество предметов (больше нуля) из любой кучки. Выигрывает игрок, взявший последний предмет. В древние времена, когда люди ещё пользовались спичками, для игры в ним обычно использовали кучки из спичек. В принципе, для нима подходят любые предметы — монетки, камешки, пуговицы, золотые слитки 999-й пробы. Для особых ценителей существуют даже специальные наборы для игры в ним, но выпускают их на всякий случай ограниченными сериями.