Cómo ganar este juego?

Question

Soporte, tenemos una tabla de n * m, y dos jugadores juegan a este juego. Descartan las celdas a su vez. Un jugador puede elegir una celda (i, j) y descartar todas las celdas de (i, j) a (n, m), y quién descarta la última celda pierde el juego.

Por ejemplo, en una placa 3 * 5, el jugador 1 descarta la celda (3,3) a (3,5), y el jugador 2 descarta (2,5) a (3,5), la placa actual es así: (O significa que la célula no se descarta mientras que x significa que se descarta)

3 O O x x x 
2 O O O O x 
1 O O O O O 
    1 2 3 4 5 

y después de jugador 1 reglas a las células a partir de (2,1) a (3,5), la junta se convierte en

3 x x x x x 
2 x x x x x 
1 O O O O O 
    1 2 3 4 5 

Ahora el jugador 2 descarta células a partir de (1,2) a (3,5), que deja sólo (1,1) limpio:

3 x x x x x 
2 x x x x x 
1 O x x x x 
    1 2 3 4 5 

Así que el jugador 1 tiene que descartar la única (1,1) celda, ya que un jugador debe descartar al menos una casilla en un turno, y pierde el juego.

Es claro que en n * n, 1 * n, y 2 * n (n> = 2) casos, el que juega primero gana.

Mi problema es que, ¿hay alguna estrategia para que un jugador gane el juego en todos los casos? ¿Debería jugar primero?

P.S

creo que se relaciona con estrategias como la programación dinámica o dividir y conquistar, pero no ha llegado a una idea todavía. Así que lo publico aquí.

La respuesta

Gracias a sdcwc's link. Para tablas de más de 1 * 1, el primer jugador ganará. La prueba está sigue: (tomado de la página wiki)

Resulta que para cualquier rectangular posición más grande que 1 × 1 el primero jugador puede ganar a partir. Puede mostrarse usando un argumento de robo de estrategia : suponga que el 2º jugador tiene una estrategia ganadora contra cualquier movimiento inicial de 1er jugador . Supongamos entonces, que el 1er jugador toma solo el cuadrado inferior derecho de . Por nuestra suposición , el 2do jugador tiene una respuesta a esto que forzará victoria. Pero si existe una respuesta ganadora, el 1er jugador podría jugarla como su primer movimiento y forzar la victoria. El segundo jugador no puede tener una estrategia ganadora de .

Y Zermelo's theorem asegura la existencia de una estrategia ganadora.

Answer 1

Este juego se conoce como Chomp. El primer jugador gana, mira el enlace de su estrategia (no constructivo).

Answer 2

Una cosa que viene a la mente: si la tarjeta es 2x2, el primer jugador pierde: de hecho, desde este foro:

O O 
O O 

hay dos variaciones (ayb):

a.1)

1 1 
O O 

a.2) primer jugador pierde

1 1 
O 2 

o, b.1)

1 O 
O O 

b.2) primer jugador pierde

1 2 
O 2 

en este punto la estrategia se reduce a obligar a la junta para convertirse en 2x2 al cuadrado; entonces, el primero que entre en ese tablero lo perderá. Esto lo llevará al segundo paso de su estrategia, principalmente:

¿cómo asegurarse de que no es el que ingresa a dicha configuración?

o,

cuántas configuraciones están ahí que conducirá mí para obtener una configuración de este tipo, a partir de una más grande? Por ejemplo, a partir de una tabla de 3x3:

O O O 
O O O 
O O O 

hay varias estrategias, dependiendo de quién empieza primero y cuántos son anulados; Sugiero, en este punto, utilizando un algoritmo genético para explorar la mejor solución (es divertido! Créanme) :)

Answer 3

Esto es similar a un juego jugado a menudo con los partidos (no recuerdo el nombre)

De todos modos, creo que depende de la forma del tablero que gane. 2 * 2 es trivialmente una pérdida para el segundo jugador y 2 * N es trivialmente una pérdida para el primero al reducir el tablero a 2 * 2 y forzar al otro jugador a jugar. Creo que todas las placas cuadradas son segundo jugador gana, mientras que son rectangulares primeros jugador gana, pero no probado todavía

Editar:

Ok creo que es para un tablero cuadrado p1 siempre elige a continuación 2,2 equilibra la fila y la columna asegurando que p2 pierde

como con el comentario de sdcwc los tableros rectangluar también son un triunfo para el primer jugador. solo el tablero degenerado 1 * 1 es un 2do jugador gana

Answer 4

