Теория игр - Игра для двоих и игра Выжова, скрытое золотое сечение

Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания

СегодняТемы алгоритмов и структур данныхВ статье 25 мы продолжаем тему теории игр.

В предыдущей статье мы узнали о простейшей игре Bash, сегодня рассмотрим еще одну классическую игровую модель —Выжовская игра. Теория игр чем-то похожа на машинное обучение: математики моделируют сцену и разрабатывают несколько классических моделей. Затем, столкнувшись с конкретной проблемой, мы проводим глубокий анализ проблемы и находим наиболее подходящее модельное приложение для ее решения.

каменная проблема

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

Мы просто проанализируем его, мы найдемНекоторые ситуации являются беспроигрышными. Например (0, 0), например (1, 2). Давайте кратко проанализируем (1, 2), есть 4 стратегии для первой руки, сначала он может взять первую стопку, затем вторая рука может взять вторую стопку, очевидно, вторая рука выигрывает. Он также может взять 1 во второй стопке, тогда останется (1, 1), и вторая рука будет взята одновременно, и вторая рука также выиграет. Третий заключается в том, что он берет вторую стопку, вторая рука может взять первую стопку, и вторая рука выигрывает. Четвертый – он берет по одному из первой стопки и второй стопки одновременно, в это время во второй стопке остается одна, и выигрывает второй игрок.

Ну, этиКаково правило между неизбежными состояниями?? Как найти этот закон и найти решение?

анализировать

Мы можем перечислить несколько обязательных состояний: (0, 0), (1, 2), (3, 5), (4, 7)...

Глядя на эти состояния, мы можем найти два закона. Мы предполагаем, что k-е обязательное состояние отказа в порядке от малого к большому равно (x, y) и x Разница между двумя числами в состоянии обязательного отказа увеличивается., который также показывает, что разница в каждом состоянии обязательного отказа различна.

На самом деле это легко доказать, воспользуемся методом доказательства от противного, предполагая, что (a, a+k), (b, b+k) все состояния должны не сработать и a Нет двух равных позиций, которые должны проиграть.

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

Красим все точки must-fail по вышеописанной логике, и можем получить следующую картину:

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

На данный момент мы очень близки к решению, и теперь остается вопрос, как мы можем быстро судить, составляют ли они проигрышную ситуацию на основе значений x и y? То есть можем ли мынайти формулу общего члена, для k-й проигрышной позиции ее координаты равны ( x_k, y_k ) Шерстяная ткань?

решать

Чтобы записать формулу общего члена, нам нужно ввестиТеорема Бетти.

Пусть a и b — два положительных иррациональных числа, и $\frac{1}{a} + \frac{1}{b} = 1$

Помните P={[], $n \in N^+$ }, Q={[], $n \in N^+$ },но $P \cap Q = \varnothing$ , $P\cup Q = N^+$

доказывать

$P\cap Q = \varnothing$

Наоборот, мы предполагаем, что существует $k \in P$ и $k \in Q$ , то есть существует натуральное число n и m удовлетворяет условию k

Это: $\frac{n}{k} > \frac{1}{a} > \frac{n}{k+1}, \frac{m}{k} > \frac{1}{b} > \frac{m}{k+1}$ Сложение двух формул дает: $\frac{m+n}{k} > 1 > \frac{m+n}{k}$

который k < n+m < k+ 1 , что противоречит тому факту, что n, m и k — все положительные целые числа.

$P \cup Q = N^+$

опровергнуть, предполагая, что существует $k \notin P$ и $k \notin Q$ , то есть существует натуральное число n такое, что m удовлетворяет условию an < k < a(n+1)-1, bm < k < b(m+1)-1

который: $\frac{n}{k} < \frac{1}{a} < \frac{n+1}{k+1}, \frac{m}{k} < \frac{1}{b} < \frac{m+1}{k+1}$

Сложив вместе, можно получить: $\frac{m+n}{k} < 1 < \frac{n+m+2}{k+1}$

То есть: n + m

Мы приложили немало усилий, чтобы доказать, что теорема Бетти предназначена только для использования, потому что мы нашлиОбщий термин состояния обязательного отказа очень похож на последовательность теоремы Бетти.. С тем же успехом мы могли бы предположить, что существуют такие a, b, которые одновременно удовлетворяют свойствам теоремы Бетти и находятся в состоянии обязательного отказа:

[an] + n = [bn], \frac{1}{a} + \frac{1}{b} = 1

Замените, чтобы получить:

Решив это уравнение, получим $a = \frac{1 + \sqrt{5}}{2}\approx 1.618$ , ученики, знакомые с математикой, могут увидеть это через некоторое время, это число равнозолотое сечениеСлучайность ли это или есть более глубокая причина?

По крайней мере, найдя a, мы можем очень просто судить о состоянии must-fail:

import math
def lose_or_win(a, b):
    if a > b:
        a, b = b, a
    
    k = b - a
    # 根据差值k求出第k个必败状态，判断是否相等
    return not (int(k * (math.sqrt(5)+1) / 2)) == a

Суммировать

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

Кроме того, в процессе вывода мы использовали теорему Бетти.Хотя вывод и доказательство этой теоремы не представляет сложности, если вы не специалист по математике, возможно, вы никогда к ней не прикасались. На самом деле это отражает тесную связь между теорией игр и математикой. Казалось бы, простой вопрос привел к ряду умопомрачительных выводов и доказательств. Как насчет этого? Вам все еще нравится?

На этом сегодняшняя статья заканчивается. Если вам понравилась эта статья, если можете, пожалуйстаобращать внимание, подбодрите меня и облегчите доступ к другим статьям.