foxyseta / monkey Goto Github PK

Possiamo fare ancora di meglio dell'escargot?

"Aggiungere schemi dinamici di ordinamento delle mosse, come provare per prima cose la mosse che si sono rivelate le migliori nel passato, ci porta molto vicini al limite teorico. Il passato potrebbe essere la mossa precedente (spesso rimangono le stesse minacce) o potrebbe derivare dalla precedente esplorazione della mossa corrente. Un modo per ottenere informazioni dalla mossa corrente è quello di utilizzare una ricerca ad approfondimenti iterativo. Innanzitutto si cerca 1 strato in profondità e si registra il miglior cammino di mosse. Poi si cerca 1 strato ancora più in profondità, ma si utilizza il cammino registrato allo scopo di fornire informazioni per l'ordinamento delle mosse. Come abbiamo visto nel Capitolo 3, l'approfondimento iterativo su un albero di gioco esponenziale aggiunge soltanto una frazione costante al tempo di ricerca totale, che può essere recuperata con gli interessi mediante un miglior ordinamento delle mosse. Le mosse migliori sono spesso chiamate mosse killer e si parla di euristica della mossa killer quando si provano queste per prime." Russell-Norvig

"Proof-number search
Proof-number search [5,7] is a best-first search, in which the cost function used in
deciding which node to expand next is given by the minimum number of nodes that have to
be expanded to prove the goal. As such it is a successor of conspiracy-number search [77,
93]. Proof-number search is appropriate in cases where the goal is a well-defined predicate,
such as proving a game to be a first-player win.
Depth-first proof-number search
The Tsume-Shogi-solving program SEO is based on a newly-developed iterativedeepening depth-first version of proof-number search, named PN* [98]. The idea is partly
derived from Korf’s RBFS algorithm [67], which was formulated in the framework of
single-agent search and as such a successor of the widely-used IDA* algorithm [66]." Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck

"Allis generalised the idea of threat-space search to a method called dependency-based
search [7]. However, the latter name was never adopted and the idea of threat-space
search or threat-sequence search is widely known by now. Threat-space search investigates
whether by a sequence of threats, to which the opponent at any time has only a limited
set of replies, a win can be forced. Since the opponent effectively has no real choices, this
search algorithm represents the application of single-agent search to two-player games.
A recent successor of threat-space search, called λ-search, has been proposed by
Thomsen [111]. This method uses null moves combined with different orders of threat
sequences, called λ-trees. Thomsen introduces λ1-moves, which threaten to end the game
or reach a specified subgoal immediately, followed by λ2-moves threatening a winning λ1-
sequence, and so on. The method behaves as a goal-directed searcher, with a favourable tree
size relative to standard α-β trees. It can be combined with any search method to search the
λ-trees. As a relevant example Thomsen mentions proof-number search. A combination of
null moves and proof numbers seems a promising method for solving Go endgames.
A close analogue to λ-search is Abstract Proof Search, proposed by Cazenave [27].
This method has reportedly been able to solve Philosopher’s Football on 9 × 9 boards.
304 H.J. van den Herik et al. / Artificial Intelligence 134 (2002) 277–311
Extensions of the algorithm can solve the 11 × 11 game and may be able to solve 13 × 13
as well [28]." Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck

"Retrograde analysis is a method in which for each position of some specific game or
endgame the number of moves towards the best reachable goal is stored. For instance, in
Chess, assuming perfect counterplay, the number of moves to be played by the stronger
side up to mate or conversion is stored. Checkers databases sometimes only contain an
indication of won, drawn, or lost per position. A database is constructed by starting in
terminal positions and then working backwards [53]. Once constructed, perfect play is
guaranteed: the stronger side chooses a move with the shortest distance-to-mate (or to
conversion) and the weaker side opts for moves with the longest distance-to-mate (or to
conversion). In passing we remark that perfect play by a computer in a position which is
H.J. van den Herik et al. / Artificial Intelligence 134 (2002) 277–311 303
game-theoretically drawn or lost does not guarantee the best performance against fallible
opponents, as was demonstrated by Jansen [63].
Using the retrograde-analysis method, the first endgame database was already constructed by Ströhlein in 1970 [106]. However, his work remained unobserved for a long
time. In the mid seventies the method of retrograde analysis was independently re-invented
by Clarke [30] and Thompson. Only when the latter researcher’s results became widely
available in the early eighties did the method gain its well-deserved fame [54,109]. Nowadays the use of retrograde analysis is commonplace for the construction of endgame
databases. It has deepened the understanding of such endgames considerably, and resulted in notions as max-to-mate, max-to-conversion, max-to-zeroing-move, and max-tothe-rule [51]." Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck

It'd be neat if monkey.ai.State.result were to return a reference to the (updated) state itself.

Una buona ed efficiente euristica per presentare le mosse in modo ordinato dalla più promettente alla meno genera alberi più atti alla potatura alfa beta.

Evitare di ripetere gli stessi calcoli per stati che sono uno trasposizione/simmetria dell'altro permette di esplorare meno nodi.

10,10,5(?), 50 50 10 e 70 70 10 sono "grandi configurazioni". Come gestirle?

MoNKey va in timeout un po' troppo spesso con le griglie abbastanza grandi.
Una possibile soluzione drastica è controllare il timeout ad ogni nodo, perché un nodo richiede tempo di visita costante.
ATTENZIONE: quando abbiamo capito che interrompiamo la ricerca prima la interrompevamo in tempo costante perché bastava uscire da una funzione sola. Adesso dove siamo in chiamate ricorsivi max e min value dobbiamo uscire da tutte chiamate ricorsivi innestate

Per ottenere soluzioni approssimate.

"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

"The category-3 games are solved by a combination of expert knowledge, threat-space search, threat-sequence search, proof-number search (and database construction)." Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck
Quali di questi metodi possono tornarci utili?

Per migliorare la ricerca imperfetta in tempo reale.

Quando ci troviamo davanti ad una situazione di sconfitta o di pareggio, procrastiniamo (scegliamo la sconfitta più lenta e dolorosa) nella speranza che l'avversario effettui uno sbaglio nel frattempo. Questo funziona solo perché il nostro algoritmo è ottimale, mentre quello dell'avversario forse sì forse no.

Un algoritmo per l'esplorazione alfa-beta giudicato più efficiente:
https://en.wikipedia.org/wiki/Best_node_search
http://www.bjmc.lu.lv/fileadmin/user_upload/lu_portal/projekti/bjmc/Contents/770_7.pdf

Come suggerito dalle note storiche che parlano di MoGo.