Блог пользователя pengyule

How to Find the Optimal Strategy When First See a Game Problem?
Автор pengyule, история, 2 года назад, По-английски

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?

  • Проголосовать: нравится
  • +31
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    → Ответить
»
2 года назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить