Brain Dump

P.S.: Про имбаланстность первого ходящего в таверне:
http://daily.heroeswm.ru/bu.php?i=y94ldtf1
Если вы будете играть бесконечно долго, то по сути всё не так страшно
правда ведь? =)
Ну вот и админ про это также думает (да-да)

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

В прошлой блог-теме я описал довольно простой scoring карт. Теперь постараемся развить идею и учесть недостатки прошлого оценщика про создании новой модели.

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

Тут какой-то скрытый текст:

Чтобы можно было искать в сообщениях по substrings.

Disclaimer

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

---

Краткая информация

• Предположительное время создания и использования: ~ 2009-2010 год (Скорее всего уже больше нигде не используется).
• Место использования: HeroesWM.ru
• Дополнительная информация: За него выписывали штрафы по 500к.
• Написан на: PHP 5(?)
• Количество файлов: 3 файла (один для debugging, один для запуска и один со всей логикой)
• Количество строчек кода с комментариями: 1056+92 = 1148 (без кода для дебага)
• Количество строчек кода без комментариев: 998+31 = 1029 (без кода для дебага)
• Комментарии (1-1029/1148)*100% = 10.36% комментариев в сорс коде. Из них половина мусор (код засунутый в комменты). Поэтому на самом деле примерно половина, т.е. 5%.
• Количество функций: 14
• Количество классов: 0
• Доступность: Очень сложная (искал год точно). Слышал, что стоит 50$. Достался бесплатно где-то год назад (спасибо большое автору).
• Язык: русский
• Автор: Не разглашается

Примечания

• код сложно читать (мало комментатриев) (дисклайк)
• нет классов (дисклайк)
• забагован (undefined globals, $foo[лол], ...) (дисклайк)
• на русском - названия переменных русофицированны - Primer: неужели вместо "ocenka_list" нельзя написать "cards_scoring_list"? (dislajk)
• почти всё в одном файле (дисклайк)
• hardcoded card scoring (but with dynamic elements) (дисклайк)
• без понятия как тестировать его на своём симуляторе. придётся сначала дебажить и настраивать. Легче наверное просто взять идею и переписать например на питоне.
• Indentation: Использует 4 пробела (лайк)
• Интеллектуальная сложность: низкая (крайне субьективно)

---

Cards defintions

• Строчек кода: 134
• Отдельный файл: нет
• Как работают сложные эффекты: eval("PHP CODE")
• Примечания: нет карт с номерами 100, 101 (сбросить карту, играем снова). Были введены в 2010 году (Обновление таверны).

---

Оценка карт

• Строчек кода: 216
• Отдельный файл: нет
• Примечания: горы if + else + "xx?aa:bb" + switch-case

Оценка карты проходит в нескольких этапах:
1. Проверяем карту напрямую через её ID
2. Проверка на победу сразу (почему это вообще сразу не проверяется?) (без ID карты)
3. Бонусы за ресурсы (без ID карты)
4. Бонусы за строения (без ID карты)
5. Бонусы за наши башни и стены (без ID карты)
6. Бонусы за вражескую башню и стены (без ID карты)
7. Бонусы за перевес строений (без ID карты)

Какой-либо оценки при победе через ресурсы я не нашёл.

Устроено так: Есть функция-оценщик карты. Оценка инициализируется 0. После этого куча if-ов (см. колонка Условие), где к оценке либо что-то постоянно прибавляется, либо вычитается. Под конец выдаётся оценка. Только в трёх случаях можно выйти преждевременно (см. колонка Описание) из функции с оценкой 999 или -999 (при победе либо при проигрыше).

Если в таблице (см. колонка Название) указано 1,2,3,... - это последовательность кода. Код разобран сверху вниз.

Функия-оценщик получает 4 параметра:
• _me (array)
• _enemy (array)
• turn (integer)
• card_id (integer)
А также использует 3 глобальные переменные:
• game (array)
• me (array)
• enemy (array)

Примечание
me, _me, enemy, _enemy - это 4 разных массива с данными игроков, чтобы узнать эффект карты на данный момент и дать карте какую-то оценку основанной на этой разнице

Симуляция

Функция оценки карт запрашивается в двух местах в коде - всё в одной функции, которая отвечает за конечный выбор карты. Параметров она никаких не получает, но использует следующие глобальные переменные:
• me (array: мои данные)
• enemy (array: данные противника)
• game (array: игровые данные)
• scoring_list (array: список с оценкой карт)

