इस गेम को कैसे जीतें?

Question

समर्थन हमारे पास एक एन * एम टेबल है, और दो खिलाड़ी इस गेम को खेलते हैं। वे को में कोशिकाओं से बाहर निकलते हैं। एक खिलाड़ी सेल (i, j) चुन सकता है और (i, j) से (n, m) तक की सभी कोशिकाओं को रद्द कर सकता है, और अंतिम सेल से नियम कौन सा गेम खो देता है।

उदाहरण के लिए, 3 * 5 बोर्ड पर, खिलाड़ी 1 सेल (3,3) से (3,5) तक नियम करता है, और खिलाड़ी 2 नियम (2,5) से (3,5), वर्तमान बोर्ड इस तरह है: (ओ का मतलब है सेल से इंकार नहीं किया है, जबकि एक्स मतलब है कि यह की संभावना से इनकार कर रहा है)

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

और खिलाड़ी के बाद 1 नियम बाहर करने के लिए (2,1) से कोशिकाओं (3,5), बोर्ड

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

अब जो केवल छोड़ देता है (3,5) के लिए 2 नियम कोशिकाओं (1,2) से खिलाड़ी बन जाता है, (1,1) स्वच्छ:

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

तो खिलाड़ी 1 को केवल (1,1) सेल का नियम बनाना पड़ता है, क्योंकि एक खिलाड़ी को मोड़ में कम से कम एक सेल को रद्द करना होता है, और वह गेम खो देता है।

यह स्पष्ट रूप से है कि एन * एन, 1 * एन, और 2 * एन (एन> = 2) मामलों में, जो पहली जीत जीतता है।

मेरी समस्या यह है कि, क्या किसी खिलाड़ी के लिए सभी मामलों में गेम जीतने की कोई रणनीति है? क्या वह पहले खेलना चाहिए?

पी.एस

मुझे लगता है कि यह गतिशील प्रोग्रामिंग या विभाजित और जीत की तरह रणनीति से संबंधित है, लेकिन एक विचार करने के लिए अभी तक नहीं आया है। तो मैं इसे यहां पोस्ट करता हूं।

जवाब

sdcwc's link के लिए धन्यवाद। 1 * 1 से बड़ी टेबल के लिए, पहला खिलाड़ी जीत जाएगा। सबूत का पालन करें: (विकी पेज से उधार)

यह पता चला है कि किसी भी शुरू कर आयताकार के लिए स्थिति बड़ा 1 × 1 से 1 खिलाड़ी जीत सकते हैं। यह एक रणनीति-चोरी तर्क का उपयोग करके दिखाया जा सकता है: मान लें कि दूसरा प्लेयर किसी भी प्रारंभिक 1 प्लेयर चाल के विरुद्ध जीतने की रणनीति है। मान लीजिए, कि पहला खिलाड़ी केवल नीचे दाएं हाथ के वर्ग लेता है। हमारे धारणा से, दूसरे खिलाड़ी के पास प्रतिक्रिया है जो जीत को मजबूर करेगी। लेकिन अगर ऐसी जीत प्रतिक्रिया मौजूद है, तो पहला खिलाड़ी इसे अपने पहले कदम के रूप में खेला गया है और इस प्रकार जीत को मजबूर कर दिया गया है। दूसरा खिलाड़ी इसलिए रणनीति जीत नहीं सकती है।

और Zermelo's theorem ऐसी जीतने की रणनीति का अस्तित्व सुनिश्चित करता है।

Answer 1

इस गेम को Chomp के रूप में जाना जाता है। पहला खिलाड़ी जीतता है, अपनी रणनीति के लिए लिंक देखें (nonconstructive)।

Answer 2

एक बात यह है कि मन में आता है: अगर बोर्ड 2x2 है, पहले खिलाड़ी खो देता है: वास्तव में, इस बोर्ड से:

O O 
O O 

दो परिवर्तन होते हैं (ए और बी):

A.1)

1 1 
O O 

.2) पहले खिलाड़ी खो देता है

1 1 
O 2 

या, बी .1)

1 O 
O O 

बी .2) पहले खिलाड़ी इस बिंदु रणनीति बोर्ड के लिए मजबूर कर 2x2 चुकता बनने के लिए करने पर निर्भर करता पर

1 2 
O 2 

खो देता है; फिर, उस बोर्ड में प्रवेश करने वाला पहला इसे खो देगा। यह आपको आपकी रणनीति के दूसरे चरण में ले जाएगा, मुख्य रूप से:

यह सुनिश्चित करने के लिए कि आप इस तरह के कॉन्फ़िगरेशन में प्रवेश करने वाले नहीं हैं?

या,

कितने विन्यास वहाँ है कि मुझे इस तरह के एक विन्यास प्राप्त करने के लिए, एक बड़ा एक से शुरू नेतृत्व करेंगे कर रहे हैं? उदाहरण के लिए, एक 3x3 बोर्ड से शुरू:

O O O 
O O O 
O O O 

वहाँ कई रणनीतियों, कर रहे हैं, जो शुरू होता है पहले और कितने निरस्त माना जाता है पर निर्भर करता है; मैं इस बिंदु पर सुझाव देते हैं, एक आनुवंशिक एल्गोरिथ्म का उपयोग सबसे अच्छा समाधान का पता लगाने के (यह मज़ा! मुझे विश्वास है) :)

Answer 3

इस बार मैचों के साथ खेला एक खेल के समान है (नाम याद नहीं आ रहा)

वैसे भी मुझे लगता है कि यह जीतने वाले बोर्ड के आकार पर निर्भर करता है। 2 * 2 दूसरे खिलाड़ी के लिए मामूली रूप से हार जाता है और 2 * एन बोर्ड को 2 * 2 तक कम करके और दूसरे खिलाड़ी को खेलने के लिए मजबूर कर देता है। मुझे लगता है कि सभी वर्ग बोर्डों दूसरे खिलाड़ी जीत रहे हैं, जबकि आयताकार पहले खिलाड़ी जीत कर रहे हैं, लेकिन यह अभी तक नहीं साबित कर दिया

संपादित करें:

ठीक है मुझे लगता है कि यह एक वर्ग बोर्ड p1 के लिए है हमेशा चुनता 2,2 तो पंक्ति को संतुलित करता है और कॉलम सुनिश्चित करना कि पी 2

एसडीसीडब्ल्यूसी की टिप्पणी आयताकार बोर्ड के साथ ही पहली खिलाड़ी जीत भी है। केवल degenerate बोर्ड 1 * 1 एक दूसरा खिलाड़ी जीत

Answer 4

यहाँ एक अजगर प्रोग्राम है जो 1x1 से बड़ा बोर्डों के लिए जीतेंगे पहले जाने के लिए अनुमति दी है, तो है (लेकिन यह बोर्ड बड़ा 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) 

और एक नमूना रन से उत्पादन:

$ 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!