《逻辑、计算和博弈 (30).pdf》由会员分享，可在线阅读，更多相关《逻辑、计算和博弈 (30).pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 LOGIC,COMPUTATION AND GAMES Logic and Game Design Graph games (many versions)analyze complexity of computation,logic,argumentation Intermediate between logic games and game logic We will discuss some examples broader program in van Benthem&Liu 2019 Travel Game and Modal Logic Graph 1 Traveler has w
2、inning strategy starting in 1 Demon has w.s.when Traveler starts in 2 Graph 2 Traveler has w.s.starting in 2 The Sabotage Game original motivation Dutch railways 2004 The Sabotage Game algorithmic tasks under disturbance complexity jumps for perturbed Graph Search problem in general larger goal regi
3、ons Zermelo:game is determined solution complexity Pspace-complete interesting special cases trees best cut links locally,grids geometrical solids:winning positions with goal region sizes on Cube Sabotage Modal Logic Modal language for studying the game via its graph invariants truth values of compl
4、ex formulas can change after deletion dynamic logic of graph change(cf.Weeks 13)Counter-Example Open problem Axiomatize the schematic validities of SML Some Theory(by Students)Computational complexity Model checking Pspace-complete(for modal logic:Ptime)SAT undecidable(for modal logic:Pspace-complet
5、e)First-order translation exists,but needs memory validities axiomatizable in principle,no PALDEL-style reduction Sabotage bisimulation and invariance Student contributions:Aachen,Stanford,Beijing(Li Dazhu,Zhang Tianwei)Axiomatizing validities JvB,Shi Chenwei,Lilei,Yin Haoxuan further open problems:
6、ask us Local Sabotage,Graded Modal Logic player E does not know which move A played Zero-One Law and Random Graph Dotted lines:epistemic uncertainty relations modal epistemic action language Proof:analyze truth on the countable random graph Also holds for modal logic,by its translation into FOL.Even
7、 for first-order fixed-point logic LFP(FO)(Week 6)that defines players winning powers in sabotage game Fact(Chris Mierzewski)Probability 1 for WINT The sabotage game is massively in favor of Traveler!Contrast with DEL-style Update Logic Analogies with Week 1 topic,but also contrasts:Reports on Symbo
8、lic Logic 2020,JvB,KM&F Z-B Turn PAL into logic of stepwise object removal From PAL to MLSR Current project Fenrong Liu,Sujata Ghosh Game Design and Taxonomy Current project Fenrong Liu,Sujata Ghosh Logical Issues Connections to the game logics of week 6?Imperfect Information Information and Questions General information-theoretic analysis number of questions needed in dynamic search?DEL,Temporal Logic,Game Logic Connect with dynamic epistemic temporal logic In general,games like this will need probabilistic equilibria Real Games ongoing research at the ILLC