Для моих друзей, кто учится программировать. Тренируемся писать агента artificial intelligence для игры в реверси.

У меня есть друг, который недавно искал работу. И одна западная компания в процессе рассмотрения его кандидатуры выдала ему тестовое задание. Это вроде бы обычное дело. Но не совсем. Суть задания была в том, чтобы написать игровой AI.
Мне очень понравился такой формат тестового задания, и я решил собезьянничать и перенять эту методику. Таким образом можно помочь моим друзьям изучить некоторые основы из современного подхода к исскуственному интеллекту, а так же дать тестовое задание потенциальному кандидату, если такового нужно рассмотреть. 

Это может быть итересно любому начинающему программисту или более опытному, но недавно заинтересовавшемуся исскуственным интеллектом, алгоритмами, структурами данных и, местами, с умением решать проблеммы (так я перевел Problem Solving Skills).

Я набросал простенький сервер с которым можно сыграть по XML-RPC используя любимый язык программирования (python, lisp, C, C#, Java - кому что ближе), и некоторое количество людей уже пишет (или написали) свои решения.
У меня так же в круге знакомых есть ребята, изучающие программирование и computer science, которым хорошо бы потренироваться в таких вещах... В общем, публикую.


Задание:

Если Вы готовы принять интересный и необычный вызов, предлагаем Вам попробовать свои силы в программировании AI на Python.

Итак, основная интрига этого, надеюсь интересного задания, заключается в написании небольшого искусственного интеллекта, который сможет сыграть партию в РЕВЕРСИ с удаленным сервером, и, возможно, обыграть его (сервер имеет не очень сложного агента AI, а потому обыграть его не очень сложно)

Описание самой игры, надеюсь, будет несложно найти в интернете (например тут https://en.wikipedia.org/wiki/Reversi и тутhttp://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B2%D0%B5%D1%80%D1%81%D0%B8).

Суть задания:

Написать программу на Python 2.7, которая выполняет следующие действия:

1. подключается к серверу и запускает экземпляр игры

2. получает в ответ начальное состояние доски 8*8 в формате:

[[0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0],

[0,0,0,1,2,0,0,0],

[0,0,0,2,1,0,0,0],

[0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0]]

где каждый 0 - это свободная клетка доски, 1 - Ваши фишки, 2 - фишки противника.

3. принимает свое решение куда поставить фишку (решение принимает исск. интеллект)

4. отправляет серверу координаты Вашего хода в формате JSON в виде [вертикаль, горизонталь] (индексация с нуля) Если совершить недопустимый ход, сервер просто проигнорирует его и состояние доски не изменится.

5. получает ответ сервера с состоянием доски, после Вашего хода и ответного хода сервера.

Например:

ваш ход: [4, 2]

Ответ сервера может быть таким (сервер тоже сделал ход):

[[0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0],

[0,0,0,1,2,0,0,0],

[0,0,1,2,1,0,0,0],

[0,0,2,0,0,0,0,0],

[0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0]]

 Логика повторяется начиная с пункта 2, до тех пор, пока сервер не ответит, что игра закончена. 

ДОПОЛНИТЕЛЬНЫЕ ЗАМЕЧАНИЯ

От вас требуется реализовать логику того, как AI агент принимает решение о том, куда походить. 

API реализован на XML-RPC, вот примерный код киента на Python:

from xmlrpclib import ServerProxy

from board import Board
from AI import ReversiSimpleAI

game_server = ServerProxy("http://ai-labs.org:8006")
game_id = game_server.start_game('yourueser@gmail.com')

# Нужно реализовать этот класс (он содержит исск. интеллект, который)
# будет принимать решения какой ход сделать
ai = ReversiSimpleAI()

step = 0
while True:
    print '==============================='
    board = Board(game_server.get_board_state(game_id))
    board.pprint()

    # Вычисляем какой ход будет наиболее оптимальным,
    # алгоритм вы реализуете сами
    x, y = ai.get_best_move(board, 1) # 1 - is your player id 2 - server's player id
    
    state = game_server.move(x, y, game_id)

    step += 1

    board = Board(game_server.get_board_state(game_id))
    print '_______________________________'
    board.pprint()
    print state
    if state[1] == 'game_over':
        if board.score(1) > board.score(2):
            print "YOU'VE WON!!!", 'in ', step, 'steps'
        if board.score(1) == board.score(2):
            print 'EQUAL SCORE', 'in ', step, 'steps'
        if board.score(1) < board.score(2):
            print "YOU'VE LOST", 'in ', step, 'steps'
        
        print 'SCORE', board.score(1), board.score(2)
        break

print 'exiting'

Попробовать очень просто - сервер up and running, вперед!

Неплохо обзор подходов к решению таких задач описали Рассел и Норвиг в своей книге AIMA.

Так же много полезных знаний на этот счет можно найти в википедии.

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

Я сам когда-то реализовывал подобного рода алгоритмы и получил очень много фана сначала изобретая этот велосипед, потом изучая state-of-the-art, сравнивая свое (не такое уж и наивное решение) с классикой и таким образом совершенствуя свои знания и навыки.