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.

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.