An Introduction To Combinatorial Games - Sciencesconf

1y ago
36 Views
1 Downloads
1.84 MB
16 Pages
Last View : Today
Last Download : 1m ago
Upload by : Emanuel Batten
Transcription

An introduction to combinatorial gamesEric Duchêne - Aline ParreauLIRIS - Université Lyon 1 - CNRSEcole Jeunes Chercheurs en Informatique MathématiqueLyon - 23 janvier 20171/13

IntroductionGames with:What 2 players playing alternately; perfect information.WhyChessCard gamesOthelloDraughtsWhoTic Tac ToeWhenPachisiGoMain question:Who is winning and how? Exact and approximate resolutions2/13

IntroductionCSMathsWhatCombinatoricsLogicNumber enNim gameby BoutonSpragueGrundyConwayTheoryDeep Games and graphs2/13

Reference books19761981200720133/13

Pure combinatorial games - a definitionBerlekamp, Conway, Guy (Winning Ways, 1981) 2 players: Left and Right, that play alternately and cannot pass theirturn; Perfect information, no chance; Finite number of moves, no draw, always a winner; Winner determined according to the last move (no scoring)ChessCard gamesTic Tac ToeOthelloPachisiDraughtsGo4/13

Game tree.5/13

Game treeNNPPPLRLPRNLP.PRRRNRRLLRR.P5/13

Computing the outcome of Domineering Unknown complexity on a n m board. When n and m are fixed:[Bullcock’s website]6/13

Decomposing Domineering into a sum of games7/13

How to play on a big Domineering game ?8/13

How to play on a big Domineering game ?8/13

Values of positions of Wythoff9/13

The PSPACE classDefinition: a decision problem is PSPACE if it can be solve in polynomialspace by a Turing Machine.The standard PSPACE-complete problem :Quantified Boolean Formula Input : A quantified boolean formula:Q1 x1 Q2 x2 .Qn xn , ϕ(x1 , ., xn )with Qi { , }, xi {0, 1} Output : Is the formula true ?An equivalent problem : QBF-Game10/13

ED-Geography is PSPACE-complete[Schaeffer 1978]Reduction from QBF-Game :(x1 x3 ) (x2 x3 ) (x1 x2 x3 )x1x1x2x2x3x3C1C2C311/13

Some nimbers sequencesArcKayles on a path00112031103322405223301130211045274 0 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 2 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7.Period 34 with some finite exceptions up to 52James Bond Game0 0 0 1 1 1 2 2 0 3 3 1 1 1 0 4.228 known values, periodicity conjectured0.106 Game0 1 0 0 0 1 2 2 2 1 4 4 0 1 0 6.Period 328226140474, with preperiod 465384263797.Guy’s conjecture: all finite octal games have periodic nimber sequence.12/13

ConclusionCurrent research questions ? Graphs and Games: combinatorial games version on graphs Metatheory: Misère, scoring games, loopy games Link with other fields:IIIArtificial Intelligence for generic gamesGame versions of parameters of graphsLogic, automata theory.Merci !13/13

Graphs and Games: combinatorial games version on graphs Metatheory: Misère, scoring games, loopy games Link with other elds: I Arti cial Intelligencefor generic games I Game versions ofparameters of graphs I Logic, automata theory. Merci ! 13/13