A Data-Driven Strategy Guide for Through the Ages, Part 3

Index:

1. Introduction (Link to Part 1)
2. Data Analysis
    2.1 Classification: Infrastructure Development (Link to Part 2)
    2.2 Classification: Cards Played (Current Article)
    2.3 Separating players with TrueSkill (Link to Part 6)
3. Analysis for Boardgamers
    3.1 Infrastructure Development (Link to Part 4) 
    3.2 Cards Played (Link to Part 5)
    3.3 Mistakes made by Good Players (Link to Part 7)

2. Data Analysis

2.2 Classification based on Key Cards played

Let us first recall this Figure from the previous section.

This shows how well we can predict the final outcome based on "infrastructure development" up to a certain round.  It grows monotonically as it should.  However, it grows at obviously different rates.  With the error-bars, we are certain that the slope between round 4 to 8 is almost half of the slopes before and after.  This implies that the status changes during these few rounds are less relevant to the final result.

Based on my experience with this game, there is a likely reason.  In order to develop any aspect of infrastructure, one must play certain cards.  Increasingly better cards become available in different stages of the game.  Thus, the biggest difference occur when players setup those cards.  That happens roughly at round 4 for State I cards, and round 8 for Stage II cards.  That is why those rounds have higher impact on the final result. Thus here, we will try to learn strategic lessons from the usage of those cards.

There are 88 such cards in the game.  We again go through the scraped data to get a 88-dimensional vector per-player-per-game.  Although we also recorded when and how are these cards played, we will not use those information yet. All we care now is whether a card is played, thus the value of each component of this 88-dimensional "Key Cards" vector is either 0 (not played) or 1 (played).

We repeat exactly the same procedure as in the previous section. An SVM with a linear kernel can classify "good" or "bad" performance based on the "Key Cards" vector.  We get a performance of 70% and a weight for each card.

Please do not squint at the above Figure.  This is not very useful due to the same reason that we do not want to use the last few rounds in the previous section. In the above Figure, a lot of cards with heavy weights are "big-late" cards.  They are played at the end of the game and costs a lot of resources and actions. By that time, if a player has those resources and actions to spare, most of the time that's already a "good" performance anyway. Therefore, they are just cashing in their lead.  These are good "indicators" to show that a player is doing well, but they are not the strategic reason why such player is good.

A more careful analysis is required to coax causation from the observed correlations.  For example, we should focus on cards which are played earlier in the game. Ideally, We should also compare cards with comparable opportunity costs.  Again, GO is a biased example that every single move has the same opportunity cost---another move.  In TtA, playing a card usually involves a combination of many types of resources, thus no card has exactly the same opportunity cost as another. Thus, we need to be more clever about "asking the right questions" here, and may need to cross-reference to some other statistics.

This does not mean that once we have selected the appropriate subset of cards to compare, we can then refer to that subset in the above Figure.  A classifier is trained to classify.  In some sense, it will use the best clue first, and then conditioned on that, it will consider less significant clues. (In a decision tree, this would have been exactly true. For a linear SVM, we can draw a 2-D example to convince ourselves that a similar effect is still present.) In this particular example, our classifier is effectively asking whether a player has played those "big-late" cards, and use that as the main guidance for classification.  It will then consider earlier cards with less weights to fine-tune the prediction.  This is similar to a conditional probability in the reverse-time order (condition on the result to compare the causes, also known as a post-selection effect). This is opposite to the usual strategic thinking, and will often lead to strange results at face value.

Let me give a concrete example here.  All those "big-late" cards cost a lot of resources.  However, all cards that help to produce more resources have small, or even negative weights in the Figure. This sounds weird, but it makes perfect sense for the classifier.  It first gets a correlation between winning and big-late cards. Then, if a player won without playing those big-late cards, she better not have invested too much in resource production.  This criterion will help the classifier to recognize those rarer winning situations. We cannot learn from the negative weights here to conclude that those resource-producing cards are bad in general.

In order to get a meaningful result for a subset of cards, we should train our classifier only on that subset.  Here is an example for all cards available early in the game.

First of all, the number on the top is the classifier performance. At 59%, it is comparable to using the data up to round 4 in the previous section.  Since "playing cards" is closer to individual moves than "improving infrastructure", that is quite a good news.  It also teaches a clear lesson.  One particular type of cards stands out in the above Figure. All the Leader cards have significantly higher weights than other types. This is consistent with advices from experienced players, and also consistent with the fact that leaders have strictly smaller opportunity cost than other cards, yet they often provide more benefits.

We will repeat this process for various other choices of subsets.  If the performance is higher than 54%, we will analyze the results in Section 3.2.  We will need to select those subsets carefully, and often need to supplement the result with other statistics to get meaningful lessons.

Sometimes, the true power of a card does not manifest alone.  Seasoned gamers usually expect combos--2 or more cards that combine to have dramatically better effects.  There is a particularly simple way to detect the existence of combos. We can train an SVM with polynomial kernel of degree X. If the performance turns out to be better than the linear kernel, that implies the existence of combos involving X or less cards.

Unfortunately, and a bit surprisingly, such situation has not come up yet during our analysis. Actually, the validation performance for nonlinear kernels are usually worse than the linear kernel. This is true even if we train on a subset of cards which seasoned players consider to have good combos. This is probably because that the chance for a player to get both cards in a combo is very small. A card has a 10%-30% chance to be played by someone. Thus a particular 2-card combo only shows up 4% of the time. Within 10k samples, there might be too much "noise" among those cases.

Note that this is not about over-fitting though. In fact, we have only talked about validation performances so far, but in all examples they are actually close to the in-sample error. Even with only 10k games, the VC dimensions of our models have always been small enough to avoid over-fitting. The "noise" here actually stops the classifier from recognizing any pattern associated with combos even in-sample. It is not very clear whether increasing the data set size will improve that.

A Data-Driven Strategy Guide for Through the Ages, Part 2

Index:

1. Introduction (Link to Part 1)

2. Data Analysis

    2.1 Classification: Infrastructure Development (Current Article)

    2.2 Classification: Cards Played (Link to Part 3)

    2.3 Separating Players with TrueSkill (Link to Part 6)
3. Analysis for Boardgamers

    3.1 Infrastructure Development (Link to Part 4)
    3.2 Cards Played (Link to Part 5)
    3.3 Mistakes made by Good Players (Link to Part 7)

2. Data Analysis

2.1 Classification based on Infrastructure Development

The first idea is a simple 2-type classification---"good" or "bad".  We can then learn from the good behaviors and avoid the bad ones.  We will say a "good" outcome is >90% of the winner's score, and a "bad" outcome is below that. This threshold is motivated by statistics.

If we remove one winner from every game, the scores of remaining players follow the above distribution.  We can see that the median of non-winners is about 80%, which should not be defined as "good".  Choosing 90% means that about 53% the results are "good" (the actual winner included), and 47% are "bad".  This is a pretty comfortable ratio for a classifier without special tuning.  Also note that the game allows resigning.  That represents the small bump around 0 in the above Figure.  Because they did not finish the game, their data are incomplete.  All resigned players are removed from our consideration.  From 10k+ games, we get 30k+ results to classify.

Next, we look at the development of infrastructure.

This examples shows the amount of foods generated each round by each player in a 4-player game (note that grey resigned at round 15).  One can find the same information for 5 other aspects in the infrastructure.  This game lasted 17 rounds, which means that the data dimension is 17*6 = 102.  We will not directly use the value in the above figure.  Since the final result is a relative quantity with respect to other players, it only makes sense for the input to be relative quantities.  We will normalize this vector by the mean of the game, indicating whether a player is doing relatively better or worse than other players at the same game and the same round.

We are not ready to throw this into a Machine Learning Classifier yet.  The number of rounds actually varies from game to game, but a typical classifier wants all data points to have the same dimensionality. 

We have two ways to circumvent this problem.

We first consider the entire game duration, but rescale that into 11 portions independent of how many rounds there are. This gives us a 66-dimensional "infrastructure development" vector per game per player, and we can classify the final result accordingly. We use the support vector machine classifier (svm.svc) from Sci-kit Learn.  It is trained on a random subset of N points, and validate it on a disjoint subset of the same size. For 3k<N<10k, the validation performance stays around 73%, and the linear kernel performs equally well with nonlinear ones. (Exception: The sigmoid kernel performs no better than random guesses. I have not figured out why.)

73% may not sound impressive, but it is already useful for our purpose. Unlike GO, TtA is not fully deterministic. There are hidden and random elements. Actually, our choice of 6 aspects does not even cover all deterministic information. The null model that always predicts "good" would have had a performance of 53%, with a standard deviation less than 1% at N=3k. Thus, the classifier is performing quite well and already learned some strategic lessons.  We train with the linear kernel 10 times and take the average of its coefficients.

These coefficients tell us "being better than your opponent at what aspect, during which time of the game", is more likely to help you win the game. We will look closer at these results and analyze them in the actual game context in Section 3.1.

We can see that in the above Figure, the coefficients tend to be larger in later portions of the game. That is expect, but also a bit problematic for our purpose. TtA simulates an economical development.  Small investments early in the game can snowball into huge benefits later.  In the last few rounds, players are typically cashing in those benefits.  Monitoring those "cashing in" moves is the most accurate way to predict the outcome. However, that is not exactly what we want to learn here.  We want to know the subtle effects of early investments. 

It is not safe to just look at the earlier portions in the above Figure. When we play this game, we make early decisions without knowing the later developments. The above classifier is already contaminated by information from the future. This will create a post-selection effect such that the coefficients on earlier portions can be misleading. In the next Section, we will provide an obvious example. For now, if we want to learn things from earlier portions, it is the best to ask our classifier to ignore future information.

This brings us to our second method.  We will only use the information from the first X rounds, with X up to 11. Despite the variability of the actual duration of each game, the first 11 rounds are almost always early-mid stages of the game.  We will take these (6*X) dimensional vectors and feed into the classifier.  After the same training and validation process, we get their performance as a function of X.

We can see that after the 1st round, the performance is better than blind guesses, and monotonically increasing.  With all 11 rounds of data, the classifier is correct 66% of the time, not too far from the 73% while using the full duration.  This implies that early developments already have small but measurable effects on the result.

For example, the above Figure shows the coefficients from round 0 to round 4. One can see clear difference between different aspects.  Military actions, foods and culture are unimportant, or even bad.  Civil actions, science and resources are generally better. We will look closer at these results and analyze them in the actual game context in Section 3.1.

The development of infrastructure does provide strategic lessons.  It tells us when and what aspects are more important to victory. However, such lessons might be a bit vague.  In other words, the Intermediate Status chosen here might be a bit far away from individual moves.  In the next Section, I will consider a different choice.

A Data-Driven Strategy Guide for Through the Ages, Part 1

Index:

1. Introduction (Current Article)

2. Data Analysis

    2.1 Classification: Infrastructure Development (Link to Part 2)

    2.2 Classification: Cards Played (Link to Part 3)

    2.3 Separating players with TrueSkill (Link to Part 6)
3. Analysis for Boardgamers

    3.1 Infrastructure Development (Link to Part 4)
    3.2 Cards Played (Link to Part 5)
    3.3 Mistakes made by Good Players (Link to Part 7)

1. Introduction

1.1 About this game:

Through the Ages (TtA) is a very popular board game first published in 2006.  Its most current revision (2015) is ranked at top 3 in the world.  For people who are familiar with boardgames, this page should tell you everything you want to know about it.

For everyone else, here is a small diagram that introduces the concept of general Euro/Economy/Strategy games, and some specific features of this game.

Basically, every player will have access to some resources.  Throughout the game, they decide how to invest those resources.  One option is direct conversion into points, since the player with the most points wins the game in the end.  On the other hand, it is often wiser to invest resources on various infrastructure.  These are the things that can continuously help you generate points and resources.  Choosing when and what to invest on is the key to improve your efficiency, and the key to victory.

TtA is a Civilization Simulation game.  You manage resources like foods, ores and knowledges; you invest them to develop technologies that improves farms, mines, and various other aspects of your country. Then finally, the country with the most aspiring cultural legacy is the winner.

Typically, a player has to make more than hundreds of decisions during a game.  The consequence of one decision often remains unclear until ten (or more) decisions later.  Thus, the strategy manifests mostly as human intuition and high-level (vague) reasoning.  This is exactly the type of problem that modern data science might be useful.

1.2 A Data-Driven Strategy?

After the tremendous success of AlphaGo, the world knows that AI can play deep strategy games.  It turns out that how an AI plays a game is very similar to how a person does.  We both follow the middle flow chart in the following diagram.

For example, in TtA, you can make a single move to build a farm.  When you do that, it usually comes with a train of reasons. "This will produce foods for me, which enables me to increase population in a future move. Then I can use that population as miners/soldiers/... etc."  Such reasoning probably stops here, because you don't exactly know how that extra miner/soldier helps you win the game.  Therefore, you cannot exactly calculate the actual effect of this farm, nor its difference to other choices you have.  Experience and intuition takes over here, which gives you a rough feeling of how "good" a farm is, and allows you go move on and evaluate your other options.

The place where explicit derivation stops and intuition takes over is marked as Intermediate Status in the above diagram.  For human beings, the derivation from individual moves to the intermediate status is usually called "tactics".  Analysis from the intermediate status to the final result is often called "strategy".  An AI basically uses two algorithms to perform these two functions.  For example, a Monte-Carlo tree search can go through individual moves and see their outcomes; a Neural Network can learn from millions of examples of the intermediate status and tell you which ones are closer to victories.

I am not taking the right path all the way as a human, nor am I taking the left path all the way as an AI.  I wish to take a diagonal path goes from top-right to bottom left.  Therefore, a Data-Driven Strategy Guide should tell us what intermediate status are more likely to win, and a human player will be in charge of finding the best tactics to achieve such intermediate status.

There is a very practical reason why I am doing this. In order for an algorithm to derive from individual moves, one must hard-code all the rules. GO is a somewhat biased example that the rules are extremely simple.  The rules of GO can be written in 10 sentences, while the rules for games like TtA are often booklets of 10+ pages.  The "rules" of a real-life problem may not even be fully captured by any finite number of words.  In these kind of situations, human minds are still superior in creativity and thinking outside the box.  Thus in general, I find it more natural for human to come up with "what can be done", and then consult an AI to understand the final consequence of such option.  In other words, AI can give you answers, but we are in charge of asking the right questions.

1.3 Data Source

Boardgaming-online has a very nice implementation of Through the Ages (TtA).  It also keeps journals of all past games.  A journal is a pretty detailed record of a game. Although it is insufficient to reconstruct the actual entire game, it should contain some information to offer a glimpse into the strategy.

Using Python packages Requests and BeautifulSoup, I scraped the content of game journals as Pandas DataFrames. There are more than 100k stored games, and I have managed to scrape 10k+ games at this moment.  Hopefully these will be enough to provide some insights.

A complete journal has about 5-10 pages, which represents 2-4 data points (depending on the number of players).  The first challenge is to use my knowledge of the game and the interface to parse the journals, in order obtain simple information that can be fed into machine learning algorithms.  This is a tedious process involving not only standard selections in pandas frame, but also quite a few customized parsing routines. I will not bother the readers with details here.  Let us jump ahead to some "clean" data I extracted from the journals.

1.4 Outline:

In Section 2, we will explore a few different choices of Intermediate Status, and see how Machine Learning can estimate the final result from them. Naively speaking, we want the Intermediate Status to be close enough to the final result, such that the Strategic Evaluation is accurate. On the other hand, we want it to be close enough to individual moves, such that Tactical Derivation is not too difficult.  GO is again a biased example that there is a clear choice for Intermediate Status: a 19x19 matrix with 3 possible values at each entry. In TtA, given the form of data we have, even choosing the form of the Intermediate Status is a main challenge.

I will first setup a classification problem and explain the process of how to obtain the training/validation set from the raw data. I will also explain the how the Machine Learning algorithms can help us formulate strategy. I will apply this classification problem in Section 2.1 and 2.2. These is the main section that Data Scientists might be interested in.

(Link to Section 2.1)    (Link to Section 2.2)

In Section 3, we will analyze the results of Section 2 in the actual context of the game.  This is the main section that boardgamers might be interested in.

(Link to Section 3.1)    (Link to Section 3.2) 

First Major Update (02/12/2018)

(Link to Section 2.3)    (Link to Section 3.3)

In Section 2.3, I will introduce another algorithm--TrueSkill. TtA is not an entirely deterministic game. TrueSkill takes that into account and allows us to ask more relevant questions. In addition to classification based on individual game results, we can instead classify behavior based on players' TrueSkill.

