Computing Equilibria in Colonel Blotto by Applying Counterfactual Regret Minimization Using a Layered Graph Representation

Equilibrium computation of games is one of the fundamental problems at the intersection of computer science and economics. Many popular games have been solved to superhuman levels with a variety of learning techniques, such as diplomacy, many different variants of poker, and most notably, chess. In this paper, we will be focusing on the game of Colonel Blotto which is a classic problem that was first introduced by Emile Borel[1] in his seminal 1921 talk on the theory of games. Colonel Blotto is a game played between two colonels who must distribute their troops among different battlefields, and it is scored by a winner-take-all rule. Colonel Blotto has historically been difficult to solve due to its immense action space. [2] was the first to formulate the game in a linear program and later, [3] was able to greatly improve their formulation in practice by representing the action space using layered graphs. Recently, the multiplicative weights update (MWU) algorithm was implemented in Colonel Blotto by [4] that took advantage of sampling from the action space to learn in larger game settings. We take advantage of the layered graph representation from [3] and use it to run counterfactual regret minimization (CFR) on Colonel Blotto for the first time. CFR is a state-of-the-art learning algorithm that permits parameter free learning and has practical performance that is much better than its theoretical bounds.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2024

Author dc:creator

• Zhang, Isaac S.

Advisor dc:contributor.advisor

• Farina, Gabriele

Statement dc:rights

• Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)
• Copyright retained by author(s)

Licence dc:rights.uri

• https://creativecommons.org/licenses/by-nc-nd/4.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/156784

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/156784