search

foxyseta / monkey

Project for the University of Bologna Data Structure and Algorithms course (a.y. 2020-21).
https://foxyseta.github.io/monkey/
GNU General Public License v3.0
3 stars 1 forks source link

Pattern search #23

Closed foxyseta closed 3 years ago

foxyseta commented 3 years ago

"Pattern search, introduced by Van Rijswijck [90], is a game-tree search enhancement based on Ginsberg’s partition search [46] and Allis’ threat-space search [7]. It applies to games where immovable counters are placed on the board, and was developed for the game of Hex. The method is able to prove wins and losses while searching a tree smaller than the minimal proof tree of the game, by proving the result for several moves at once in lost positions. Pattern search concentrates on finding threat patterns . A threat pattern is a collection Ψ of empty cells in a position P, with the property that the game-theoretic value of P is unaltered when the winning side is restricted to playing moves within Ψ . A threat pattern is not unique for a position, since adding an empty cell to a threat pattern always creates another valid threat pattern. A threat pattern can be thought of as representing the relevant area on the board, an area that human players commonly identify when analysing a position. The patterns can be calculated recursively." Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck

foxyseta commented 3 years ago

Interessante! Stanno cercando di lavorarci pure Mattia e Luca.