“Iterative Widening”, Tristan Cazenave2001-08-04 (model-based RL; backlinks)⁠:

We propose a method to gradually expand the moves to consider at the nodes of game search trees.

The algorithm is an extension of Abstract Proof Search, an algorithm that solves more problems than basic Alpha-Beta search in less time and which is more reliable.

Unlike other related algorithms, iterative widening adapts to the game via general game definition functions.

In the game of Go, it can solve more problems than the original non-widening algorithm in ~half of the time, as shown by experimental results.

See Also:

• Improving width-based planning with compact policies

• π-IW: Deep Policies for Width-Based Planning in Pixel Domains

• Planning for Novelty: Width-Based Algorithms for Common Problems in Control, Planning and Reinforcement Learning

• Classical Planning Algorithms on the Atari Video Games

• Algorithmic Progress in Six Domains

• Wu’s Method can Boost Symbolic AI to Rival Silver Medalists and AlphaGeometry to Outperform Gold Medalists at IMO Geometry

Backlinks: