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

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


Мы будем писать вариант игры «Быки и коровы», по-английски которая называется «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, в котором хавает ввод наш будущий флеш-проигрыватель на нашем будущем сайте.

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

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

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