bartmassey / mixed-strategies-rs Goto Github PK

mixed strategies game solver in Rust

License: Other

Rust 100.00%

mixed-strategies-rs's Introduction

Mixed Strategies

This Rust codebase contains a library crate, mixed-strategies, for computing optimal mixed strategies and game values given the payoff matrix for a classical two-player zero-sum game.

A simple driver program is also provided that reads a payoff matrix (as ASCII text) from standard input and displays the game solution. The examples/ directory in this distribution contains a number of example payoff matrices.

The code in this distribution is an implementation of algorithms described in the most excellent book

The Compleat Strategyst
John D. Williams
RAND Commercial Books 1954
https://www.rand.org/pubs/commercial_books/CB113-1.html

It's fantastic that The RAND Corporation has chosen to provide a free PDF of this book for download: my paper copy is getting pretty dog-eared. I highly recommend this book as an introduction to game theory. All errors and bugs in the implementation are, of course, my own.

Please see the rustdoc for usage of the library crate.

Installation and usage

Example session (for a rock-scissor-paper game):

$ cargo install --git https://github.com/BartMassey/mixed-strategies-rs
...
   Installed package `mixed-strategies v0.1.0 (...)` (executable `mixed-strategies`)
   
$ printf -- '0 1 -1\n   -1 0 1\n   1 -1 0\n' | mixed-strategies  
value 0.000
max 0:0.333 1:0.333 2:0.333
min 0:0.333 1:0.333 2:0.333

Meaning expected game outgome is neutral for both players, and each player should choose row (column) with equal probability.

Haskell

This started out to be a port of my Haskell implementation also called mixed-strategies. If you want Haskell instead of Rust, you can check that out: it's quite similar. I gave up on the port when I realized it would be easier to reimplement from scratch than to understand my old Haskell.

Author

Bart Massey

License

This program is licensed under the "MIT License". Please see the file LICENSE in the source distribution of this software for license terms.

mixed-strategies-rs's People

Contributors

Stargazers

Watchers

Forkers

mixed-strategies-rs's Issues

Rational arithmetic

Given that everything is linear here, it would be possible to provide a version of this that works over the rationals rather than f64. This would allow exact rather than approximate solutions, but would likely be much slower: it would also complicate the code if the possibility of using f64 (or f32, at that point might as well) were retained.

Termination condition

Compleat Strategyst suggests that a schema is fully reduced when all the marginals are non-negative. However, the pivot strategy can proceed only when at least one column marginal is negative. It is possible that having all the column marginals nonnegative guarantees that the row marginals will also be nonnegative, but it would be nice to have a proof of that in hand or figure out what to do when it doesn't happen. It currently isn't checked for, which is arguably a bug. Note that inactive row or column strategies are not checked for sign in solution(), so there may not be a panic if the solver terminates prematurely.

Better Schema constructors

Right now the only Schema constructor is Schema::from_matrix() which takes a wonky input format. Should probably provide Schema::from_array() and make from_matrix() use that. Maybe other things, too?

Trivial test fails.

$ printf -- '0\n   0\n' | mixed-strategies  
thread 'main' panicked at 'assertion failed: v > 0.0', /home/rust/.cargo/git/checkouts/mixed-strategies-rs-67b1db906ef82bc0/a2e9fc3/src/lib.rs:366:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

There's no choice at all for both players. I expect output like this:

value 0.000
max 
min

Better pivot selection

The current pivot selection criterion is that of Compleat Strategyst. It may be that better methods are out there since 1959. Should be investigated.

Non-square payoff matrix

The code has never been tested with a non-square payoff matrix. This should be done, and the test should be added to the test suite. I don't even understand how the inactive strategy naming thing works for a rectangular matrix, so there's that: I think some code probably needs to be added or changed somewhere.

Bug or paradox?

$ cat /tmp/q.mtx ; cat /tmp/q.mtx | mixed-strategies
 0  +1  -1
-1   0  +1
+1  -1   0

 0  +2  -2
-2   0  +2
+2  -2   0
value 0.000
max 0:0.333 1:0.333 2:0.333
min 0:0.333 1:0.333 2:0.333

$ cat /tmp/w.mtx ; cat /tmp/w.mtx | mixed-strategies
 0  +1  -1    0  +2  -2 
-1   0  +1   -2   0  +2 
+1  -1   0   +2  -2   0 
value 0.000
max 1:0.400 2:0.400 3:0.200
min 0:0.333 1:0.333 2:0.333

Why not 0.333 0.333 0.333 as well?