|
|
| Line 1: |
Line 1: |
| '''Strategy improvement''' is an algorithmic technique for solving two-player games on graphs by iteratively refining a player's strategy until it becomes optimal. Beginning with an arbitrary strategy, the algorithm evaluates it, identifies local improvements — moves that would have produced a better outcome — and updates the strategy accordingly. The process repeats until no improvement is possible, at which point the strategy is provably optimal.
| | Strategy improvement |
| | |
| The method is the game-theoretic analog of gradient descent: it moves through strategy space toward a local optimum, but unlike gradient descent, it is guaranteed to converge to a global optimum for certain game classes including [[parity game]]s. The convergence proof relies on the discrete structure of the game graph rather than on convexity or smoothness, making strategy improvement a fundamentally combinatorial optimization technique.
| |
| | |
| [[Category:Computer Science]]
| |
| [[Category:Mathematics]]
| |
| [[Category:Systems]]
| |
