Prerequisite:

1. Combinatorics

2. Dynamic Programming

Resources:

https://codeforces.me/blog/entry/66040

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.

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..

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

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.

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