![]() Proof idea: If the mouse is on the cycle and the cat is as well, the mouse can always 'run away' from the cat. no chords, etc.) and the mouse can reach the cycle before the cat, the game is not won for the cat. Proposition 2: If the graph contains a cycle of proper length at least 5 (i.e. This gives that the game is only lost for the cat whenever the mouse is too quick and we can proceed in analysing only drawn or winning scenarios. Note, that the mouse cannot 'sneak by' while the cat is away, that's an easy exercise. If the cat is adjacent to the hole and the cat has to move, move onto the hole. If the cat is on the hole and the cat has to move, do one of the following: If the mouse is adjacent to the cat, catch it. Proposition 1: If the cat reaches the hole before the mouse, the game is not won for the mouse. So then at step 1 of the algorithm, would node 4 in our new marked set contain (4, 4, cat) or (4, 4, mouse)?Īlike kotu in the comments, I do not fully understand what you want to achieve with your algorithm, but I'm sure that when playing the game you must assume perfect play, and thus the mouse will win in your example by simply moving to the hole.ĭetermining the game's outcome is not so trivial, so here are my observations: For example, in the picture below (where cat starts at 1, mouse starts at 5, and the hole is at 10), cat wins at vertex 4 in two ways: ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |