Игра для программистов — Быки и коровы

    Привет Хабралюди. Я расскажу вам, как на Питоне написать движок и примерный бот игры для программистов. Игры для программистов — это такие игры, в которые играют не люди, а программы.


    Мы будем писать вариант игры «Быки и коровы», по-английски которая называется «Bulls and Cows». Правила оригинальной игры между двумя людьми можете прочитать тут.
    Правила нашей игры:
    1. Движок задумывает число, оно n значное и цифры в нем не могут повторяться. Движок сообщает программе-игроку число n
    2. Программа-игрок предполагает какое-то число, сообщает его движку
    3. Движок сообщает программе-игроку, сколько цифр из числа программы-игрока есть в задуманном и стоят на своем месте (Быки), и сколько есть в задуманно, но не стоят на своем месте (коровы).
    4. Если число не угаданно, возврат к п.2


    Программа-игрок будет общаться с движком посредством stdin/out. Наша спецификация предполагает, что движок запускает переданные ему в качестве аргументов программы-игроки.

    Движок



    Напишем вначале функциональные части:

    Copy Source | Copy HTML
    1.  
    2. #!/usr/bin/python
    3. import random
    4.  
    5. class Game(object):
    6.     def __init__(self, number=6):
    7.         if number > 10:
    8.             exit()
    9.         self.number = number
    10.         self.secret = self.make_secret(self.number)
    11.         self.main()
    12.  
    13.     def is_right_secret(self, secret):
    14.         """check all digits are different"""
    15.         dct = {}
    16.         for digit in secret:
    17.             try:
    18.                 if dct[digit]:
    19.                     return False
    20.             except KeyError:
    21.                 dct[digit] = True
    22.         return True
    23.  
    24.     def make_secret(self, number):
    25.         """generate number-counted secret"""
    26.         while True:
    27.             result = ""
    28.             for i in range(number):
    29.                 result += "%d" % random.randint( 0,9)
    30.             if self.is_right_secret(result):
    31.                 return result


    Здесь мы задумываем число, которое программы-игроки будут отгадывать. Также мы проверяем, чтобы все цифры в числе были разными. затем мы запускаем Game.main — основной цикл программы.

    Также необходимо дописать функцию подсчета быков и коров:

    Copy Source | Copy HTML
    1.  
    2. def count_bulls_cows(self, number, secret):
    3.      """count bulls and cows in number/secret"""
    4.      cows, bulls =  0,  0
    5.      dct = {}
    6.      for i in range(len(secret)):
    7.          if secret[i]==number[i]:
    8.              bulls += 1
    9.          else:
    10.              dct[secret[i]] = True
    11.              try:
    12.                  if dct[number[i]]:
    13.                      cows += 1
    14.              except KeyError:
    15.                  pass
    16.      return bulls, cows


    Теперь введем константы, которые будут обозначать кодовые слова для общения с программами игроками, и некоторые другие:

    Copy Source | Copy HTML
    1.  
    2. MESS_NUMBER_DIGITS = "number_digits" #start message
    3. MESS_GUESS = "guess!"
    4. MESS_COWS = "cows:" #If the matching digits on different positions, they are "cows" 
    5. MESS_BULLS = "bulls:" #If the matching digits are on their right positions, they are "bulls" 
    6. MESS_BULLS_COWS_SPLIT = "|" #Splitter between cows and bulls message
    7. MAX_TURN_NUMBER = 1000


    Теперь опишем игровой процесс в main(): (привожу с отладочными сообщениями)

    Copy Source | Copy HTML
    1. def main(self):
    2.     for player in self.players:
    3.         player.connect()
    4.         player.send("%s %d" % (MESS_NUMBER_DIGITS, self.number))
    5.         print ("%s %d" % (MESS_NUMBER_DIGITS, self.number))
    6.         starttime = time.time()
    7.         while True:
    8.             if player.turns > MAX_TURN_NUMBER:
    9.                 print ">>>> Player '%s' turns timeout" % player.name
    10.                 player.disconnect()
    11.                 break
    12.             answer = player.recieve()
    13.             print ">>>> Answer is %s" % answer
    14.             if len(self.secret)!=len(answer):
    15.                 self.stop_game("wrong number")
    16.             bulls, cows = self.count_bulls_cows(answer, self.secret)
    17.             if bulls==self.number:
    18.                 player.time = time.time() - starttime
    19.                 player.send("%s" % MESS_GUESS)
    20.                 player.disconnect()
    21.                 print ">>>> Player disconected"
    22.                 break
    23.             else:
    24.                 player.turns += 1
    25.                 player.send("%s %d%s%s %d" % (MESS_BULLS, bulls,\
    26.                         MESS_BULLS_COWS_SPLIT, MESS_COWS, cows))
    27.                 print(">>>> %s %d%s%s %d" % (MESS_BULLS, bulls,\
    28.                         MESS_BULLS_COWS_SPLIT, MESS_COWS, cows) )
    29.  
    30.     winner = self.players[ 0]
    31.     for player in self.players:
    32.         if player.turns<winner.turns:
    33.             winner = player
    34.     print ">>>> Winner name: %s" % winner.name


    Тут все понятно. По очереди играем с каждым игроком. Вначале отправляем количество цифр в загаданном числе. Засекаем время. Принимаем число-догадку игрока, если не угадал (число быков не равно числу цифр в числе) — отправляем число быков/коров и увеличиваем число ходов, потребовавшеясе игроку на отгадку, если угадал — останавливаем таймер, пишем ему что он выиграл, отключаемся от игрока, переходим к следующему.

    В конце выбираем победителя.

    Опишем машинерию соединения с процессами программ-игроков в классе Player:

    Copy Source | Copy HTML
    1.  
    2. class Player(object):
    3.     def __init__(self, name, progname):
    4.         self.name = name
    5.         self.turns =  0
    6.         self.time = -1
    7.         self.progname = progname
    8.  
    9.     def connect(self):
    10.         self.__proc = subprocess.Popen(self.progname, stdin=subprocess.PIPE,\
    11.                         stdout=subprocess.PIPE)
    12.  
    13.     def send(self, sendstring):
    14.         self.__proc.stdin.write(sendstring+'\n')
    15.  
    16.     def recieve(self)
    17.         return self.__proc.stdout.readline().strip('\n')
    18.  
    19.     def disconnect(self)
    20.         self.__proc.terminate()
    21.  


    Немного перепишем Game.__init__, чтобы инициализировать игроков:

    Copy Source | Copy HTML
    1. def __init__(self, number, players_progs):
    2.      if number > 10:
    3.          exit()
    4.      self.number = number
    5.      self.secret = self.make_secret(self.number)
    6.  
    7.      self.players = []
    8.  
    9.      for playername in players_progs:
    10.          self.players.append(Player(playername, players_progs[playername]))
    11.  
    12.      self.main()
    13.  


    Тупой бот



    Теперь надо потестировать получившееся. Для тестов нам нужна программа-игрок, самая простая. Она же потом будет api — классом, от которого настоящие программы-игроки будут наследоваться
    Создадим в папке проекта подпапку api, а в нем файл mooapi.py:

    Copy Source | Copy HTML
    1.  
    2. #!/usr/bin/python
    3. import random
    4. import sys
    5.  
    6. MESS_NUMBER_DIGITS = "number_digits" #start message
    7. MESS_GUESS = "guess!"
    8. MESS_COWS = "cows:" #If the matching digits on different positions, they are "cows" 
    9. MESS_BULLS = "bulls:" #If the matching digits are on their right positions, they are "bulls" 
    10. MESS_BULLS_COWS_SPLIT = "|" #Splitter between cows and bulls message
    11.  
    12.  
    13.  
    14. class MooPlayer(object):
    15.  
    16.     ##technical functions
    17.     def send(self, st):
    18.         sys.stdout.write("%s\n"%st)
    19.         sys.stdout.flush()
    20.  
    21.     def recieve(self):
    22.         return sys.stdin.readline().strip("\n")
    23.  
    24.  
    25.     def number_split(self, st):
    26.         num = st.split(' ')
    27.         if num[ 0]==MESS_NUMBER_DIGITS:
    28.             return int(num[1])
    29.         else:
    30.             exit()
    31.  
    32.     def answer_split(self, st):
    33.         try:
    34.             bullst, cowst = st.split(MESS_BULLS_COWS_SPLIT)
    35.         except ValueError:
    36.             exit()
    37.         bulls, cows = bullst.split(' '), cowst.split(' ')
    38.         if bulls[ 0]==MESS_BULLS and cows[ 0]==MESS_COWS:
    39.             return bulls[1], cows[1]
    40.         else:
    41.             exit()
    42.  
    43.     def main(self):
    44.         self.number = self.number_split(self.recieve())
    45.  
    46.         while True:
    47.             try:
    48.                 self.oldguess = guess
    49.                 guess = self.guess(cows=cows, bulls=bulls, firstrun=False)
    50.             except NameError:
    51.                 guess = self.guess(firstrun=True)
    52.             self.send(guess)
    53.             answer = self.recieve()
    54.             if answer == MESS_GUESS:
    55.                 exit()
    56.             else:
    57.                 bulls, cows = self.answer_split(answer)
    58.  
    59.  
    60.     ##some functions
    61.     def is_right_secret(self, secret):
    62.         """check all digits are different"""
    63.         dct = {}
    64.         for digit in secret:
    65.             try:
    66.                 if dct[digit]:
    67.                     return False
    68.             except KeyError:
    69.                 dct[digit] = True
    70.         return True
    71.  
    72.     def generate_number(self, number):
    73.         """generate number-counted secret"""
    74.         while True:
    75.             result = ""
    76.             for i in range(number):
    77.                 result += "%d" % random.randint( 0,9)
    78.             if self.is_right_secret(result):
    79.                 return result
    80.  
    81.     ############ Main guess function ###########
    82.     def guess(self, firstrun, bulls= 0, cows= 0):
    83.         """This is main api function. firstrun means that it is first time run,<br/>        bulls/cows is number of bulls and cows from last time.<br/>        also you have:<br/>            self.number  - number of digits<br/>            self.oldguess - old guess try<br/>        """
    84.         return self.generate_number(self.number)
    85.  
    86.  
    87. if __name__ == "__main__":
    88.     mooplayer = MooPlayer()
    89.     mooplayer.main()


    Тут все просто, часть кода скопированна из модуля движка, анализа никакого не происходит, просто угадывается случайным числом.
    Тому, кто будет писать программу-игрока, нужно будет импортировать модуль mooapi, наследовать свой класс от MooPlayer и переопределить функцию MooPlayer.guess()

    Почему я не импортировал модуль движка — для наглядности, тем, кто будет писать апи для других языков программирования.
    Теперь можно запустить программу-игрока и попробовать поиграть с ней в быки и коровы:

    >>number_digits 4
    5032
    >>bulls: 0|cows: 0
    4123
    >>bulls: 0|cows: 0
    2890
    >>bulls: 0|cows: 0
    2691
    >>guess!


    (>>) обозначает ввод с клавиатуры

    Запускаем



    теперь добавим в конец модуля движка:

    Copy Source | Copy HTML
    1.  
    2. if __name__ == "__main__":
    3.     game = Game(2, {'Player1':"api/mooapi.py", 'Player2':"api/mooapi.py", 'HabraMan':"api/mooapi.py" })


    Это запустит игру с двухзначными числами, тремя игроками с одинаковыми программами api/mooapi.py. С двухзначными — это чтобы наша тупая программа смогла угадать.

    Запустим модуль движка:
    >>>> bulls: 0|cows: 1
    >>>> Answer is 67
    >>>> bulls:1 cows:0
    >>>> bulls: 1|cows: 0
    >>>> Answer is 87
    >>>> bulls:0 cows:0
    >>>> bulls: 0|cows: 0
    >>>> Answer is 49
    >>>> bulls:0 cows:0
    >>>> bulls: 0|cows: 0
    >>>> Answer is 54
    >>>> bulls:0 cows:0
    >>>> bulls: 0|cows: 0
    >>>> Answer is 82
    >>>> bulls:1 cows:0
    >>>> bulls: 1|cows: 0
    >>>> Answer is 21
    >>>> bulls:0 cows:0
    >>>> bulls: 0|cows: 0
    >>>> Answer is 62
    >>>> bulls:2 cows:0
    >>>> Player disconected
    >>>> Winner name: HabraMan


    Работает!
    В следующем посте я расскажу, как сделать программу полезной — прикрутить к ней парсинг аргументов коммандной строки и вывод всего добра в xml, в котором хавает ввод наш будущий флеш-проигрыватель на нашем будущем сайте.

    Ссылка на полные тексты программ

    Радость от движка заключается в том, что его можно будет прикрутить на мультиюзерный сайт, который мы сейчас пишем.

    Вы можете стать первым, кто реализует алгоритм достопочтенного Кнута в нашем боте.

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 5

      +1
      Может в спец блог перенесете?

      Игры для программистов
        +3
        Господи, чем народ только не занимается.
          +3
          На первом курсе мы такое писали на паскале (вместе с алгоритмом кнута).
            0
            К сожалению для этой игры есть идеальный алгоритм.
              0
              только при маленьких значениях n вроде как

            Only users with full accounts can post comments. Log in, please.