247 lines
12 KiB
TeX
247 lines
12 KiB
TeX
\documentclass{article}
|
||
|
||
\input{settings/common-preamble}
|
||
\input{settings/bmstu-preamble}
|
||
\input{settings/fancy-listings-preamble}
|
||
|
||
\def\makeyear{2021}
|
||
\def\grpNum{11М}
|
||
|
||
\begin{document}
|
||
\pagestyle{empty}
|
||
\makeBMSTUHeader
|
||
|
||
\makeReportTitle{лабораторной}{2}{Мультиагентные системы}{Распределённые информационные системы}{}{Локтев Д.А.}
|
||
\newpage
|
||
\tableofcontents
|
||
|
||
\lstlistoflistings
|
||
\newpage
|
||
\section{Результаты выполнения задания}
|
||
Задания выполнены с применением значений для варианта №11(2)
|
||
|
||
\section{Введение}
|
||
Целью работы является изучение подходов к проектированию мультиагентных систем и построению искусственного интеллекта, а также их реализация. Доработка алгоритма поведения игрока и компьютеров в игре Pacman реализуется на языке Python второй версии в среде разработки JetBrains PyCharm Community Edition.
|
||
|
||
\section{Улучшение агента ReflexAgent}
|
||
Комментарий к фукнции \code{evaluationFunction(self, currentGameState, action)} содержал следующие указания:
|
||
\begin{verbatim}
|
||
Реализуйте здесь лучшую оценочную функцию
|
||
Оценочная функция берет текущее и предполагаемое следующее состояние GameStates
|
||
(pacman.py) и возвращает число (чем больше число, тем лучше).
|
||
Код ниже содержит полезную информацию о состоянии, такую как оставшуюся еду
|
||
(newFood) и позицию пакмена после движения (newPos).
|
||
newScaredTimes содержит число шагов, в течении которых каждый призрак останется
|
||
напуганным, поскольку пакмен съел гранулу силы.
|
||
Выведите эти переменные, чтобы посмотреть, что в них находится, и затем
|
||
комбинируйте их для создания великолепной оценочной функции.
|
||
\end{verbatim}
|
||
|
||
Улучшенный код рефлексивного агента представлен в листинге \hyperref[lst:betterReflex]{\ref{lst:betterReflex}}. Результаты выполнения тестов, запушенных командой \code{python autograder.py -q -q1 -no-graphics} представлен в выводе \hyperref[fig:result1]{\ref{fig:result1}}.
|
||
|
||
\begin{lstlisting}[language=Python, caption=Улучшенный код агента, style=PyCodeStyle, label={lst:betterReflex}]
|
||
def evaluationFunction(self, currentGameState, action):
|
||
# Useful information you can extract from a GameState (pacman.py)
|
||
successorGameState = currentGameState.generatePacmanSuccessor(action)
|
||
newPos = successorGameState.getPacmanPosition()
|
||
newFood = successorGameState.getFood()
|
||
newGhostStates = successorGameState.getGhostStates()
|
||
newScaredTimes = [ghostState.scaredTimer for ghostState in newGhostStates]
|
||
currentPos = currentGameState.getPacmanPosition()
|
||
currentFood = currentGameState.getFood()
|
||
currentGhostStates = currentGameState.getGhostStates()
|
||
currentScaredTimes = [ghostState.scaredTimer for ghostState in currentGhostStates]
|
||
|
||
additional_score = 0
|
||
current_distance_to_food = float("inf")
|
||
current_distance_to_ghost = float("inf")
|
||
new_distance_to_food = float("inf")
|
||
new_distance_to_ghost = float("inf")
|
||
|
||
for food in newFood.asList():
|
||
d = manhattanDistance(food, newPos)
|
||
new_distance_to_food = min([new_distance_to_food, d])
|
||
|
||
pos_x, pos_y = newPos
|
||
if currentFood[pos_x][pos_y]:
|
||
additional_score += 10
|
||
|
||
food_before_action = len(currentFood.asList())
|
||
food_after_action = len(newFood.asList())
|
||
for ghost in successorGameState.getGhostPositions():
|
||
d = manhattanDistance(newPos, ghost)
|
||
new_distance_to_ghost = min([new_distance_to_ghost, d])
|
||
|
||
score = 1.0 / new_distance_to_food - food_after_action + additional_score
|
||
if new_distance_to_ghost < 2:
|
||
score -= 500
|
||
|
||
return score
|
||
\end{lstlisting}
|
||
|
||
\begin{figure}[H]
|
||
\renewcommand{\figurename}{Вывод}
|
||
\begin{verbatim}
|
||
Question q1
|
||
===========
|
||
|
||
Pacman emerges victorious! Score: 1246
|
||
Pacman emerges victorious! Score: 1241
|
||
Pacman emerges victorious! Score: 1233
|
||
Pacman emerges victorious! Score: 1232
|
||
Pacman emerges victorious! Score: 1241
|
||
Pacman emerges victorious! Score: 1245
|
||
Pacman emerges victorious! Score: 1233
|
||
Pacman emerges victorious! Score: 1239
|
||
Pacman emerges victorious! Score: 1237
|
||
Pacman emerges victorious! Score: 1242
|
||
Average Score: 1238.9
|
||
Scores: 1246.0, 1241.0, 1233.0, 1232.0, 1241.0, 1245.0, 1233.0,
|
||
1239.0, 1237.0, 1242.0
|
||
Win Rate: 10/10 (1.00)
|
||
Record: Win, Win, Win, Win, Win, Win, Win, Win, Win, Win
|
||
*** PASS: test_cases\q1\grade-agent.test (4 of 4 points)
|
||
*** 1238.9 average score (2 of 2 points)
|
||
*** Grading scheme:
|
||
*** < 500: 0 points
|
||
*** >= 500: 1 points
|
||
*** >= 1000: 2 points
|
||
*** 10 games not timed out (0 of 0 points)
|
||
*** Grading scheme:
|
||
*** < 10: fail
|
||
*** >= 10: 0 points
|
||
*** 10 wins (2 of 2 points)
|
||
*** Grading scheme:
|
||
*** < 1: fail
|
||
*** >= 1: 0 points
|
||
*** >= 5: 1 points
|
||
*** >= 10: 2 points
|
||
|
||
### Question q1: 4/4 ###
|
||
|
||
|
||
Finished at 22:04:54
|
||
|
||
Provisional grades
|
||
==================
|
||
Question q1: 4/4
|
||
------------------
|
||
Total: 4/4
|
||
|
||
Your grades are NOT yet registered. To register your grades, make sure
|
||
to follow your instructor's guidelines to receive credit on your project.
|
||
\end{verbatim}
|
||
\caption{Результат запуска улучшенного рефлексивного агента}
|
||
\label{fig:result1}
|
||
\end{figure}
|
||
|
||
\section{Улучшение алгоритма}
|
||
В рамках персонального задания было необходимо улучшить алгоритм альфа-бета отсечения (вариант 11(2)). Улучшенный код алгоритма представлен в листинге \hyperref[lst:alphaBeta]{\ref{lst:alphaBeta}}. Результаты выполнения тестов алгоритма, запушенных командой \code{python autograder.py -q -q2 -no-graphics} представлен в выводе \hyperref[fig:result2]{\ref{fig:result2}}.
|
||
|
||
\begin{lstlisting}[language=Python, caption=Улучшенный алгоритм Альфа-бета отсечение, style=PyCodeStyle, label={lst:alphaBeta}]
|
||
class AlphaBetaAgent(MultiAgentSearchAgent):
|
||
def maxvalue(self ,state, agentIndex, currentdepth, alpha, beta):
|
||
v = (float("-inf"), "Stop")
|
||
for action in state.getLegalActions(agentIndex):
|
||
v = max([v, (self.value(state.generateSuccessor(agentIndex, action), (currentdepth + 1) % self.number_of_agents, currentdepth + 1, alpha, beta), action)], key = lambda item:item[0])
|
||
if v[0] > beta:
|
||
return v
|
||
alpha = max(alpha, v[0])
|
||
return v
|
||
|
||
def minvalue(self, state, agentIndex, currentdepth, alpha, beta):
|
||
v = (float("inf"), "Stop")
|
||
for action in state.getLegalActions(agentIndex):
|
||
v = min([v, (self.value(state.generateSuccessor(agentIndex, action), (currentdepth + 1) % self.number_of_agents, currentdepth + 1, alpha, beta), action)], key = lambda item:item[0])
|
||
if v[0] < alpha:
|
||
return v
|
||
beta = min(beta, v[0])
|
||
return v
|
||
|
||
def value(self, state, agentIndex, currentdepth, alpha, beta):
|
||
if state.isLose() or state.isWin() or currentdepth >= self.depth * self.number_of_agents:
|
||
return self.evaluationFunction(state)
|
||
if (agentIndex == 0):
|
||
return self.maxvalue(state, agentIndex, currentdepth, alpha, beta)[0]
|
||
else:
|
||
return self.minvalue(state, agentIndex, currentdepth, alpha, beta)[0]
|
||
|
||
def getAction(self, gameState):
|
||
self.number_of_agents = gameState.getNumAgents()
|
||
alpha = float("-inf")
|
||
beta = float("inf")
|
||
path2 = self.maxvalue(gameState, 0, 0, alpha, beta)
|
||
return path2[1]
|
||
\end{lstlisting}
|
||
|
||
\begin{figure}[H]
|
||
\renewcommand{\figurename}{Вывод}
|
||
\begin{verbatim}
|
||
Question q2
|
||
===========
|
||
|
||
*** PASS: test_cases\q2\0-lecture-6-tree.test
|
||
*** PASS: test_cases\q2\0-small-tree.test
|
||
*** PASS: test_cases\q2\1-1-minmax.test
|
||
*** PASS: test_cases\q2\1-2-minmax.test
|
||
*** PASS: test_cases\q2\1-3-minmax.test
|
||
*** PASS: test_cases\q2\1-4-minmax.test
|
||
*** PASS: test_cases\q2\1-5-minmax.test
|
||
*** PASS: test_cases\q2\1-6-minmax.test
|
||
*** PASS: test_cases\q2\1-7-minmax.test
|
||
*** PASS: test_cases\q2\1-8-minmax.test
|
||
*** PASS: test_cases\q2\2-1a-vary-depth.test
|
||
*** PASS: test_cases\q2\2-1b-vary-depth.test
|
||
*** PASS: test_cases\q2\2-2a-vary-depth.test
|
||
*** PASS: test_cases\q2\2-2b-vary-depth.test
|
||
*** PASS: test_cases\q2\2-3a-vary-depth.test
|
||
*** PASS: test_cases\q2\2-3b-vary-depth.test
|
||
*** PASS: test_cases\q2\2-4a-vary-depth.test
|
||
*** PASS: test_cases\q2\2-4b-vary-depth.test
|
||
*** PASS: test_cases\q2\2-one-ghost-3level.test
|
||
*** PASS: test_cases\q2\3-one-ghost-4level.test
|
||
*** PASS: test_cases\q2\4-two-ghosts-3level.test
|
||
*** PASS: test_cases\q2\5-two-ghosts-4level.test
|
||
*** PASS: test_cases\q2\6-tied-root.test
|
||
*** PASS: test_cases\q2\7-1a-check-depth-one-ghost.test
|
||
*** PASS: test_cases\q2\7-1b-check-depth-one-ghost.test
|
||
*** PASS: test_cases\q2\7-1c-check-depth-one-ghost.test
|
||
*** PASS: test_cases\q2\7-2a-check-depth-two-ghosts.test
|
||
*** PASS: test_cases\q2\7-2b-check-depth-two-ghosts.test
|
||
*** PASS: test_cases\q2\7-2c-check-depth-two-ghosts.test
|
||
*** Running AlphaBetaAgent on smallClassic 1 time(s).
|
||
Pacman died! Score: 84
|
||
Average Score: 84.0
|
||
Scores: 84.0
|
||
Win Rate: 0/1 (0.00)
|
||
Record: Loss
|
||
*** Finished running AlphaBetaAgent on smallClassic after 1 seconds.
|
||
*** Won 0 out of 1 games. Average score: 84.000000 ***
|
||
*** PASS: test_cases\q2\8-pacman-game.test
|
||
|
||
### Question q2: 5/5 ###
|
||
|
||
Finished at 22:41:44
|
||
|
||
Provisional grades
|
||
==================
|
||
Question q2: 5/5
|
||
------------------
|
||
Total: 5/5
|
||
|
||
Your grades are NOT yet registered. To register your grades, make sure
|
||
to follow your instructor's guidelines to receive credit on your project.
|
||
\end{verbatim}
|
||
\caption{Результаты прохождения тестов алгоритма альфа-бета отсечения}
|
||
\label{fig:result2}
|
||
\end{figure}
|
||
|
||
\section{Выводы}
|
||
В рамках выполнения задания были применены алгоритмы, позволяющие построить искусственный интеллект способный победить в аркадной игре Pacman.
|
||
|
||
Оценочная функция позволяет достаточно быстро и точно, в выбранной метрике, указать оценку вероятности победы конкретного игрока для конкретного расположения фигур, не опираясь на то, каким образом игроки к этому состоянию пришли. Алгоритм альфа-бета отсечения является модификацией алгоритма минимакса, однако, в отличие от него, анализ некоторых ходов может быть не выполнен, то есть, прекратиться досрочно.
|
||
|
||
Агенты позволяют использовать существующее программное обеспечение, в контексте выполнения работы им являлась игра Pacman, для достижения своих целей -- победы. Алгоритмы их работы являются эвристическими и не гарантируют победу, а лишь позволяют с заданной быстротой и точностью достичь поставленной цели -- анализ текущей ситуации и выбор лучшего выхода из неё.
|
||
|
||
\end{document}
|