Hallo!
Vielleicht kann mir jemand weiterhelfen: was ist die Grundy-Funktion, und wofür brauch ich sie? Ich weiß nur, dass sie aus der Graphentheorie kommt.
Besten Dank schon mal und
Schönen Gruß
Andre
Hallo,
Vielleicht kann mir jemand weiterhelfen: was ist die
Grundy-Funktion, und wofür brauch ich sie? Ich weiß nur, dass
sie aus der Graphentheorie kommt.
ich bin kein Mathematiker, aber ich habe folgende interessante Darstellung gefunden:
"3. Complexity
The mathematical foundations of game analysis were represented by four papers at this conference. More and more games are shown to be complete in polynomial space, a complexity class that contains as a subset the class of NP problems, in which most puzzle-type problems reside. PSPACE is likely strictly larger than NP, which makes games in general “more difficult” than puzzles. Informally, the difference in difficulty between puzzles and games lies in the verification of a solution. The solution to a puzzle can be verified easily, whereas verifying the solution to a game position is essentially as difficult as finding the solution in the first place, since each variation must be checked. Three papers in this section dealt with complexity results for various games, while the fourth paper involved combinatorial game theoretical analysis of a graph game.
Wolfgang Slany discussed complexity results for graph Ramsey games such as the game of Sim. In this game, players take turns colouring the edges of a graph until one player completes a monochromatic subset of edges isomorphic to a specified goal graph. Ramsey theory investigates the question: which graphs have the property that, when fully coloured, a monochromatic subgraph of either colour must exist? When a graph has this property, the game of Sim cannot end in a draw. Slany shows that these graph games are PSPACE-complete.
Sprague-Grundy theory forms the basis of combinatorial game theory for impartial games, where both players have identical move options. Aviezri Fraenkel uses this theory to analyse the two-player graph game Virus. Fraenkel’s paper discusses several examples of this game, as well as its connections to linear error correcting codes. A generalized Sprague-Grundy function is introduced that can compute Nim values on cyclic graphs. This function can distinguish between wins, losses, and draws by infinite play.
Two more complexity results conclude this section. Marcel Crâºmaru and John Tromp obtained a construction to prove that determining whether a ladder in Go works or not is PSPACE-complete, showing that even the simplest type of Go tactics is difficult. Their construction is more elegant than a previous PSPACE-hardness proof that focused on the capture of a large group of stones.
Finally, Michael Buro showed that endgames in Amazons are NP-complete. In the endgame phase, it frequently occurs that the board is partitioned into separate regions such that no region contains queens of two different colours. The game then effectively becomes a puzzle, with the players attempting to maximize their number of moves independently. NP-completeness is first proved for the Hamiltonian circuit problem for cubic subgraphs of the integer grid, which is then reduced to the Amazons endgame puzzle problem. "
Quelle: http://www.cs.ualberta.ca/~javhar/research/cg2000.doc
Vielleicht nützt es was.
Herzliche Grüße
Thomas Miller
Danke für deine Antwort 
(oT)