После этого происходит следующее (почти нет комментариев в коде - сложно читать):
1. Иницализируем переменные: best_ocenka=-9999999 (-Inf), best=array(), combinations=array() (6-7 карт на моей руке)
2. Инициализируем список с оценками оценкой -999 для каждой карты (6-7 карт на моей руке)
3. Иницализируем список вариантов и собираем комбинации с максимальной глубиной: 3-1 = 2
4. Проверка всех переборов (так и написано в комментарии в коде - это самая большая часть этой функции). Здесь автор симулирует игру картой и потом в оценщике карты проверяет что именно даёт данная карта (см. таблицы ниже той где идёт проверка карт через ID). Т.е. оценщик судит уже по реальным эффектам
5. Под конец идёт сравнение оценки с лучшими оценками и выбирается карта с самой лучшей оценкой.

Строчек кода в функции выборки карт: 181
Примечания: 4 отдельных блока с for-loops.
Количество дополнительных внутренних for/foreach-loops в этих блоках:
1. 0x (в сумме 1x) (инициализация)
2. 0x (в сумме 1x) (инициализация)
3. 2x (в сумме 3x) (собираем комбинации карт)
4. 1x (в сумме 2x) (симуляция игры)

• Максимальная оценка: +999
• Минимальная оценка: -999
• Оценка, если башню врага можно разрушить за один ход: +999
• Оценка, если можно построить свою башню по максимум за один ход: +999
• Оценка, если можно разрушить свою башню: -999

---

1 - Оценка карт напрямую

В колонке условие - используется if statement. Для читабельности все if-ы убраны.
В if суммируется scoring, т.е. так: "score += 50".

---

2 - Проверка на победу сразу

В if-else суммируется scoring, т.е. так: "score += (me["руда"] ......".
Здесь более-менее динамичный scoring.

---

3 - Бонусы за ресурсы

В if-else суммируется scoring, т.е. так: "score += (me["руда"] ......".
Здесь более-менее динамичный scoring.

---

4 - Бонусы за строения

В if-else суммируется scoring, т.е. так: "score += (me["руда"] ......".
Здесь более-менее динамичный scoring.

---

5+6 - Бонусы за наши/вражеские башни и стены

В if-else суммируется scoring, т.е. так: "score += (me["руда"] ......".
Здесь более-менее динамичный scoring.

---

7 - Бонусы за перевес строений

В if-else суммируется scoring, т.е. так: "score += (me["руда"] ......".
Здесь более-менее динамичный scoring.

Примечания
• Для читабельности убрал знаки "$" и ";"
• ocen = оценка = scoring

---

Примечния к оценкам из первой таблицы

В первой таблице идёт проверка карт через ID.

Бракованная руда: Везде только отрицательный скоринг. Совершенно не учитывается ситуация, где мы на грани победить через постройку/разрушение башни, а противник через фарм ресурсов. В таких случаях есть смысл украсть у него руду. Или другой пример: Если у нас 0 шахт и 0 руды, то можно смело пользоваться этой картой, если у противника например где-то 10 руды и например 1-2 шахты.

Аналогично с картой Землятресение.

Вот например с картой Обвал рудника такие ситуации учтены.

Паритет: Даёт -100 если у нас монастырь выше чем у противника. Значит, что этой картой не играем - можно и сбросить. Тут как с картой сдвиг - если есть возможностъ лучше её оставить, чтобы противнику не так просто было бы уравнять монастыри. К тому же она может пригодится.

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

И похожии ситуации с другими картами.

Автор бота не учёл какой-то дополнительный scoring для сброса карт. Нужна не только оценка на то что бы сыграть картой, а ещё на то какую карту лучше оставить. Там всё решается через один тип оценки. Например снова посмотрим на карту сдвиг, если наша стена выше чем у противника, то оценка будет -100, т.е. по сути это кандидат на выброс, а это довольно критично.

---

Этапы в оценщике карт

1. Проверяем карту напрямую через её ID
2. Проверка на победу сразу (почему это вообще сразу не проверяется?) (без ID карты)
3. Бонусы за ресурсы (без ID карты)
4. Бонусы за строения (без ID карты)
5. Бонусы за наши башни и стены (без ID карты)
6. Бонусы за вражескую башню и стены (без ID карты)
7. Бонусы за перевес строений (без ID карты)

Тут я согласен, довольно неплохо продуманно.

---

Проблемы оценки карт

Scoring карт отчасти динамичный. Но во многих местах значения фиксированны рукой создателя.

Так как всё добавляется в ручную, то было пропущено много случаев (1 - Оценка карт напрямую), где можно было бы эксплоитить какие-то специальные эффекты карт. Примеры:
• Steal technology VS Big vein - Какая карта когда выгоднее?
• Arcomage. Профитабельное переливание ресурсов и постройка заводов.
• Arcomage. Finding exploitable cards & maximizing cards' effects
• Arcomage. Maximal effects. Lookup table. (max. сгенерированно автоматически)
• Arcomage. Minimal effects. Lookup table. (min. сгенерированно автоматически)

