A Generalized Extensive-Form Fictitious Play Algorithm
This provides an intuitive and easy-to-implement tool for game solving, but it is incremental as it builds on existing extensive-form and Fictitious Play approaches.
The authors tackled the problem of finding equilibria in two-player, zero-sum games by introducing a new extensive-form algorithm that is realization equivalent to generalized Fictitious Play, comparing it favorably to existing methods in terms of storage and computational efficiency.
We introduce a simple extensive-form algorithm for finding equilibria of two-player, zero-sum games. The algorithm is realization equivalent to a generalized form of Fictitious Play. We compare its performance to that of a similar extensive-form fictitious play algorithm and a counter-factual regret minimization algorithm. All three algorithms share the same advantages over normal-form fictitious play in terms of reducing storage requirements and computational complexity. The new algorithm is intuitive and straightforward to implement, making it an appealing option for those looking for a quick and easy game solving tool.