Два хороших ответа. I’d добавляют немного приема — при необходимости в реальном объекте файла (некоторые методы ожидают один, не только интерфейс), вот способ создать адаптер:
Эта игра известна как Chomp . Побеждает первый игрок, см. Ссылку на его стратегию (неконструктивная).
Это похоже на игру, в которую часто играют спичками (не могу вспомнить название)
В любом случае, я думаю, кто выиграет, это зависит от формы доски. 2 * 2 банально проигрывает второму игроку, а 2 * N - тривиально проигрышу для первого из-за уменьшения поля до 2 * 2 и принуждения другого игрока к игре. Я думаю, что все квадратные доски - это победы второго игрока, а прямоугольные - это победы первого игрока, но это еще не доказано
Редактировать:
Хорошо, я думаю, что для квадратной доски p1 всегда выбирает 2,2, а затем уравновешивает строку и столбец обеспечение поражения p2
, как и в случае с комментарием sdcwc, прямоугольные доски также являются победой первого игрока. только вырожденная доска 1 * 1 является победой второго игрока
На ум приходит одна вещь: если доска 2x2, первый игрок проигрывает: фактически, с этой доски:
O O
O O
есть два варианта (a и b):
a.1)
1 1
O O
a.2) первый игрок проигрывает
1 1
O 2
или, b.1)
1 O
O O
b.2) первый игрок проигрывает
1 2
O 2
на этом этапе стратегия сводится к тому, чтобы заставить доску стать 2х2 в квадрате; тогда тот, кто первым войдет в эту доску, потеряет ее. Это приведет вас ко второму шагу вашей стратегии, в основном:
как убедиться, что вы не тот, кто вводит такую конфигурацию?
или,
, сколько существует конфигураций, которые позволят мне получить такая конфигурация, начиная с более крупной? Например, начиная с доски 3x3:
O O O
O O O
O O O
есть несколько стратегий, в зависимости от того, кто начинает первым и сколько аннулируется; На этом этапе я предлагаю
Вот программа Python, которая выиграет для плат размером больше 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!