0

How to Find the Optimal Strategy When First See a Game Problem?

 2 years ago
source link: http://codeforces.com/blog/entry/105541
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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?

12 hours ago, # |

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

12 hours ago, # |

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

  • 6 hours ago, # ^ |

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

    • 1 minute ago, # ^ |

      As a MO student, the approach we often take is to consider what is a losing position for the person who is taking first. When we have found a pattern to that, let us say we are taking first. Then, after our move, we try to leave the above position to our opponent so that they will definitely lose the game. Thus, we can recursively make a list of losing and winning positions, and eventually find some pattern.

4 hours ago, # |

With Game problem did you mean Game Theory problem?

26 minutes ago, # |

← Rev. 2 →  

+1

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.

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK