1
$\begingroup$

I have a series of games with the following properties:

  1. 3 or more players, but purely non-cooperative (i.e., no coalition forming);
  2. sequential moves;
  3. perfect information;
  4. deterministic state transitions and rewards; and
  5. game size is large enough to make approximate methods required (e.g. $1000^{120}$ for certain problems).

For example, Chinese Checkers, or, for a more relevant example to my work, a multi-player knapsack problem (where each player, in round-robin fashion, can choose without replacement from a set of items with the goal of maximizing their own knapsack value).

Question: what policy improvement operators or algorithms a) converge to optimality or b) provide reasonably strong results on these games?

What have I researched

  • In a small enough game (e.g., 3-person Nim with (3,4,5) starting board), full tree search is possible.
  • In a one-person setting, certain exact Dynamic Programming formulations can reduce complexity. For example, in a one-person setting with a small enough knapsack, any standard array-based approach can solve the problem. I'm unsure if or how these "cost-to-achieve" shortest path formulations carry over to multi-player games.
  • In a one-person setting, policy improvement approaches like rollout algorithms and fortified rollout algorithms have the cost improvement property. I'm unsure if this property carries over to multi-player versions.
  • Work has been done (for example, this thesis) to demonstrate that Monte Carlo Tree search strategies can generate powerful policies on the types of games I'm interested in. I believe it's been proven that they converge to Nash Equilibrium in two-player perfect information games, but am not aware of any guarantees regarding multiplayer games.
  • For imperfect information games, Monte Carlo Counterfactual Regret Minimization (e.g. here) is required for any convergence guarantees. Given I am working in a perfect information environment, these seem like overkill.
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.