Логические игры

Не так давно я захотел написать свой шахматный движок. На удивление в Интернете нашлось не так много хороших статей на эту тему. Были статьи с довольно слабыми программами, многие из которых даже умудрялись пропускать некоторые важные правила. А были статьи с хорошими программами (некоторые из них были даже чуть лучше чем получилось у меня в итоге), но там авторы рассказывали лишь основные идеи, пропуская подробности, из-за чего написать что-то свое по таким статьям было проблематично. Поэтому после написания своей программы, я решил написать статью, дабы облегчить жизнь интересующимся в данной теме. Я не претендую на лучшую шахматную программу или на чистейший код, но эта статья будет хорошим и легким началом для тех, кто хочет написать что-то свое.

12 сентября 2024 года OpenAI представила новую модель OpenAI o1-preview - первую модель, которая по утверждению создателей умеет "рассуждать".

Я решил посмотреть, насколько хорошо она умеет отвечать на вопросы из игры "Что? Где? Когда?"

Введение

Парадокс двух детей Вы встретили на прогулке соседей с сыном. Известно, что у них двое детей. Какова вероятность, что второй — тоже мальчик?

Казалось бы, детская задачка, где нужно просто “вспомнить формулу”, но всё не так однозначно. Если задать этот вопрос прохожему, он, скорее всего, скажет ½. Преподаватель математики, возможно, ответит ⅓. Кто из них прав?

В каком-то смысле, правы оба. Просто каждый представляют себе свой способ, как была получена информация о ребёнке. На самом деле это и есть условие задачи. Только скрытое. 

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

Парадоксы, о которых пойдет речь, — не логические ошибки. Это ситуации, в которых само понятие вероятности начинает колебаться. Они не ломают теорию, но обнажают, где она требует особенной осторожности. Именно в таких местах теория вероятностей становится особенно странной — и особенно интересной.

В этой статье — три таких истории. В первой один и тот же факт даёт разные вероятности, если по-разному устроено наблюдение. Во второй один и тот же объект может быть “случайным” множеством способов. А в третьей невозможно придумать, как сделать задачу математически строгой.

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

А пока — вернёмся к соседям с мальчиком. Разберемся, почему эта задачка не так проста, как кажется на первый взгляд.

Уровни сложности чтения

• Я слишком молод, чтобы думать

  
  
  • Введение и правила игры
  • Как они это делают?
  • Матрица инцидентности для игры Доббль
  • Каких двух карточек не хватает в комплекте игры?
  • Почему в игре на 2 карточки меньше максимально возможного количества?
  • Благодарности
  
  

• Сделай мне умно

  
  
  • Введение и правила игры
  • Как они это делают?
  • При чём тут карточки?
  • Проективные плоскости малых порядков
  • Матрица инцидентности для игры Доббль
  • Каких двух карточек не хватает в комплекте игры?
  • Почему в игре на 2 карточки меньше максимально возможного количества?
  • Благодарности
  
  

• Кошмар

  
  
  • Введение и правила игры
  • Как они это делают?
  • Конечная геометрия для грудничков
  • При чём тут карточки?
  • Проективные плоскости малых порядков
  • Как построить проективную плоскость?
  • Матрица инцидентности для игры Доббль
  • Каких двух карточек не хватает в комплекте игры?
  • Почему в игре на 2 карточки меньше максимально возможного количества?
  • Благодарности
  
  

Введение и правила игры

Несколько лет назад я купил игру Доббль (Dobble, оригинальное название “Spot It!”). Это очень простая, быстрая и весёлая игра, которую я считаю одной из лучших настольных игр вообще.

Основную часть генератора лабиринтов написал какой-то уволившийся торчок. Я связался с ним, чтобы выяснить, как его алгоритм работал. Он ответил, что придумал этот алгоритм, когда был вусмерть накурен и вдобавок пьян, что написал его сразу на ассемблере прежде чем вырубился, а потом даже близко не мог вспомнить, в чем его алгоритм состоял.

Многие из вас, я уверен, слышали о теории игр в какой-то момент своей жизни. Если вы хотите выглядеть умным и произвести впечатление на свою девушку — просто упомяните «игру с нулевой суммой» или «эволюционную стратегию», и ваши шансы отвести её домой сегодня вечером только что подскочили на 50%. Или вы можете использовать теорию игр, чтобы принимать решения в инвестировании своих денег (чтобы их полностью потерять и разориться) или, например решая, на какой девушке жениться (что также очень вероятно вас разорит). Как видите, это очень полезная теория.

Чтобы казаться умным - достаточно выучить эти пару выражений, но чтобы на самом деле что-то понимать - придется разобраться. Оказывается, это не так уж сложно и довольно интересно. Давайте посмотрим.

Я играл в компьютерные игры с 1995 года. И хотя в детстве я не раз засиживался за Civilization или TTD, я не могу считать себя заядлым геймером. За последние десять лет большую часть редкого игрового времени я потратил на Factorio. Более того, я закончил несколько франшиз, чисто для галочки.

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

Почти в каждой карточной игре после партии нужно перетасовать карты. Пока я тасую карты, передо мной всегда возникает вопрос: "Уже хватит?" Вопрос серьезный — лишнее время тратить не хочется, а играть на заряженной колоде тоже не в кайф.

В статье разберемся с ситуацией.