pengyule's blog

How to Find the Optimal Strategy When First See a Game Problem?
By pengyule, history, 2 years ago, In English

Hi, I am eager to know How to Find the Optimal Strategy When First See a Game Problem?

For example, CodeTON #2 Problem F Colouring Game, how do you know "start by taking RB/BR parts" is the smartest move, before you see the editorial?

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

Comments Comments (4)
| Write comment?
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I also find Game Problems hard,and I cannot solve them in contests.

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

Start from the losing condition and think about how each player can prevent that from happening. Alice loses when no red cells remain and Bob loses when no blue cells remain. Therefore, Alice should minimize loss of red cells and maximize loss of blue cells.

Now think about each of the possible moves. Alice can only play WR/RW, BR/RB, or RR as she must include at lease one red cell. BR/RB is strictly better than WR/RW because both reduce red cells by 1 while BR/RB also reduces blue cells by 1. RR is even worse as it reduces red cells by 2 without affecting blue cells.

Therefore, BR/RB is the best move for Alice (and the same logic applies to Bob).

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

    Thank you verrrrry much. I will try to apply this logic on other game problems.

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

Before getting too deep in the details I like to think: "If I was playing the game, how would I play?".

Right away, if I were playing as Alice I would not want to choose "RR" as that removes 2 Rs at once. Over "RR", I would prefer "RW" as it removes only 1 R, and over that I would prefer "RB" as that also removes a B for the other player. I think it's good to get a general intuition for how to play the game before trying to solve the problem.

→ Reply