In Section 3.3, we look into all cards during Age A and Age I. By cross-referencing the outcomes of individual games with players's skill, we discover a few interesting mistakes made by stronger players.

Caylus (凱呂斯) 量化分析

Caylus 是個經典的工人放置遊戲 
http://boardgamegeek.com/boardgame/18602/caylus
目前在 BSW 和 BGA 上都可以免費玩

我想要提供的不是一個固定的策略，因為多人 Caylus 中很可
能不存在一個死板的最佳策略。我要介紹一個 "量化" 的方法
，讓每個人都可以憑自己的風格和經驗，找到最有勝算也最適
合自己的策略。

目錄：
第一章：初步估計
第二章：增值動作分析
第三章：房子的價值
第四章：效率和限量
第五章：賞賜
第六章：風險和戰爭

感謝 ptt 版友 noyarc, meir 對本文初版的批評指教。





第一章：初步估計

遊戲最後比的是分數，但是遊戲當中你最常直接得到的東西是
資源和錢。所以建立任何戰術最重要的第一步，是瞭解資源和
錢的價值。我推薦的計算方式是：

　　　　　一個資源　＝　一塊錢　＝　一分

金塊一個三分的廢話就先不提。請先注意，這個算式是為了將

來的計算做基礎，而不是直接拿來估計你下一個動作的價值。

幾乎在任何時候，手上比別人多一顆資源，是比多一元來的好

，也比多一分來得好。然而這裡說的“好”，是根據遊戲的進行

隨時在變化，而無法死板的量化的。我的目的就是要透過簡單

的計算，讓你靈活的在更種狀況下，能自己去分析到底“好”在

哪裡。

所以我定的基礎價值是被市場決定的。所謂 "市場"，泛指所

有不同東西互相轉換的機制。前期的中立建築確保一塊錢常常

被轉換成一分；第三階段的城堡確保大量的資源可以被轉換成

平均一個一分；拉監工，使用銀行和教堂也確保錢可以直接變

成一個一分。在一般的遊戲狀況下這些管道的暢通使得以上的

估計方式算是可靠。

當然，有一些細節必須注意。一塊錢算一分是建立在大家的錢
在一個合理的範圍，後期大概是十塊左右，前期則略低。在第
二階段，當你有十塊而兩個對手都只有五塊，那你確實有五分
的領先。當你有二十塊而對手有十五塊時，顯然並沒有領先很
多。特別是遊戲快要結束而多的錢花不完的時候，剩下來的錢
是幾乎沒有價值的。

因此，在你金錢領先的時候，請千方百計的發動 "拉監工 (小
圓盤) 的戰爭" 。先不管最後結果的細節，大家一起花錢就是
對你有利。要怎樣發動一場 "拉監工的戰爭" ，是 Caylus 

中最經典的部分，我會之後再詳細說明。多餘的錢常常會讓你

在這個可能性中取得優勢地位，而一塊錢價值一分這件事已經

把這個隱性的優勢計算在內了。

在確立的初步的價值估計之後，我們會發現遊戲中的動作大致
上分為兩類：
(1) 轉換：
花一塊錢派人去拿一個資源，買分或買金塊，或是蓋城堡沒得
賞賜。這些行動並沒有(或是很少)直接讓你的總資產增值。
(2) 增值：
蓋房子，蓋城堡得賞賜，比武場得賞賜，得到金錢，用木造或
石造資源房。

轉換的動作通常即使你兩手空空依然可以去做。增值的動作常
常需要你手上有資源，有時還需要大量且特定種類的資源，才
能夠執行。一場遊戲下來，執行最多次 (總效果最大) 增值動
作的玩家就是贏家。這不表示你隨時都直接搶增值動作。當你
可以執行轉換動作確保接下來某些增值動作只有你能做，你也
是搶到了那些增值動作。舉例：拿石頭確保敵人沒有，那造石
場就是你的；拿布而敵人沒有，那比武場就是你的；確保資源
多樣化可以蓋出較多城堡，那城堡就是你的。

等你瞭解哪些動作增值多少，再想想你要做多少準備才能去執

行，你就會開始瞭解各種動作的“好”在哪裡了。

