The_mysterio's blog

Game-Theory problems
By The_mysterio, history, 4 years ago, In English

Hello Codeforces community, A newbie here.My name is Sayan Chaudhuri and I am from India. Although as you can see my rating is low, I particularly face high difficulty while solving problems based on games. Like problems of DIv 3C or Div2B which often are problems based on games, I find it extremely troubling to solve them. I just get bamboozled when I find the term "optimally" as it does not occur to me, what an optimal move could be...So, how do you guys approach these problems on games.. If anyone can give me some intution or any sort of other help that may help me to overcome this difficulty. round 668 div2 problem B Sequential Nim- this problem is an example. I am not just able to understand how to solve it.... Thanking you in advance...

  • Vote: I like it
  • +15
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

Prerequisite:

  1. Combinatorics

  2. Dynamic Programming

Resources:

https://mirror.codeforces.com/blog/entry/66040

→ Reply
»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

There is no generalization to such problems. These can be based on constructive thinking, some simple if-else criteria, Nim's game, combinatorics, greedy or dp. Again, these are only a few possibilities that I have came across, there is NO generalization.

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Thanks for your feedback. The problems that I have encountered so far normally involve simple if else ....let's see how can I improve further on this..

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

When I have no idea what the optimal play is I try to play the game on paper for both the players and choose what would be optimal for both sides, and after that it is easier to see the optimal play for both players

→ Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

First of all, I have no idea why are you getting down vote.

I will explain how I approach Game theory problems with two examples:

Consider problem 1404B - Tree Tag (which I was able to solve):

Thinking about: How would I win the game if I was Alice?

  • If I can reach Bob in the first move, I am the winner, obviously.
  • If $$$da \ge db$$$, I will win probably, as the game lasts for $$$10^{100}$$$ moves. Bob will try to escape to one of the leaves because he can't jump over me (I can reach him if he does).
  • If $$$2 \times da \ge db$$$, Bob won't be able to jump over me on the path between me and Bob, Because I will be able to catch him on the next move. Then I can decrease the number of possible vertices that Bob can stay in. this way I will win.
  • Obviously if $$$db$$$ is quite big (Bigger that the diameter of the tree for instance) then there should be some situations that I can also win.
  • So let $$$diam$$$ be the length of the diameter of the tree. if $$$2 \times da \ge diam$$$ then I will probably win, because again Bob is not able to jump over me on the path between us (As there is no path longer that $$$2 \times da$$$)

This leads to (Let the length of the path between us be $$$dist$$$):

  • If $$$da \ge dist$$$ I'll win on the first move.
  • If $$$2 \times da \ge \min(diam, db)$$$ I'll win.

Now what if I am Bob? How would I win?

  • In situations other than than those two if statements, I will be able to jump over Alice on the path between us in the tree. So she will never catch me.

And the problem is solved. Note that the process of solving the problem has two parts (In two player games), and in each part, you should come up with some if statements. Start from easy conditions, write them on paper, and go on. Remember that most of the game problems are solved using easy terms. Referring to 1375F - Integer Game. Many scared from "Print First or Second" part. But the solution was to win in 2-3 steps. The main reason for not solving the task during the contest is having fear.

Now consider 1404D - Game of Pairs (which I wasn't able to solve):

Yeah I didn't solve it during the contest, but I have something to say.

Thinking about: How should I win as First?

  • Ok, I have no idea.

Thinking about: How should I win as Second?

  • Well, I don't know.

So what to do in these situations? Leaving the contest is the option for many people, but for me, it was: try to solve it for small $$$n$$$. This way I guessed that the solution is based on the parity of $$$n$$$. It should be a nice attempt when you have no idea, and helps you to guess the condition in problems that the condition is short, which was the case for this problem.

So what else? Now I may assume that for even $$$n$$$ I can win as First. Here you should be able to come up with some ideas, which is achieved through effort and solving many problems in a wide range of topics. Actually I didn't come up with the idea of "matching congruent numbers in modulo $$$n$$$", so the thinking process ends here for me. I am pretty sure that I would solve it if I had solved enough amount of problems before the contest. Solving $$$x$$$ number of Game theory problems means (at least) $$$x$$$ number of Game theory winning strategy ideas most of the times. Solve problems, be red.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First thanks to you for raising the concern as to why people downvote me.. Secondly a hell lot of thanks to you for writing this awesome advice...I shall try to follow your words. One doubt that I raised in an earlier comment above is what should each player focus on..making the other one play a losing move or playing a winning move for oneself?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Playing a winning move and making the other to play a losing move of course. It may happen that thinking about one of them is easier on some problem, and the other on some other problem. You should try all of your ideas when solving a task.

      You may think of a digraph (actually a DAG in many games) which each vertex is a state, which describes how is the situation of the game right now? For example in 1404B - Tree Tag, an state is pair of (Alice's current vertex, Bob's current vertex), so we have $$$n^2$$$ vertices. I can't imagine a graph for 1404D - Game of Pairs because that game doesn't have step moves and the game has only one move for each player.

      So if the graph is a DAG meaning there is no cycle in the game (The game ends without even considering the moves of two players) You can label each vertex as a Winning state or a Losing state. A winning state is a vertex which has at least one edge going through a Losing state vertex, and a losing state has no edge going through another losing state. The set of losing state vertices is called Kernel in terms of graph theory. An edge going through a losing vertex is a losing move, and similarly an edge going through a winning vertex is a winning move. I don't know any English resource for learning basic game theory ideas (May be cp-algorithms), but surely you'll find a nice one using Google.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Why is this downvoted??

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Is there a reasonable reason to downvote this blog? Really I'm eager to know.

→ Reply