Brain Dump

На веки вечные. Внизу Павлуша Холмс в поисках правды.

После того как справка нолдора переехала на дейли, вот новая ссылка:
http://daily.heroeswm.ru/help/arcomage/cards.htm

Аркомаг. История изменений в таверне.

2007-07-03 17:38:03 - Строительство таверны (бесконечная колода, без ставок)
2007-07-30 09:59:09 - Добавили гильдию картёжников (ставки на деньги)
2008-01-27 19:14:40 - Добавили 1 колоду (была только бесконечная. 100 карт)
2010-11-11 11:10:02 - Обновление таверны (добавили 2 карты, изменили старые)
2010-12-26 19:49:49 - Добавили карточные турниры
2011-10-15 18:53:20 - Добавили золотые карты
2013-01-24 15:07:15 - Поддержка обеих языков во флеше: англ. и русский
2014-01-08 14:09:00 - Добавили ботов в таверне ([1], [2], [3], [4])

Особенно интересуют следующие пункты:

1. 2007-07-03 17:38:03 - 2007-07-30 09:59:09 - бесконечная колода
2. 2007-07-30 09:59:09 - 2008-01-27 19:14:40 - добавленна 1 колода
3. 2010-11-11 11:10:02 - добавили 2 карты, изменили старые
4. 2011-10-15 18:53:20 - Добавили золотые карты

Ситуация такая: мы выкинули карту, через минимум сколько ходов она придёт к одному или другому игроку на руки? И есть ли некий максимум "не-выхода" карты - может ли карта не выходить 100, 200, 400, 1000, ... ходов ?

Итак, я провёл несколько длительных экспериментов, чтобы получить ответ на этот вопрос. При экспериментов были доступны данные о моих картах и картах противника во время каждого хода (какая карта вышла и какая пришла). Любые запросы/ответы протоколлировались через программу fiddler (перехватчик HTTP запросов) и позже обрабатывались скриптом (statistical language R). Напомню: в колоде у нас 102 карты (ID: 0...101).

У нас есть 3 варианта:

1). 7 против 7 карт
2). 7 против 6 карт
3). 6 против 6 карт

Пример: У меня 7 карт, а у противника 6 карт. Скидываем карту:

I). Первый вопрос:

Через мин. сколько ходов придёт снова карта мне/врагу? (минимальный cooldown)

II). Второй вопрос:

Есть ли верхняя граница "не-получения" карты, то есть может ли карта не выходить подолгу, например 200 ходов?

---

I). Мин.количество ходов "не-выхода" карты:

1). (102 карты - (7+7))/2 = 88/2 = 44 -> cooldown у сброшенной карты минимум 44 хода.
3). (102 карты - (6+6))/2 = 90/2 = 45 -> cooldown у сброшенной карты минимум 45 ходов.
Теперь интересный случай: 6 против 7:
2). (102 карты - (6+7))/2 = 89/2 = 44.5 -> округление идёт вверх или вниз?
Сделал длительный эксперимент (скидывал карты несколько часов). При втором варианте идёт округление вверх, т.е. cooldown 45 ходов.

---

II). Есть ли верхняя граница по "не-выпаданию" карты?

Карты могут не выходить по 200, 400 и более ходов. Но вероятность того, что карта будет очень долго не выходить становится крайне мало.



На графике видно, что в большинстве случаев карта обязательно выходит где-то после 45-150 ходов. Скорее всего механизм такой: Скидываем карту, она попадает во вторую часть колоды (в радомное место). После этого скидываем ещё одну карту, но она может отодвинуть карту до этого, т.е. может получиться, что мы будет постоянно отодвигать одну и ту же карту не давая ей шанс выйти на руки. Если мы будем играть 10.000 ходов (После этой игры максимальное количество ходов стало 2500), то может получится, что одна будет не выходить 1.000 ходов, но исходя из данных наблюдаемых в эксперименте вероятность такого события крайне мала.

Формула

Вероятность того, что определённая карта не выйдет из общего котла X ходов: ((44/45)^Х) * 100% [1] Т.е. будут выходить 44 другие, но не она.
где Х это количество ходов
чем больше Х, тем меньше вероятность, что карта останется ещё дольше. Но бывают и случаи, когда бывает что карта не выходит и по 100 или 200 и более ходов. Но случается такое редко.

Данные по формуле [1]:


Статистические данные очень схожы с данными рассчитаными по формуле.
В статистических данных у нас частота явлений, а в данных по формуле вероятность.
Чтобы переделать количество явлений (frequency) в вероятность (probability), нужно посчитать сумму всех явлений: N (должно быть меньше чем лимит ходов, т.е. 2500) и делить явления на это число N.

Пример:
Событие: 44 хода не выходила карта (любая)
Это событие было 60 раз

Всего например 2400 собранных явлений
60/2400*100% = 2.50% вероятность того, что карта выйдет из кулдауна и срау попадёт кому-то на руки
По формуле: (1-(44/45)^1)*100 = 2.22%

---

Если описать PHP кодом, то будет примерно вот так:

// здесь сидят карты
$cooldown_array = array(3, 7, 9, 42, 101, ...);
// отсюда вытягиваются карты
$pool_array = array(99, 0, 5, 6, 8, 102, ...);

// у первого игрока 6 карт
$cards_player_1 = 6;
// у второго игрока 7 карт
$cards_player_7 = 7;

// 44/45 ходов кулдаун
$cooldown = ceil((102 - ($cards_player_1 + $cards_player_7)) / 2);

/* Игрок играет картой и получает новую */

// карта с номером 42 будет сидеть 44/45 ходов в этом массиве
$cooldown_array[] = 42;

if(sizeof($cooldown_array) === $cooldown - 1){
    // получаем карту, которую засунули 44/45 ходов назад
    $card = array_shift($cooldown_array);
    // добавляем карту в массив. она готова для выхода в мир
    $pool_array[] = $card;
}

// получаем новую карту и даём игроку
$card_id = $pool_array[mt_rand(0, count($pool_array ) - 1)]];
// убираем карту из массива $pool_array
...

All of us know the situation - we play in tavern (Empire Capital, 1 deck) and drop/play a card. What we didn't know exactly is after how much turns the card will come again to us or to our enemy. Is there a minimal "cooldown" for a card? And is there also a maximal "cooldown"? Maybe after 100, 200 or even 400 turns the card will definitely come to us or our enemy.
Card tracking is very important during arcomage tournaments or during card games with high stake hence these are important questions which need to be answered.
I made several experiments and finally figured out the card-reappearance-mechanics. To make such experiments it was important to know how all the information is transfered between my computer and server. Every time you play or drop a card you send an information to server (request) where are the card ID, current turn and card position (on our hands) encoded. The game server receives our request and analyses it and finally the server sends us (to file: "arcomage.swf") the response, which contains a new card which we receive after our turn.
I used web debugging software fiddler to track the communication between my PC and server. During the experiments the web debugging software ran on my and my opponent's PC. Later the collected information was merged and  analysed with my scripts, which were written in R (statistical language R).
Side note: In arcomage we have 102 cards (ID: 0...101).

We have 3 possibilities:

1). 7 cards VS 7 cards
2). 7 cards VS 6 cards
3). 6 cards VS 6 cards

Example: I have 7 cards and my opponent has 6 cards. We use one of our cards:

I). First question:

What is the minimal card cooldown - after how much turns one of us could get this card again ?

II). Second question:

Is there an upper bound for such cooldown? So, is it possible that a used card won't reappear even after 200 turns?

---

I). Minimal cooldown:

1). (102 cards - (7+7))/2 = 88/2 = 44 -> minimal cooldown (both players have 7 cards) is: 44 turns.
3). (102 cards - (6+6))/2 = 90/2 = 45 -> minimal cooldown (both players have 6 cards) is: 45 turns.
Now we have an interesting case:
2). (102 cards - (6+7))/2 = 89/2 = 44.5 -> will the result be rounded up or down?
I made a long experiment (we just dropped cards for several hours) and figured out that the result will be rounded up, hence the minimal card-cooldown for  the second case is 45 turns.

---

II). Is there an upper bound for such cooldown?

Nope, bad news - such upper bound wasn't observed at all. In the first experiment several cards didn't reappear more than 200 turns. In the second experiment (where we played ~10 hours) were several cards which didn't reappear more than 400 turns.
But we have good news too :) - the probability of such "very long card-cooldown" is very very low.

---

On both screenshots we can see that the card will almost cerntainly reappear after 45-150 turns. But there still exists a chance that this card could reappear only after 200...400...1000 turns, but such chance is extremly low.

---

I think that the mechanism could be realized (on the server) in the following way:

We have 2 lists: A and B. A is alist where the newly played/dropped card comes to, let's give an ID to this card: 42
A = [x,x,x,x, ..., 42], so we just append it at the end. This card will stay here for the next 44/45 turns (depends on amount of cards we have on hands). After each turn first element of array A will be taken and added to list B (on random position). Finally, after 44/45 turns our card (with ID:42) will be removed from the list A and added to the list B:
B_old =  [1,.....x, y,.....]
B_new = [1,.....x] + [42] + [y,.....]

B is another list, which works like a blackbox - we know only the size of this blackbox, but we don't know which element is on which position. Our game engine will take one random number between 1 and "length(blackbox)" (this is the size of the blackbox) and then choose one element (card) on this random position - it will be our new card which we will receive.

UPDATE [16.12.2019]: После перехода на HTML5, часть вещей теперь будет проще и быстрее реализовать (Данная статья писалась, когда ещё не было аркомага на HTML5).

---

Так примерно будет выглядеть версия 1.0.4

---

Название инспирированно от HearthStone Companion (OverWolf) =)

Тема про какого-то перса навела на мысль про подчсёт доната.

1. Смотрим какая вероятность получить Х умелки
2. Считаем сколько умелки получил перс через донат
3. Обратно высчитываем сколько он примерно задонатил

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

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


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

Это было про начало игры. Теперь представим себе ситуацию, что где-то через X ходов у нас снова такое же состояние на столе, как и в начале игры - те же ресурсы, те же предприятия, та же башня, та же стена, и у противника аналогично.
Крайне маловероятно такое, но всё равно пустъ будет. - Так в чём различие и зачем это?

- Насчёт различия: Различие и вправду есть - различие в кулдауне и в информации о том как играл противник (его стиль игры). Из-за кулдауна мы на 100% знаем, что карта K там будет сидеть ещё X ходов.

Интересна вообще самая цепочка карт, которыми сыграли. Интересно к какому состоянию подходят лучше всего какие карты. И ещё - для перехода из одного состояния в другое нужно N ходов. Например какие серия из карт нужна, чтобы сделать цикл и вернутся обратно к начальному состоянию? Зачем это надо? - В начальном состоянии мы как бы начинаем игру с начала, т.е. если не задалось в начале, то может повезёт сейчас. Поэтому нужна серия карт (наши с противником по-очереди), с максимальной длинной D (distance), которая приведёт нас к началу, если противник доминирует (больше ресуров и предприятий в течении 10-20 ходов).

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

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

Метод такого типа можно применить не только к аркомагу.

Была идея отнестись к цепочки из карт как генетическому коду. Но с этим очень сложно получатся - у нас не 4 буквы, а 102, т.е. как-то по классам разбивать карты надо - сложновато если честно (однако можно анализировать не сами какие-то отдельные цепочки, а сравнивать их друг с другом (multiple sequence alignment)). Если hidden markov model, то проблема, что у нас не цепочка, а лесенка - карты и игровые состояния - цепочки могут быть схожими, но состояния на столе могли быть разными. Тоже не совсем ясно как-то. Была ещё идея отнестись к игровому состоянию как к протеину, а к карте как к ligand (key-lock model proteins), но тоже как-то не совсем ясно как можно перенять какие-то формулы из биохимической модели для комбинаторной проблемы.
Может у кого есть конкретная идея (формула или метод как переделать одну проблему в другую, но известную) в этом направлении, но у меня нет.

А на основе динамики игры можно делать интересные прогнозы: Нужно анализировать много текущих игр, разбивать по классам, искать схожые мотивы в цепочках. Тут как мне кажется есть ещё потенциал. Например даже чтобы узнать когда какой картой играют - например когда используют карту вор (например если противника 8 маны, и 2 руды). Можно придумать что-то умное и засунуть цепочки например в suffix tree, т.е. такие цепочки, которые приводят к доминированию (нужна какая-то простейшая оценка) или к победе.
Тут и рейтинг карт можно даже сделать. Проблема, что нужно очень много данных.

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

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

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

Внимание: Это метод подходит для анализа и сравнения одного игрока с другим, а не для общей статистики всех игроков.

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

Можно и сравнить себя с каким-либо другим игроком тоже.

Можно брать например по 1000 игр.

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

http://www.heroeswm.ru/cgame.php?gameid=83265888
http://www.heroeswm.ru/cardsgame.php?gameid=83265888&action=getnicks