He aquí un programa Python que va a ganar para placas mayores de 1x1 si se le permite ir primero (pero es bastante lento para las placas más grandes que 10x10):

class State(object): 
    """A state is a set of spaces that haven't yet been ruled out. 
    Spaces are pairs of integers (x, y) where x and y >= 1.""" 

    # Only winnable states in this dictionary: 
    _next_moves = {} 
    # States where any play allows opponent to force a victory: 
    _lose_states = set() 

    def __init__(self, spaces): 
     self._spaces = frozenset(spaces) 

    @classmethod 
    def create_board(cls, x, y): 
     """Create a state with all spaces for the given board size.""" 
     return State([(r+1, c+1) for r in xrange(x) for c in xrange(y)]) 

    def __eq__(self, other): 
     return self._spaces == other._spaces 

    def __hash__(self): 
     return hash(self._spaces) 

    def play(self, move): 
     """Returns a new state where the given move has been played.""" 
     if move not in self._spaces: 
      raise ValueError('invalid move') 
     new_spaces = set() 
     for s in self._spaces: 
      if s[0] < move[0] or s[1] < move[1]: 
       new_spaces.add(s) 
     return State(new_spaces) 

    def winning_move(self): 
     """If this state is winnable, return a move that guarantees victory.""" 
     if self.is_winnable() and not self.is_empty(): 
      return State._next_moves[self] 
     return None 

    def random_move(self): 
     import random 
     candidates = [m for m in self._spaces if m[0] > 1 and m[1] > 1] 
     if candidates: return random.choice(candidates) 
     candidates = [m for m in self._spaces if m[0] > 1 or m[1] > 1] 
     if candidates: return random.choice(candidates) 
     return (1,1) 

    def minimal_move(self): 
     """Return a move that removes as few pieces as possible.""" 
     return max(self._spaces, key=lambda s:len(self.play(s)._spaces)) 

    def is_winnable(self): 
     """Return True if the current player can force a victory""" 
     if not self._spaces or self in State._next_moves: 
      return True 
     if self in State._lose_states: 
      return False 

     # Try the moves that remove the most spaces from the board first 
     plays = [(move, self.play(move)) for move in self._spaces] 
     plays.sort(key=lambda play:len(play[1]._spaces)) 
     for move, result in plays: 
      if not result.is_winnable(): 
       State._next_moves[self] = move 
       return True 
     # No moves can guarantee victory 
     State._lose_states.add(self) 
     return False 

    def is_empty(self): 
     return not self._spaces 

    def draw_board(self, rows, cols): 
     string = [] 
     for r in xrange(rows, 0, -1): 
      row = ['.'] * cols 
      for c in xrange(cols): 
       if (r, c+1) in self._spaces: 
        row[c] = 'o' 
      string.append(('%2d ' % r) + ' '.join(row)) 
     string.append(' ' + ''.join(('%2d' % c) for c in xrange(1, cols+1))) 
     return '\n'.join(string) 

    def __str__(self): 
     if not self._spaces: return '.' 
     rows = max(s[0] for s in self._spaces) 
     cols = max(s[1] for s in self._spaces) 
     return self.draw_board(rows, cols) 

    def __repr__(self): 
     return 'State(%r)' % sorted(self._spaces) 

def run_game(x, y): 
    turn = 1 
    state = State.create_board(x, y) 
    while True: 
     if state.is_empty(): 
      print 'Player %s wins!' % turn 
      return 
     if state.is_winnable(): 
      move = state.winning_move() 
     else: 
      move = state.random_move() 
     state = state.play(move) 
     print 'Player %s plays %s:' % (turn, move) 
     print state.draw_board(x, y) 
     print 
     turn = 3 - turn 

def challenge_computer(x, y): 
    state = State.create_board(x, y) 
    print "Your turn:" 
    print state.draw_board(x, y) 
    while True: 
     # Get valid user input 
     while True: 
      try: 
       move = input('Enter move: ') 
       if not (isinstance(move, tuple) and len(move) == 2): 
        raise SyntaxError 
       state = state.play(move) 
       break 
      except SyntaxError, NameError: 
       print 'Enter a pair of integers, for example: 1, 1' 
      except ValueError: 
       print 'Invalid move!' 
      except (EOFError, KeyboardInterrupt): 
       return 
     print state.draw_board(x, y) 
     if state.is_empty(): 
      print 'Computer wins!' 
      return 
     if state.is_winnable(): 
      move = state.winning_move() 
     else: 
      move = state.minimal_move() 
     state = state.play(move) 
     print 
     print 'Computer plays %s:' % (move,) 
     print state.draw_board(x, y) 
     print 
     if state.is_empty(): 
      print 'You win!' 
      return 