A Quantified Guide to Caylus

Prologue:

Caylus is an epic “worker placement” game, http://boardgamegeek.com/boardgame/18602/caylus. It is currently available on both BSW and BGA for free online play. Thanks to that, a large number of games have been played and recorded. Inevitably, most of the online games are between 2 players, which gamers call “2er”s. Due to the lack of intrinsic luck factors, 2er Caylus can be rigorously calculated, and there exists a framework of dominant strategy focused on using the 4^th track (building) favors.

This post will not be about such dominant strategy, since you can find a good description elsewhere. Actually, I will barely talk about 2er. I will instead focus on multiplayer games, 3er, 4er or 5er, where there is no dominant strategy. Don't get me wrong. The building favor is still useful, and a related strategy can still be efficient. However, that should not be the only strategy you know. If that is the case, such lack of flexibility not only decreases your own chance to win but also makes the game boring.

Disclaimer: This is NOT a strategy guide. I will not tell you exactly what to do. Instead, the main point is to demonstrate a framework of calculation and quantification. This is because multiplayer Caylus is too deep for any linearized strategy. I am simply providing the tools that everyone can use to find his/her own favorite strategy.

Chapter One:  Basic evaluation

Chapter Two:  Productive actions

Chapter three: The value of buildings

Chapter four:  Efficiency and quota

Chapter five:  Favours

Chapter six:   Risks and wars

Chapter One:  Basic evaluation

Victory is determined by victory points (VP), but during the game you will often directly acquire money (coins) and resources (cubes). We need to establish a baseline conversion rate in order to perform any calculation. Here is what I will use:

1 coin = 1 cube = 1VP

In addition, 1 gold = 3VP.

Please note that this equation is not for you to directly evaluate your immediate next move. They form the baseline of our calculation because they come from the most frequent, and usually guaranteed actions (that if one player choose to do so, others cannot or will not stop him)  throughout the game: (1) neutral buildings turn one coin into one cube and are continuously used through out the game, (2) multiple castles in the last stage turns 1 cube to 1 VP and it is common to have a lot of castle building, (3) Bank and Church turn coins into VP or equivalent golds in exactly this rate. Even you are not a very good player, you can expect this basic conversion from coins to cubes to VP to happen naturally for you, in at least this rate.

As you get better, you will manage to get yourself better conversion rates. The purpose of this guide is to provide a framework to quantify how much "better" you can get, which is convenient determined by comparing to this baseline rate.

The true value of coins and cubes are of course highly situation-dependent. By the very end of the game, you certainly prefer 1 more VP than anything else. Earlier in the game, 1 more cube can usually give you an advantage much larger than 1VP. The value of having more coins depends sensitively on how much your opponents have. Early in the game, when you have 7 coins while your opponents have 2, that is a solid 5VP lead (or maybe much more). However later in the game, when you have 20 coins while your opponents have 15, it is obviously not as good.  A smart arrangement to induce a ``bribing war’’ on Provost can efficiently reduce everyone’s money, therefore maintaining the value of your extra coins.

In addition to the actions that established this baseline value, which by definition only ``transforms’’ one form or resources into another form without increasing value, there are other actions which are “productive”: they allow higher conversion rates than the baseline. Being able to perform more and better productive actions wins the game. 

However, this does not mean transforming actions are weaker than productive actions. That is because productive actions often require you to have certain set of resources, which you can only get from doing a few transforming actions as preparation. If you are the only one who is ``prepared’’ for these productive actions, you almost guarantee that they are yours to take. For example, the Jousting Field (1 Favour) requires a cloth (purple cube), and there is absolutely no way to get a cloth before the Jousting Field activates in the same round. Therefore, if you are the only player who has a cloth left from the previous round, you pretty much guarantee the usage of Jousting Field. Likewise, being the only player to have stone somewhat guarantees your usage to the Mason. 

So getting the right transforming action is a integrated part to help you get more productive actions. Exactly how to do that, is tactic/strategy, which is not my focus. Since you eventually have to do some productive actions to win the game, my goal is to help you understand their values. Otherwise, you might have beautiful planning, getting all the productive actions you want, and still lose the game, simply because you ``wanted’’ the weaker productive actions. That would be a shame, right?