Optimizing for Strategy Diversity in the Design of Video Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917708329648128 |
|---|---|
| author | Hanguir, Oussama Ma, Will Ryan, Christopher Thomas Han, Jiangze |
| author_facet | Hanguir, Oussama Ma, Will Ryan, Christopher Thomas Han, Jiangze |
| contents | We consider the problem of designing a linear program that has diverse solutions as the right-hand side varies. This problem arises in video game settings where designers aim to have players use different "weapons" or "tactics" as they progress. We model this design question as a choice over the constraint matrix $A$ and cost vector $c$ to maximize the number of possible \emph{supports} of unique optimal solutions (what we call "loadouts") of Linear Programs $\max\{c^\top x \mid Ax \le b, x \ge 0\}$ with nonnegative data considered over all resource vectors $b$. We provide an upper bound on the optimal number of loadouts and provide a family of constructions that have an asymptotically optimal number of loadouts. The upper bound is based on a connection between our problem and the study of triangulations of point sets arising from polyhedral combinatorics, and specifically the combinatorics of the cyclic polytope. Our asymptotically optimal construction also draws inspiration from the properties of the cyclic polytope. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2106_11538 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Optimizing for Strategy Diversity in the Design of Video Games Hanguir, Oussama Ma, Will Ryan, Christopher Thomas Han, Jiangze Optimization and Control We consider the problem of designing a linear program that has diverse solutions as the right-hand side varies. This problem arises in video game settings where designers aim to have players use different "weapons" or "tactics" as they progress. We model this design question as a choice over the constraint matrix $A$ and cost vector $c$ to maximize the number of possible \emph{supports} of unique optimal solutions (what we call "loadouts") of Linear Programs $\max\{c^\top x \mid Ax \le b, x \ge 0\}$ with nonnegative data considered over all resource vectors $b$. We provide an upper bound on the optimal number of loadouts and provide a family of constructions that have an asymptotically optimal number of loadouts. The upper bound is based on a connection between our problem and the study of triangulations of point sets arising from polyhedral combinatorics, and specifically the combinatorics of the cyclic polytope. Our asymptotically optimal construction also draws inspiration from the properties of the cyclic polytope. |
| title | Optimizing for Strategy Diversity in the Design of Video Games |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2106.11538 |