Парринг-машина

[HiveTyrant]

Добрый день,

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

Так вот, тема о том, что я могу приоткрыть завесу тайн написания этих программ. С разбором алгоритма (альфа-бета отсечения). В конце будет программа, которая может прогнозировать игры. Народу интересна данная тема? :rolleyes:

Начнем с простого. Рассмотрим сам алгоритм. Проще всего его воспринять из английской википедии.

https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning

Суть его невероятно проста. Есть дерево, которое описывает все возможные варианты паррингов. В конечном итоге, у каждой вершины есть два обязательных значения. Альфа и Бета.

• Альфа - текущее максимальное значение, меньше которого игрок максимизации (обычно, это вы) никогда не выберет
  
• Бета - текущее минимальное значение, меньше которого игрок минимизации(обычно, это противник) никогда не выберет
  

Изначально, Альфа и Бета равны -∞, +∞ соответственно, но при расчете паррингов достаточно -1 и 200 000 соответственно, так как всегда любое значение суммы игр будет больше -1 и меньше 200 000.

Альфа и Бета изменяются по следующим формулам:

Альфа = max(Альфа , Оценка) - для уровня максимизации.

Бета = min(Бета , Оценка) - для уровня минимизации.

Оценка, конечно, суммируется по мере углубления к корню дерева.

А дальше все просто. Если вдруг в какой-то момент альфа становится больше беты, то дальше можно не считать.

"Красивая картинка"

Надеюсь, алгоритм понятен всем?

Изменено 22 марта, 2016 пользователем HiveTyrant

[PeakMind]

сам алгоритм прост и называется перебор. вопрос в том как оценивать "мувы"?

[HiveTyrant]

сам алгоритм прост и называется перебор. вопрос в том как оценивать "мувы"?

Лалка. Перебор слишком медленный. Меня лично напрягает ситуация, когда противники 15 минут ждут решения машины.

[PeakMind]

альфа-бета отсечение это эвристика для рекурсивного перебора, причем с не очень большим процентом отсечений.

если в кратце о ней то если мы в какой то момент получили оценку хуже чем получали раньше то эта ветка перебора - тупик.

если говорить за алгоритм, то тут идеально это динамика.

ну и количество возможных парингов не настолько велико что бы долго перебирать все варианты.

мне более интересно как понять какой из двух лучше

Изменено 22 марта, 2016 пользователем PeakMind

[Warpmanъ]

есть два атакера, на одном гравы точены на другом кава...кхм...недокормлена

вопрос в том что враг может выбрать ниже оптимума. чтобы получить оптимум в следующем шаге, оставив себе там выбор альфы.

[HiveTyrant]

есть два атакера, на одном гравы точены на другом кава...кхм...недокормлена

вопрос в том что враг может выбрать ниже оптимума. чтобы получить оптимум в следующем шаге, оставив себе там выбор альфы.

Подниматься с листьев к корню?

[Pururu]

HiveTyrant, яннп, но продолжайте. Надо же университетскую программу вспоминать изредка ;j

[HiveTyrant]

Теперь поговорим о том, как кто выбирает атакера/дефендера. То есть, о схеме составления паррингов.

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

Ссылка на рульпак ЕТС

Что нам дает это обстоятельство? Дает нам возможность составить алгоритм! Он не имеет ничего сложного. Суть всего этого процесса простая - взять как можно больше очков СУММАРНО, и отдать как можно меньше очков СУММАРНО. Это значит, что иногда придется жертвовать в данный момент одним хорошим паррингом, чтобы потом взять два! При составлении паррингов "на глазок" такой стратегии сложно придерживаться.

Теперь встает вопрос - как переложить текущую систему паррингов на алгоритм альфа-бета отсечения?

В принципе, это не так уж и сложно.

В первую очередь нам надо составить дерево паррингов. Что это такое? Это огромный граф, где описываются возможные варианты выборов на данном шаге. Так как В одном туре подразумевается 3 шага со стороны каждого игрока, то глубина дерева будет 8*3, где 8 - количество игроков в команде.

Можно глубину уменьшить до 8*3-1, так как в случае, когда остается последний защитник и последний атакер, то шага, когда выбирается два атакера - нет, так как в команде просто не набирается двух атакеров. На самом деле, глубина еще меньше, 8*3-2, так как на последнем шаге выбор из атакеров тоже не слишком большой, выделять выбор в отдельную фазу не имеет смысла. Можно выбирать сразу пару деф-атакер.

Теперь рассмотрим каждый игровой тур внимательно. Можно, очевидно, выделить три шага, как говорилось ранее.

• Выбор из множества всех доступных игроков защитника
  
• Выбор двух игроков на роль атакера
  
• Выбор из двух атакеров лучшего
  

Как же нам выбрать лучшую ветку?

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

Когда мы выбираем атакера на шаге 3, то мы уже знаем защитника из шага 1. А значит мы можем говорить о том, что знаем оценку. Значит в первую очередь, мы должны строить дерево следующим образом - оно должно быть построено в хронологическом порядке (то есть спускаемся с первого защитника до последнего атакера, чтобы знать дефендера всегда), но считать сумму мы должны с листьев. И медленно поднимаясь от листьев до корня, мы будем иметь конечную сумму (на самом деле нет, а только лучшую последовательность, но зная ее, мы легко восстановим сумму).

Таким образом, все что нам - это расписать то, как мы получаем текущее значение суммы игр на каждом шаге.

Изменено 23 марта, 2016 пользователем HiveTyrant

[Daddymoroz]

ХТ, ты сразу скажи, когда в народ запустишь программу и капитаны станут ненужны? :D

[Тюрьминатор]

Это все клево, но вся эта стройная система идет лесом, ибо почти всегда найдется тот, кто оценки поставит от балды и таким образом порушит все расчеты автоматом.

[stalk37]

Это все клево, но вся эта стройная система идет лесом, ибо почти всегда найдется тот, кто оценки поставит от балды и таким образом порушит все расчеты автоматом.

Человеческий фактор, такое всегда лечиться инструкциями и [ой!]юлями.

[HiveTyrant]

ХТ, ты сразу скажи, когда в народ запустишь программу и капитаны станут ненужны? :D

Я пытаюсь намекнуть капитанам - платите деньги старому еврею, и программа может оказаться забагованная :D

Это все клево, но вся эта стройная система идет лесом, ибо почти всегда найдется тот, кто оценки поставит от балды и таким образом порушит все расчеты автоматом.

Это будет следующий шаг на самом деле. Надо просто народ подготовить.

Да и гешефт будет жирнее, когда все команды перейдут на данную систему. :rolleyes:

[WarMaster6]

то есть мы подбираем пары методом графов, не так ли?

[HiveTyrant]

то есть мы подбираем пары методом графов, не так ли?

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