finkst#1091509|armyanka2#5110970|100|300|3000|249|2|0|-9909681|9|8|10|10|10|6|184|254|466|276|514|326|13|7|60|106|NA|2|1|t54-0|2|t54-|0|0|

HearthStone интересней Аркомага, но Аркомаг намного проще чем HearthStone и годится больше для анализа и сборки идей. ;)

Master’s thesis / PhD thesis Ejnar Hakonsen
System - and AI design of a digital collectible  card game
Довольно интересно пишет, частично прочитал, ещё не успел всё до конца прочитать.

Предыстория

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

1. How to find undervalued Hearthstone cards automatically
2. Метод наименьших квадратов (wikipedia)
3. Least Squares Fitting (Wolfram)

Вот так можно использовать этот метод в аркомаге:

1. Hacking Arcomage. Ideas from DEFCON22.
2. Arcomage. Card scoring. Game beginning. Me first.

Проблемы:

1. Проблемы с нестандартными эффектами наподобие "играем снова". Например я давал вручную оценку таким эффектам (1-2 очка). Но вручную это делать как-то не очень.
2. Как правильно давать оценку "сложным" картам? В Аркомаге есть два типа сложных карт: Первые это карты с условиями. Пример: "Если башня больше чем у врага, то 10 урона, иначе 5", т.е. у карты 2 возможных исхода, а не один. Вторые это эксплуатируемые карты. Пример: "-8 маны всем игрокам". Если у нас например 1 мана, а у противника 8 (не зависимо от каких-либо других карт), то карта сама по себе выгодна, т.к. почти весь "урон" по мане достаётся противнику, т.е. мы эксплуатируем карту в наших целях. У такой карты очень много различных исходов, но эксплуатируемые карты это тоже карты с условиями, но я добавил их в отдельную категорию. Вспомните например о карте вор - как можно максимировать её эффект?
   Получается, что нужно делать оценку не карты такой какой она есть, а делать оценку либо для всех вариантов (через симуляцию), либо делать оценку динамичной (как и было сделанно), т.е. каждый ход смотрим на эффект, который сделает карта и оцениваем её - оправдывает ли она свою стоимость?
3. Комбинации из карт. В принципе всё очень просто: суммируем все эффекты. А дальше? - Ведь мы же делаем так: играем картой А, играет противник, мы играем картой Б. А и Б и есть наша комбинация из карт, т.е. противник играет между каждым ходом. Комбинация по сути наша тактика. Суммируем все эффекты - а потом делим на количество карт из комбинации? или делим на количество всех ходов? Или вообще не делим? Возможностей есть много разных. Вот появилась ещё одна мелкая сложность.

Wikipedia: Приближение с помощью кривых

И всё же - всё равно можно использовать. Неплохой метод, но только для поиска выгодных карт.

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

Вообще для чего нужна оценка?

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

Оценка это вроде как единая валюта для карт и игровых состояний.

Карточная игра с ID 74555157 навела меня на мысль посчитать постройку шахт, монастырей и казарм в среднем (т.е. чего ожидать в среднем к концу игры). Проблема в этой игре состоит в том, что эти персонажи помогали друг другу строить, а нужно учесть ситуацию, где будут рушить у друг друга. Тут можно взять статические данные прошедших игр и посмотреть как выглядят производства в конце игры (Предприятия или производства это шахты, монастыри и казармы; В зависимости от типа победы) и примерно прикинуть их рост в среднем (Пример: размер шахты / количество ходов).

- Зависимость процента побед от того, кто начинает первым
- Аркомаг. История изменений в таверне.

1. Смотрим какие ID игр между изменениями в таверне
2. Собираем часть игр из этих рамок
3. Смотрим например на изменения в винрейте.

Правда кардинальных изменений довольно мало.

Кстати ещё интересно сколько карт у ботов.

2007-07-03 17:38:03 - Строительство таверны (бесконечная колода, без ставок)
2007-07-30 09:59:09 - Добавили гильдию картёжников (ставки на деньги)
2008-01-27 19:14:40 - Добавили 1 колоду (была только бесконечная. 100 карт)
2010-11-11 11:10:02 - Обновление таверны (добавили 2 карты, изменили старые)
2010-12-26 19:49:49 - Добавили карточные турниры
2011-10-15 18:53:20 - Добавили золотые карты
2013-01-24 15:07:15 - Поддержка обеих языков во флеше: англ. и русский
2014-01-08 14:09:00 - Добавили ботов в таверне ([1], [2], [3], [4])