Tetris - A Study of Randomized Constraint Sampling
From Meritology
Author's Abstract
Randomized constraint sampling has recently been proposed as an approach for approximating solutions to optimization problems when the number of constraints is intractable – say, a googol or even infinity. The idea is to define a probability distribution ψ over the set of constraints and to sample a subset consisting of some tractable number N of independent identically distributed constraints. Then, a relaxed problem, in which the same objective function is optimized but only the sampled constraints are imposed, is solved.
[...]
Our study involves a specific stochastic control problem: the game of Tetris. In principle, an optimal strategy for playing Tetris might be computed via dynamic programming algorithms. However, because of the enormity of the state space, this is computationally infeasible. Instead, one might synthesize a suboptimal strategy using methods of approximate dynamic programming, as has been done in [16, 2, 11]. In this chapter, we experiment with the linear programming approach, which differs from others that have previosly been applied to Tetris. This study sheds light on the effectiveness of both the linear programming approach to approximate dynamic programming as a means of producing controllers for hard stochastic control problems, and randomized constraint sampling as a way of dealing with an intractable number of constraints.
Resource: [1] Title: Tetris - A Study of Randomized Constraint Sampling Author: Vivek F. Farias and Benjamin Van Roy
