菜单

一道简单的博弈论问题 (II play with GG)

3月 12, 2019 - 算法

写在前面

又有一段时间没更新博客了QAQ。这一段时间倒是也发生了很多事情,先是数模美赛,又是过年放假,到了新学期又是各种破事缠着,时间莫名其妙的就被占用了(其实是因为我懒),借着这两天4C选拔赛的机会,又把ACM的东西拾起来了一点(虽然比赛基本凉了),第二场选拔赛的时候正好碰到了一个挺好玩的博弈论问题,写出来留个纪念吧。

题目描述

之前的题干有点记不清楚了,好在牛客网上有一道几乎一模一样的题目,就拿这个题讲一讲吧。

IG won the S championship and many people are excited, ii and gg are no exception. After watching the game, the two of them also want to play a game.
There is now an infinite chessboard with only one piece. Initially the pieces are placed at the (x, y) position (the board coordinates are counted from 0). They took turns to move the pieces. ii moves first.
There are three ways to move
1. Move the piece to the left by one space (from (x, y) to (x-1, y)).
2. Move the piece down one space (from (x, y) to (x, y-1)).
3. Move the piece to the lower left by one space (from (x, y) to (x-1, y-1)).

It should be noted that the pieces cannot be removed from the board.
The first person who can not operate is judged negative (in other words, the first person who moves the piece to (0,0) wins).
Now give the initial coordinates x, y of the piece. Under the premise that both take the optimal strategy, please output the name of the winner (ii or gg).

Input

The input contains only one line. Enter two integers x y to represent the initial coordinates of the piece. (0 \leq x, y \leq 1000)

Output

the winner’s name (ii or gg)。

Sample Input

1 1
124 654

Sample Output

ii
gg

题目大意

这题的题干意思大致说,给定一个棋子所在的初始位置(x, y),由ii先手进行操作,每次操作有三种方式,向下,向左或者想左下方移动一格,也就是对应题干中的(x-1, y), (x, y-1), (x-1, y-1)这三种方式。如果轮到某个人操作时,没有可以移动的位置,则另一个人获得胜利。现在给出一个初始的起始位置,要求我们给出最后获胜的人的名字。

题目分析

首先我们明确,这是一道博弈论的题目,给出一个初始的状态,在双方都选择最优解的情况下,其游戏结果是确定的。对于这类问题,我们的思路应该是从简入难,从最基本的情况开始分析。
1. 考虑最简单的情况,如果初始状态下棋子放在(0,0),那么对于ii而言,游戏开局时就没有可以移动的方式,于是gg自动获胜。也就是说,在(0,0)时,先手必败。
2. 有了上一种情况的例子,我们很轻松的可以得到,如果先手方可以把棋子移到(0,0),那么后手方无法继续移动棋子,先手就能获得胜利。也就是说(0,1),(1,1),(1,0)这三种情况下,先手必胜。
3. 接下来我们考虑一条线,也就是说当初始状态下棋子在(x,0)或者在(0,x)的位置时的情况,由于规则的限制,移动只限制在向(0,x-1)和(x-1,0)位置进行,我们可以轻松的推出,当x为奇数时,先手必胜,x为偶数时,后手必胜。
4. 继续深入讨论,如果处于(1,x)的状态下,此时先手可以通过移动到(0,x)或(0,x-1)的位置来确保状态转移成(0,偶数)的情况,由于先手在下一次操作中相当于后手,也就是说先手可以确保自己这一次操作后达到后手必胜的结局,从而获得游戏的胜利。
5. 由上述分析我们可以得到,不管是对于谁在操作,都会极力避免通过自己的操作使得局面变成(1,x)或者(x,1)的局面,因此问题抽象成两条线上的问题,要么一直向左,要么一直向下,也就是说,再由之前的结论,我们可以总结得到最后的结果,当(x,y)均为偶数时,后手必胜,在其他情况下,先手必胜。

代码实现

博弈论的问题的特点也很明确,只要得到了结论,代码总是十分简单。

总结

这道题在博弈论里不算难题,但是难得我推出一道博弈论题目,还是赶紧把他记下来,省的以后忘记,也算是给这类问题填个坑吧。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注