Всё очень ригидно и малоподвижно, т.к. оценки делались в ручную, а не динамично.

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

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

---

Симуляция

Честно говоря я не сразу увидел, что идёт симуляция игры. А это уже что-то интересное, т.к. всё-таки в конечном итоге есть что-то наподобие динамической оценки карт, хотя и с самим оценщиком карт я далеко не согласен, т.к. слишком много интересных моментов пропущено.
Однако из кода не совсем ясно насколько сильно развит концепт карточных комбинаций, т.е. например:
1. мой ход
2. ход противника
3. мой ход (играем снова)
4. мой ход
5. ход противника
6. мой ход

1-3-4-6 например была какая-то тактика, которую мы успешно смогли реализовать (1-3-4-6 в данном случае комбинация из карт, растянутая на несколько независимых ходов).

Насколько я понял такого там нет.

---

Вердикт

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

Если у кого есть интерес написать бота и посоревноваться со мной (ещё раз - я не про ГВД. Я лишь пользуюсь здешним блогом и собираю статистику. - На этом и всё) - пишите!

Правила

Ввод данных через JSON (в текстовом файле через командную строку)
Выход: ID карты и action: "turn" / "drop", тоже в консоль

Возможно когда будет проработанна более менее концепция оценки карт и доделаю своего бота (не для ГВД).

---

Карты

• Все карты из таверны. оффициальные ID карт. (english)
• Все карты из таверны. (на русском)

http://www.sbgames.org/sbgames2016/downloads/anais/156888.pdf


[15] I. Millington. Artificial  intelligence  for  games. Morgan  Kaufmann/Elsevier, Burlington, MA, 2009.
[16] I. Millington. Artificial Intelligence for Games. CRC Press, 2009.
[20] N. Sephton, P. I. Cowling, E. J. Powley, and N. H. Slaven.  Heuristic move pruning in monte carlo tree search for the strategic card game lords of war.  In IEEE Conference on Computational Intelligence and Games (CIG), pages 1–7, 2014.
[24] C. Ward and P. Cowling. Monte carlo search applied to card selection in magic: The gathering.  In IEEE Symposium on Computational Intelligence and Games (CIG), pages 9–16, 2009.

---

• [15] http://lecturer.ukdw.ac.id/~mahas/dossier/gameng_AIFG.pdf
• [20] http://orangehelicopter.com/academic/papers/cig2014-low-heuristics.pdf
• [24] Monte Carlo search applied to card selection in Magic The Gathering (pdf)

---

• Ensemble Determinization in Monte Carlo Tree Search for the Imperfect Information Card Game Magic: The Gathering
• Monte-Carlo Tree Search for Simulation-based Strategy Analysis

Интересно: I wrote a master's thesis on effective Hearthstone AI (reddit), (PDF)

Когда будет время постараюсь сделать обзор этой мастер-работы

google: "hearthstone ai card score"

Спасибо ред-анту за идею :)

Ситуация такая
номер хода: Игрок
1: бот
2: Я
3: бот

Юзерскрипт видит ответ от 1 и 3, а результат хода 2 "сьедается", т.к. бот в турнире слишком быстро играет.

- Нужен game state перед ходом 2
- и нужен game state после хода 3

game state после хода 2 и перед ходом 3 теряется
сыграл бот - получили последние данные
потом не получили данные когда сыграли картой
получили данные после того как бот снова сыграл

---

У нас есть наши карты после хода #1 и после хода #3. Пример:
1: [1,2,3,4,5]
3: [1,2,3,4,8]
Значит в ходе номер 2 мы сыграли картой 5 и получили карту 8.

Теперь 2 варианта (юзерскрипт не знает какой из них правильный)

1) Картой 5 мы играли
Симулируем прирост ресурсов и игру картой 5, использую game state после 1 -> получаем game state 2 (v1)

2) Карту 5 мы сбросили
Симулируем прирост ресурсов и сброс карты -> получаем game state 2 (v2)

После этого симулируем игру картой бота в 3 и проверяем какой из двух вариантов даёт game state как после 3 (game state нужен для других вещей).

// fixed ;)

Для начала рассмотрим несколько желаемых качеств и утверждений, которыми должна обладать оценка карт и комбинаций или какой-то ИИ для аркомага.

Этот список пока ещё не полный и будет пополнятся.

