Solving Games and All That

Abdallah Saffidine

in Economics Thesis from University Paris Dauphine from Paris Dauphine University

Abstract: Efficient best-first search algorithms have been developed for deterministic two-player games with two-outcome.We present a formal framework to represent such best-first search algorithms.The framework is general enough to express popular algorithms such as Proof Number Search, Monte Carlo Tree Search, and the Product Propagation algorithm.We then show how a similar framework can be devised for two more general settings: two-player games with multiple outcomes, and the model checking problem in modal logic K.This gives rise to new Proof Number and Monte Carlo inspired search algorithms for these settings.Similarly, the alpha-beta pruning technique is known to be very important in games with sequential actions.We propose an extension of this technique for stacked-matrix games, a generalization of zero-sum perfect information two-player games that allows simultaneous moves

Keywords: Théorie des jeux; Monte-Carlo, Méthode de; Elagage Alpha-beta; Logique Modale K; Proof Number Search; Monte Carlo Tree Search; Intelligence artificielle (search for similar items in EconPapers)
JEL-codes: C15 C7 (search for similar items in EconPapers)
Date: 2013 Written 2013
Note: dissertation
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://basepub.dauphine.fr/xmlui/bitstream/123456789/14677/1/2013PA090069.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to basepub.dauphine.psl.eu:443 (Bad file descriptor) (http://basepub.dauphine.fr/xmlui/bitstream/123456789/14677/1/2013PA090069.pdf [301 Moved Permanently]--> https://basepub.dauphine.psl.eu/xmlui/bitstream/123456789/14677/1/2013PA090069.pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:dau:thesis:123456789/14677

Ordering information: This item can be ordered from
http://basepub.dauph ... ndle/123456789/14677

Access Statistics for this book

More books in Economics Thesis from University Paris Dauphine from Paris Dauphine University Contact information at EDIRC.
Bibliographic data for series maintained by Alexandre Faure ( this e-mail address is bad, please contact ).