lecture_11組合博弈入門(編輯修改稿)
2024-08-18 02:07 本頁面
【文章內(nèi)容簡介】 DOJ_1850) ? Being a Good Boy in Spring Festival 2022/8/19 24 第三部分 Graph Games amp。 SpragueGrundy Function 2022/8/19 25 What is the graph game ? (1) Player I moves first, starting at x0. (2) Players alternate moves. (3) At position x, the player whose turn it is to move chooses a position y ∈ F(x). (4) The player who is confronted with a terminal position at his turn, and thus cannot move, loses. 2022/8/19 26 Example about graph game: 0,0,0 1,0,0 0,0,1 0,1,0 5,7,9 2,0,0 …… 2022/8/19 27 The SpragueGrundy Function. Definition: The SpragueGrundy function of a graph, (X,F), is a function, g, defined on X and taking nonnegative integer values, such that g(x) =min{n ≥ 0 : ng(y) for y ∈ F(x)}. (1) In words, g(x) the smallest nonnegative integer not found among the SpragueGrundy values of the followers of x. g(x) =mex{g(y) : y ∈ F(x)}. (2) 2022/8/19 28 Use of the SpragueGrundy Function: Ppositions: Positions x for which g(x) = 0 Npositions: Positions x for which g(x) 0 2022/8/19 29 Exercise: ? What is the SGvalue of the subtraction
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1