if __name__ == '__main__': 
    challenge_computer(8, 9) 

Y la salida de una ejecución de ejemplo:

$ python -c 'import game; game.run_game(8, 9)' 
Player 1 plays (6, 7): 
8 o o o o o o . . . 
7 o o o o o o . . . 
6 o o o o o o . . . 
5 o o o o o o o o o 
4 o o o o o o o o o 
3 o o o o o o o o o 
2 o o o o o o o o o 
1 o o o o o o o o o 
    1 2 3 4 5 6 7 8 9 

Player 2 plays (4, 8): 
8 o o o o o o . . . 
7 o o o o o o . . . 
6 o o o o o o . . . 
5 o o o o o o o . . 
4 o o o o o o o . . 
3 o o o o o o o o o 
2 o o o o o o o o o 
1 o o o o o o o o o 
    1 2 3 4 5 6 7 8 9 

Player 1 plays (5, 1): 
8 . . . . . . . . . 
7 . . . . . . . . . 
6 . . . . . . . . . 
5 . . . . . . . . . 
4 o o o o o o o . . 
3 o o o o o o o o o 
2 o o o o o o o o o 
1 o o o o o o o o o 
    1 2 3 4 5 6 7 8 9 

Player 2 plays (3, 7): 
8 . . . . . . . . . 
7 . . . . . . . . . 
6 . . . . . . . . . 
5 . . . . . . . . . 
4 o o o o o o . . . 
3 o o o o o o . . . 
2 o o o o o o o o o 
1 o o o o o o o o o 
    1 2 3 4 5 6 7 8 9 

Player 1 plays (4, 1): 
8 . . . . . . . . . 
7 . . . . . . . . . 
6 . . . . . . . . . 
5 . . . . . . . . . 
4 . . . . . . . . . 
3 o o o o o o . . . 
2 o o o o o o o o o 
1 o o o o o o o o o 
    1 2 3 4 5 6 7 8 9 

Player 2 plays (2, 3): 
8 . . . . . . . . . 
7 . . . . . . . . . 
6 . . . . . . . . . 
5 . . . . . . . . . 
4 . . . . . . . . . 
3 o o . . . . . . . 
2 o o . . . . . . . 
1 o o o o o o o o o 
    1 2 3 4 5 6 7 8 9 

Player 1 plays (1, 5): 
8 . . . . . . . . . 
7 . . . . . . . . . 
6 . . . . . . . . . 
5 . . . . . . . . . 
4 . . . . . . . . . 
3 o o . . . . . . . 
2 o o . . . . . . . 
1 o o o o . . . . . 
    1 2 3 4 5 6 7 8 9 

Player 2 plays (2, 2): 
8 . . . . . . . . . 
7 . . . . . . . . . 
6 . . . . . . . . . 
5 . . . . . . . . . 
4 . . . . . . . . . 
3 o . . . . . . . . 
2 o . . . . . . . . 
1 o o o o . . . . . 
    1 2 3 4 5 6 7 8 9 

Player 1 plays (1, 4): 
8 . . . . . . . . . 
7 . . . . . . . . . 
6 . . . . . . . . . 
5 . . . . . . . . . 
4 . . . . . . . . . 
3 o . . . . . . . . 
2 o . . . . . . . . 
1 o o o . . . . . . 
    1 2 3 4 5 6 7 8 9 

Player 2 plays (2, 1): 
8 . . . . . . . . . 
7 . . . . . . . . . 
6 . . . . . . . . . 
5 . . . . . . . . . 
4 . . . . . . . . . 
3 . . . . . . . . . 
2 . . . . . . . . . 
1 o o o . . . . . . 
    1 2 3 4 5 6 7 8 9 

Player 1 plays (1, 2): 
8 . . . . . . . . . 
7 . . . . . . . . . 
6 . . . . . . . . . 
5 . . . . . . . . . 
4 . . . . . . . . . 
3 . . . . . . . . . 
2 . . . . . . . . . 
1 o . . . . . . . . 
    1 2 3 4 5 6 7 8 9 

Player 2 plays (1, 1): 
8 . . . . . . . . . 
7 . . . . . . . . . 
6 . . . . . . . . . 
5 . . . . . . . . . 
4 . . . . . . . . . 
3 . . . . . . . . . 
2 . . . . . . . . . 
1 . . . . . . . . . 
    1 2 3 4 5 6 7 8 9 

Player 1 wins!