- если карта или комбинация из карт даёт в течении периода хождения одного персонажа 100%-ую победу, то score (оценка) должен быть максимальный
- если даёт именно нам поражение, то score должен быть 0-вым или бесконечно негативным
- нужно не давать сопернику победить за один ход
- если у нас нет карты сдвиг, то нужно иметь стену всегда чуть-чуть выше чем у противника (т.е. всегда выше нуля), но не настолько высокой, чтобы для него было выгодно поменять стены местами. Зачастую выгодно иметь стену выше чем у противника.
- Если комбинация карт состоит из нескольких раздельных ходов, где играем мы (1.1), потом противник (2.1), потом снова мы(1.2), потом снова противник (2.2), то комбинация не должна быть длиннее чем 2-3 хода (и ходами притивника между ними). Также следует давать какой-то мелкий штраф (или может даже бонус?) за то что ходим в течении нескольких ходов и преследуем какую-то цель
- Играть эффициентно, стараться например использовать карты, где можно максимировать выгоду в зависимости от ситуации или находить и использовать по мере надобности undervalued cards (про это я писал в теме с least squares)
- стараться в разумных рамках фармить ресурсы (resources) и строить предприятия (facilities)
- scoring (оценка) карт в зависимости от ситуации на столе
- scoring (оценка) для игровой ситуации вообщем (руда, мана, шахты, стены, башни, ...)

Спорные идеи
- score(play card) > score(drop card) (для большинства ситуаций)
- score(direct damage) > score(tower damage)
- score(direct damage) > score(wall damage)

Можно выделить 3 типа урона среди карт
- карты, где урон всегда только по башне: tower damage
- карты, где урон всегда только по стене: wall damage
- карты, где урон без всяких условий - им можно нанести урон и башне и стене, назовём его: direct damage
Отчасти об этом я писал уже здесь: Cards damage (conditional cards+exploitable effects)

---

Для того чтобы начать вообще с чего-либо начнём с очень простой модели.

Рассмотрим какими способами можно победить в аркомаге напрямую используя карты:
1. победа через постройку башни (T1 >= MAX, где T1 это наша башня (мы игрок #1), а MAX это высота башни для победы)
2. победа через разрушение башни противника (T2 <= 0, где T2 это башня противника (игрок #2))
3. победа через фарм ресурсов (RES1 >= MAX, где RES1 это наши ресурсы, а MAX количество ресурсов нужное для победы)

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

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

Можно представить себе 3 типа победы как шкалы в системе координат.
X: "Т-2-0" - разрушение башни противника
Y: "T-1-MAX" - постройка нашей башни
Z: "RES-1-MAX" - накопление ресурсов

Графически можно представить себе примерно вот так


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

Естественно наша модель пока хромает, как минимум по следующим пунктам:
- не учитывается стена, а она защищает башню от типа урона direct damage
- не учитывается постройка или разрушение предприятий (facilities)
- модель не видит напрямую комбинации из карт. нам придётся суммировать эффекты комбинаций и стоимость (комбинация из карт это по сути наша стратегия) и считать как одну карту, но в принципе это не настолько большая проблема, как два пункта выше.

Теперь постараемся описать нашу идею математически, т.е. построить какой-то простейший scoring на основе этой идеи.



Идея такая:
Мы смотрим какой из эффектов даёт больший вклад в победу какого-либо типа. Максимальный эффект и определяет оценку карты.

Результат каждой отдельной оценки всегда между 0 и 1.
Если score равен 1, это значит, что карта приводит к победе.

Вспомогательные функции h и g


Тета это какой-либо threshold (порог), который мы задаём. Например макс. башня или макс. ресурсы.


Тета 1 и Тета 2 это два каких-либо порога.

Теперь рассмотрим каждый случай раздельно (scoring для каждого типа победы):

1. Победа через разрушение башни пртивника (X)



Тета 1 в данном случае является 0, т.е. если карта делает так, что мы может разрушить башню противника (и её высота будет равнятся нулю или ниже).
Тета 2 в данном случае является высотой башни нужной для победы. Напомню, что нам нужен score между 0 и 1.

Пример:



Получаем score 0.2, при этом 40 это высота башни после применения карты.
Наверное лучше было бы использовать разницу двух оценок: Высота башни до применения карты и после. Разница и будет оценкой.

2. Победа через постройку нашей башни (Y)



Тета в данном случае является башней нужной для победы (Например в столице 50).

3. Победа через фарм ресурсов (Z)



Z состоит из трёх компонентов: ore, mana, stacks (руда, мана, отряды).
Тета это количество ресурсов нужных для победы. Т.к. для победы нужно собрать каждого вида ресурса по максимуму, то просчитываем отдельный score для руды, маны и отрядов.

---

Примечания
- Ситуация на столе имплицирует и scoring какой-то карты в данный момент
- Недостатки данного типа оценки описаны наверху (стена и предприятия не учитываются). Стена защищает башню, но не во всех случаях. А вот ресурсы нужны всегда, поэтому нужно строить "предприятия" (шахты, монастыри, казармы). Т.к. копить до макс.ресурсов очень долго, то оценка решит, что лучше либо разрушить башню противнику либо построить свою. И будет считать что не надо фармить ресурсы вообще. В конце концов ресурсы закончатся и будем в тупике.
- Можно подумать ещё над weighted scoring, т.к. распределение эффектов у карт разное. Например много карт для постройки башни.
- Можно подумать сделать вторую систему координат для противника
- Можно экспериментировать с подобными системами координат и оценками для других вещей: Например для трёв видов ресурсов (X: руда, Y: мана, Z: отряды), чтобы задать приоритет фарма, при этом можно сделать плавающий порог. и т.д.

• Альтернативные издержки (wikipedia)

• Opportunity cost (wikipedia)

В своё время предлагали как вариант оценщика вот такое.
На досуге нужно будет вчитаться и понять  что это и обдумать насколько имеет смысл.
Может вообще глупость какая...

Везде пишу и пишу про оценку карт через least squares
На самом деле least squares делает следующее
Смотрим на эффекты какой-то карты и смотрим сколько карта стоит
Потом с помощью least squares считаем теоретическую стоимость карты и сравниваем её с её реальной стоимостью.
Так находим слишком дорогие или слишком дешёвые карты.
О качестве и по сути оценке самой карты это ничего не говорит.

Есть эффекты, которые зависят от ситуации на столе
Поэтому можно считать теоретическую стоимость карты через least squares каждый ход
В таких случаях ценность карты может например поднятся.
Т.е. вроде динамическая оценка стоимости, а не самой карты.

Типо если у врага карта сдвиг, а у меня карта Сердце дракона (+20 к стене, +8 к башне), но стена моя и так на 10 выше чем у противника (и до победы через постройку макс-башни ещё далеко), то least squares скажет, что карта дешёвая, но не факт что ей сейчас вообще нужно играть..  

Но имеет ли смысл сыграть вообще этой картой и как оценить её в плане ситуации - тут как мне кажется least squares совершенно не подходит.  
Ну будет таким образом теоретическая оценка стоимости. А не оценка самой карты. - Ну и что?

А жаль... :(

Я не думаю что какой-то оценщик карт будет настолько прост как least sqaures - без внесения своих личных фиксированных данных, как я видел в других ботах - такое не сложно сделать - примерно прикинуть что где когда важнее и оценить. Просто и надёжно, но не совсем качественно как мне кажется.
Глупых ботов по началу писать весело, но всё же быстро надоедает.

К тому же одной только оценки какой-то выборочной карты мало. Она не будет учитывать комбинации. Т.е. помимо оценки карт нужна оценка комбинаций, которая будет сравнивать эффект и карт и комбинаций наравне.
А вот стоимость комбинаций можно посчитать методом наименьших квадратов. И сравнить различные комбианции в плане сумамрной стоимости.

least squares
• https://elie.net/blog/hearthstone/how-to-find-automatically-hearthstone-undervalued-cards
• Метод наименьших квадратов (wikipedia)

По правилам столицы в начале игры у каждого так:
• 2 шахты, 5 руды
• 2 монастыря, 5 маны
• 2 казармы, 5 отрядов

Когда начинается игра, у первого игрока (тот который ходит первым) по 7 ресурсов каждого типа (5+2).

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

Итак есть 7 ресурсов каждого типа.
И есть 102 карты.

Не сложно посмотреть, что всего 62 карты со стоимостью <= 7
62/102*100% = 60.78% от общего количества
Иными словами это и есть вероятность того что нам попадаёт карта со стоимостью <= 7 единиц ресурса.

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

Если начать выбирать какая карта хорошая, а какая нет - т.е. какой картой человек точно не будет играть в первом ходу, то естественно количество карт будет уже не 62 (со стоимостью <=7 ресурса), а намного меньше.
Вопрос как обьективно определить ценность какой-то карты в начале игры здесь пока что не рассматривается. Так для начала нужен какой-то scoring для карт на основе которого и можно будет отталкиваться.
Чтобы не усложнять рассчёты пока я не использую никакой scoring (оценку) карт, а беру карты такими как они и есть. Естественно это не совсем соответствует реальности.

Цель данной статьи в первую очередь посмотреть на возможные механизмы раздачи,

---

Представим себе, что карты раздают так:
1) сначала 6-7 карт игроку #1
2) потом из оставшихся выдают карты игроку #2

Идея: берём из колоды карту, потом мешаем, и рандомно снова выбираем карту, потом снова рандомно выбираем и так далее.

Формула

И должно действовать правило: a + b = c

У игрока #1: 6 карт на руках

Вероятность, что из них Х карт со стоимостью <= 7:
X: %
0: 0.2850532
1: 3.0297083
2: 12.8341808
3: 27.7495801
4: 32.3136557
5: 19.2224824
6: 4.5653396

У игрока #1: 7 карт на руках

Вероятность, что из них Х карт со стоимостью <= 7:
X: %
0: 0.1009563
1: 1.2886780
2: 6.7379449
3: 18.7165136
4: 29.8452515
5: 27.3319671
6: 13.3155737
7: 2.6631147

Таблица для игрока #1

Если 6 карт
E(X) = 0.002850532*0 + 0.030297083*1 + 0.128341808*2 + 0.277495801*3 + 0.323136557*4 + 0.192224824*5 + 0.045653396*6 = 3.647059 -> 3 карты
Ожидаемое число карт со стоимостью <= 7: 3 карты

Если 7 карт
E(X) = 4.254902 -> 4 карты
Ожидаемое число карт со стоимостью <= 7: 4 карты

Таблица для игрока #2

Тут всё зависит от того какие карты попались игроку #1 (а именно сколько каких).
Формула тоже немного меняется, т.к. количество доступных карт уменьшается.
Формула есть в коде в конце этой блогостатьи.


Таблица читается так:
• Первая строчка: Сколько карт у первого игрока, со стоимостью <= 7. Если у первого игрока 6 карт, то последняя колонка отпадает (перед трёмя "mean")
• Вторая строчка: Сколько карт у вас 6 или 7. "D" значит difference (разница). Эта строчка вспомогательная и является "шапкой" для строчек с данными ниже
• Предпослендяя колонка (не "D", а "7") перед трёмя колонками "mean" также значит, что у обеих игроков по 7 карт.

Количество карт (стоимость <= 7) у обеих игроков

Вывод

Если иметь 7-ую карту (золотая колода), то вероятность иметь как минимум 5 карт со стоимостью <= 7 (которыми мы сможем сыграть прямо в первом ходу), увеличивается практически в двое.

Если у вас все карты со стоимостью >7 и вы ничем не можете играть в первом своём ходу, то поздравляю! - вы невероятно везучий и выиграли в рулетке! ;)

Вердикт: Такой механизм раздачи карт маловероятен.

---

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

игрок 1 -> получает карту 1
игрок 2 -> получает карту 1
игрок 1 -> получает карту 2
игрок 2 -> получает карту 2
игрок 1 -> получает карту 3
игрок 2 -> получает карту 3
...
игрок 1 -> получает карту 6
игрок 2 -> получает карту 6
игрок 2 -> получает карту 7

У каждого игрока по 7 карт



Здесь слишком замороченные рассчёты. Нет желания считать  
Не думаю что на сервере такое используют.

Вердикт: Такой механизм раздачи карт маловероятен.

---

Самый реалистичный вариант. Спасибо ред-анту за идею. :)

Мешаем колоду. Получаем массив с рандомными числами (0...102)
Пример: 4,5,42,101,0,99,21,17,59,41,33,4,87,...
Напрямую через индекс выбираем карты первому игроку
Потом даём карты второму.

Вероятность у первого и второго игрока одинаковая.
Т.е. механизм раздачи никак не влияет - нет различия кто ходит первым или вторым.

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

$cards = range(0, 101);
shuffle($cards);
$cards_player_1 = array_slice($cards, 0, 6);
$cards_player_2 = array_slice($cards, 6, 6);

---

• О том как можно навредить противнику, который начинает игру вторым и усложнить его старт (early game), можно обговорить в другой раз. Если вредить второму игроку (украсть у него ресурсы), то количество возможных карт, которыми он сможет в этом ходу сыграть, может резко упасть.

---

Детально начальные условия и условия для победы можно посмотреть здесь:
http://www.heroeswm.ru/help.php?section=39#cards

• Все карты из таверны
• http://help.ordenmira.ru/arcomage/cards.htm (карты на русском)

---

Вариант раздачи карт #1

(Обратите внимание на количество "(с)" в его инфе. (с))

Начнём с того что во флеш я не лезу (Вообще я в флеш лезу. И не надо придумывать что там что-то сложно читать.). Нет не поймите не правильно - можно сделать мод и для флеша, но на JS всё это намного проще. К тому же причина номер 2 - что сейчас администрация переводит всё на html5. А значит особый смысл что-то делать с флешем отпадает.

Итак раз флеш без модов, то нужно использовать флеш админов. Как просто сделать прокси на JavaScript для tampermonkey, который бы перехватывал бы пакеты флеша и их модифицировал - я не знаю. Как перехватить сниффером пакеты я знаю. А писать какой то extension для бруазера или использовать дополнительно к JS-скрипту какой-то сниффер для браузера а ля tamperdata это тоже как-то не очень-то и элегантно. Extension можно, но мне не хочется. Нужно решение попроще.

А переписывать аркомаг на хтмл5 пока не состоит в моих планах.
Какуе-то работу за админов я точно за бесплатно не буду делать.
Пусть ищут дурачков в другом месте.
или "фанатов игры готовых на беззаговорочную помощь даром".
называйте как хотите.
за бриллианты это тоже как-то не серьёзно.
ну вы поняли меня :)

Итак

Проблема заключается в играх с ботом или когда противник слишком быстро играет. Нереально быстро.
Мой скрипт обновляет данные каждую секунду
Если перс или бот, или бот у перса :) играет очень очень быстро, то мой скрипт не видит часть ходов
Даже если обновлять инфу например каждую 1/10 секунды, то и то есть вероятность, что будут пропадать ходы.
Скрипт их не будет видеть
К тому же qrator может засчитать это за атаку и временно кикнуть из игры.

Пример:

Я играю в турнире против бота

1) JS: посылает запрос к серверу. Получает последнюю инфу о состоянии игры
2) Flash: жму на карту- флеш отправляет запрос к серверу. Получает последнюю инфу о состоянии игры, т.е. как сыграл я
3) Сервер: получает мою карту. бот за миллисекунды ходит картой "играем снова" и картой Х
4) JS: посылает запрос к серверу. Получает последнюю инфу о состоянии игры, но не успевает увидеть какой картой я сыграл
5) Flash: получает информацию о состоянии игры, т.е. как сыграл бот

Всё дело в каких-то десятых долях секунды, но из-за них теряются ходы в юзерскрипте.

Чтобы не делать какие-то трюки с флешем и писать какие-то extensions
можно сделать некий workaround и написать функцию, которая получит 2 состояния игры - до того как я сыграл картой и после
после этого эта функция просчитывает возможные варианты и фильтрует и выдаёт карту, которой сыграл игрок

(нужно только сохранять все состояния игры. каждый ход)

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

Но конечно есть другая сложность.
Нужно учесть всякие карты, где  есть какие-то условия или условие не сразу ясное.

Во всех ли случаях бывает ли точный ответ - ещё нужно проверить.

исходим из того что потеряли только 1 ход.
чем больше ходов теряем, тем глубже комбинаторное дерево и начинаются всякие сложности, но это и не нужно.

---

Кстати если вдруг потеряется часть хода во время того как использовали кучу карт "играем снова" за раз, то тут сервер всё-таки даёт данные этой цепочки, пишется так:

t100-d20-t101-d1-t3

t100 = action=turn card, cardID=100 (играем снова)
d20 = action=drop card, cardID=20
...

---

Скрипт находится в состоянии разработки и пока нигде не доступен.

После того как будет более-менее готовая бета-версия скрипт будет сильно обфусцирован и встроены функции антидебаггинга. круто, да?



.

.

.

.

.

И тогда я его ВАМ НАВЕРНОЕ может и дам !

1) В логе нет такой инфы о том сколько карта у какого игрока было.
2) Во время игры можно узнать например что у противника 7 карта. Но если 7ой он ни разу не играл, то можно подумать, что у него всегда их было 6.

Можно что-то ещё узнать через статистический анализ игры про размер котла (pool) и через него выйти на значение кулдауна и на количество карт у противника. Но для этого придётся играть пару сотен ходов. Это конечно глупость.

:(

Есть 2 варианта:
1) Писать какой-то скрипт и просить игроков юзать его, для сбора статистики
2) Измерить ботами

Вроде как второй вариант проще.
Заодно и можно протестировать других двоих ботов (не моих).

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

Правда в гвд есть некая сложность, что золотая колода стоит 1000 монет.
Но их по сути не сложно нафармить.

Симулятор вообще уже есть. Нет сложности его написать.
Поэтому через гвд и не особо нужно. Да и задержка будет из-за отправки пакетов через сеть. Т.е. совсем не оправданный лаг.

1. Разными алгоритмами собираем всякие комбинации и отдельные карты
2. Каждую карту и комбинацию оцениваем например через least squares (каждый ход заново)

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

---

- Arcomage. Card scoring. Game beginning. Me first.
- Arcomage. Finding exploitable cards & maximizing cards' effects.
- Arcomage. Профитабельное переливание ресурсов и постройка заводов.
- Отстройка шахт/монастырей/казарм с нуля [Tavern #007]
- http://daily.heroeswm.ru/bu.php?i=x67whaeo (min)
- http://daily.heroeswm.ru/bu.php?i=24g382i8 (max)

- http://daily.heroeswm.ru/bu.php?i=177duhho (темы ксерокса про аркомаг)

Данная статистика инспированна видео от ютубера Kripparian, который играет в игру HearthStone: [Hearthstone] The Shocking Truth Behind The Coin и обсуждает аналогичную ситуацию - насколько сильно влияет эффект того, кто начинает игру первым. Хочется этим сказать, что проблемы такого рода есть в разных играх, но в ГВД этими проблемами (в аркомаге) администрация не занимается, т.к. занята в первую очередь боями, а карты явлются лишь небольшой сторонней фичей.

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

Данные:

• на этот раз я просканировал 500.001 игру - ID: 83265888...83765888
• содержат турнирные игры. Не всегда можно определить турнирная игра или нет
• содержат игры с 1ой и бесконечной колодой
• нет возможности различить сколько карт у каждого игрока (6 или 7)
• битые ссылки заново пересканировал (в прошлый раз были такие )
• Детально начальные условия и условия для победы можно посмотреть здесь: http://www.heroeswm.ru/help.php?section=39#cards
• Пример как читается лог игры в аркомаге: http://daily.heroeswm.ru/bu.php?i=h68sulwe (если кого интересуют все детали, напишите мне лично)

---

Примечания к таблице:

• В логе есть только данные о начальной башне и стене. О начальных ресурсах нет никакой информации. Поэтому районы: Rogues' Wood, Shining Spring, ... Crystal Garden собраны вместе
• В анализе побед игры с ничьёй (через таймаут) и победа через таймаут не учитывались
• В анализе ходов учитывалась и ничья
• T start: начальная башня (T=tower=башня)
• W start: начальная стена (W=wall=стена)
• Шах: начальное количество шахт
• Мон: начальные количество монастырей
• Каз: начальное количество казарм
• "won first": % побед у тех игроков, которые ходили первыми
• "won second": % побед у тех игроков, которые ходили вторыми
• "Diff": разница % побед между ходящим первым и вторым (т.е. перекос, имбаланстность)
• T>=MAX: (T=tower=башня), победа через постройку башни
• T<=0: победа через разрушение башни
• RES>=MAX: (RES=resources=ресурсы), победа через фарм ресурсов
• "total": процент игр от общего количества данных (доля данных)
• В колонке "turns" 4 числа: первые три: 1.Quantile (0.25), Median (0.5), 3.Quantile (0.75), четвёртое: mean (среднее арифметическое; обозначено жирным; самое нижнее)

---

Итоги:

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

Очень тревожат данные с 17% (17 процентов, Карл!!! 17%!!! Это же почти 1/5 всех игр!) перекосом в турнирах (по правилам столицы), это значит что статистически игроки, которые начинают игру первыми в 58.57% случаев побеждают, а те, которые играют вторыми только в 41.42% случаев. Радостного в этом мало. И насколько понятно администрация игры не собирается ничего менять в этом плане. Аркомагом не занимались с 2012-ого года (в 2013/2014 лишь добавили ботов в турнирах), поэтому приоритет карт у администрации довольно ясен.

Если играть по правилам Tiger Lake, Dragons' Caves, Titans' Valey, Sublime Arbor (max башня: 150 и max ресурсы 400), где в начале дают по 5 шахт, казарм, монастырей, то игра идёт довольно быстро. Видимо излюбленная тактика победы у игроков это победа через фарм ресурсов.

> Игра по правилам столицы

1. Как побеждают?

Tower >= 50: 80%
Tower <= 0: 20%

2. Длительность игры?

40...60 ходов

(1 карта = 1 серверо-ход. эффекты "играем снова" не влияют).

3. Cooldown

cooldown: 44/45 ходов (6+6, 6+7: 45, 7+7: 44)

Формула:
Карта не выходила T-1 ходов. Какая вероятность того, что карта выйдет на ход T? (Но из кулдауна она уже вышла)

4. Выгода того кто ходит первым

Шанс победы, если первый: 58%
Шанс победы, если второй: 41%
Разница: 17%

(средние данные по всем играм не учитывая ставки)

---

Данные: столица. 1 + бесконечная колода

---

Примечание

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

Собственно как и ожидалось... :)

---

Вопросы

1) Имбоватость 7-ой карты, если играем с человеком, у которого 6 карт
2) Как влияет 7-ая карта на игру вообщем. Если например у обоих по 7
3) Дин.оценка карты

---

Анализ механизма выхода карт в таверне
Analysis of arcomage card-cooldown mechanics