_Evoiz_'s blog

how to solve this problem ?
By _Evoiz_, history, 5 years ago, In English

what is the best way to solve this problem ? game theory? we have N*M empty grid and we have two players each player in his turn take an empty cell and put "X" in it game end when a player can make line with three "X" (like tik-tak-too game) players play optimally so who is the winier in this game?

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

Comments Comments (26)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by _Evoiz_ (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by _Evoiz_ (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the constraints on n, m? If they are very small, then we can do masking to solve this problem.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do diagonal lines also count?

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

Edited: Sorry, I totally misunderstood problem.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Since the player wins when 3 X's are together, the below solution assumes that either of m or n is greater than or equal to 3.

Player 1 wins only when both m and n are odd. Else player two will win.

The logic is simple. Suppose that either of m or n is not odd. Hence player 2 can always mimic turn of player 1 and upon getting appropriate chance it can make the winning move.

Where as if both m and n are odd, player 1 will place first X in the center square of grid and then player 1 will mimic each turn of player 2 thus on getting appropriate chance player 1 will make the winning move.

Thus player 1wins if both m and n are odd else player 2 wins

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think it's work , thank you.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, how can the second player win if we have 4x4 grid and the first player starts the game marking by "X" the field (2,2) (here it doesn't matter whether 0-based or 1-based coordinates are)?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i think if n or m less than or equal to two then their is no winner . or we can say that if player didn't find any empty cell he will be lose and game over . so we can see if n or m less than 3 this is special case, other this if n or m is even player 2 will wine

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if n or m is even then i can split the grid to two grid (n*m/2) or (n/2*m) and the second player make move like the first player

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We can't split it independently, the halfs will affect each other. In case of 4x4 grid and first step (2,2) the second player can't reply symmetrically, otherwise he looses.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          so how we solve it in your opinion?

          → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Assuming the grid is 3x3 (like the original tic-tac-toe), by your solution Player 1 is the winner, whereas when both playing optimally in original tic-tac-toe game (3x3 grid), the results are always end up in draws. It contradicts with your solution (I don't know the solution yet, though).

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if the first player put "X" in the center of grid ,what ever player two put his "X" the first will can make a line with three "X" .

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

    I didn't get, why if n is odd and m is even the second player wins. For example, if n = 3 and m = 4 then the first player can put X in cell (2, 2) (we suppose lines are numbered from 1 to 3 and columns from 1 to 4). Then the second player has to put in cell (2, 3), doesn't he? If he does, so the first player will win

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      that's true so we start again how to solve this problem ?

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please provide link to the problem so that we can also learn

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i am so sorry , their is no link because i write this problem and i didn't find a solution for it . i didn't see this problem in any other online judge before

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Quoting from this article. A 3-in-a-row game is a winning game for Player 1 if and only if N >= 3 and M >= 4 (number of row and column can be swapped). Otherwise, it's a draw game (3x3 or smaller grid).

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it's not like tic-tak-too because the two players play with "X"

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      p1: put "X" in cell (2,2)(center);p2: put"X" in cell (1,1);p1: put"X" in cell(3,3) and p1 win

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ah, I see. I'm sorry I misunderstood your problem thinking that thr X from Player 1 and 2 are different.

        → Reply