Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 357 lines (300 sloc) 11.299 kb
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
1 """
2 An AI agent to play (and win) Spite and Malice
3 """
4
5 from model import *
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
6 from player import Player
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
7 import sys
8 import random
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
9 from copy import copy, deepcopy
62015956 » Pontiffx
2010-02-23 AI almost complete
10 from cardmodels import Card
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
11 from time import sleep
62015956 » Pontiffx
2010-02-23 AI almost complete
12 import logging
13
14 log = logging.getLogger("snm.agent")
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
15
16
17 class StateNode(object):
18 " A node in the search that represents a current state of the board "
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
19 SELF = "self"
20 OTHER = "other"
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
21
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
22 def __init__(self, state, action=None, parent_node=None):
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
23 self.state = state
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
24 self.action = action
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
25 self.parent_node = parent_node
26 self.child_nodes = []
62015956 » Pontiffx
2010-02-23 AI almost complete
27 self.util_value = 0
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
28 self.player = self.SELF
29
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
30 def __eq__(self, other):
31 " Override equality so that we can remove duplicate states. "
32 if other == None or type(other) != StateNode:
33 return False
34 if self.state == other.state and self.action == self.action:
35 return True
36 return False
37
38 def __ne__(self, other):
39 return not self.__eq__(other)
40
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
41 def __str__(self):
42 return "Node[%d](%s,%s,child_nodes:%d,player:%s)" % (
43 self.util_value, self.state, self.action, len(self.child_nodes), self.player)
44
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
45
46 class ComputerPlayer(Player):
47 """
48 An AI player for Spite and Malice. This uses a modified version of minimax that
49 checks each state to see which player is player, and evaluates accordingly.
50 """
51
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
52 MIN_VALUE = -sys.maxint
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
53 MAX_VALUE = sys.maxint
54
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
55 def __init__(self):
56 " setup the ai "
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
57 # list of moves stored up
58 self.play_queue = []
59
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
60 def play_card(self, game_state):
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
61 """
62 my_cards: cards in their hand, the top card on their payoff stack, and their discard piles.
63 opponents_cards: the top card of the opponents payoff stack, and their discard piles.
64 center_stacks: the enter center stacks
65 """
66 # play queued moves if we have some
67 if len(self.play_queue) > 0:
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
68 sleep(0.3)
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
69 return self.play_queue.pop(0)
70
71 # find the best possible move
62015956 » Pontiffx
2010-02-23 AI almost complete
72 self.terminal_nodes = []
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
73 node = StateNode(game_state)
62015956 » Pontiffx
2010-02-23 AI almost complete
74 self._evaluate(node)
75
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
76 self._build_play_queue()
77 return self.play_queue.pop(0)
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
78
79
62015956 » Pontiffx
2010-02-23 AI almost complete
80 def _evaluate(self, node):
81 " Evaluate a node, and recurse if necessary "
82 # no reason to get util for starting state
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
83 if node.parent_node:
62015956 » Pontiffx
2010-02-23 AI almost complete
84 node.util_value = self._utility(node)
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
85
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
86 if self._terminal_test(node):
62015956 » Pontiffx
2010-02-23 AI almost complete
87 log.info("Adding terminal state %s" % node)
88 self.terminal_nodes.append(node)
89 return
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
90
62015956 » Pontiffx
2010-02-23 AI almost complete
91 # evaluate all child nodes
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
92 for child_node in node.child_nodes:
62015956 » Pontiffx
2010-02-23 AI almost complete
93 self._evaluate(child_node)
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
94
95
96
97 def _terminal_test(self, node):
98 """
99 Check if this node is the last one in its path that we can use
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
100 to considerg moves. Calls sucessors to populate the child
101 nodes of the node.
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
102 """
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
103 # follow path and check if any CENTER moves were made
104 discard_only = True
105 cur_node = node
106 while cur_node:
107 if cur_node.action and cur_node.action.to_pile != DISCARD:
108 discard_only = False
62015956 » Pontiffx
2010-02-23 AI almost complete
109 log.info("Found a center move in %s" % (cur_node))
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
110 break
111 cur_node = cur_node.parent_node
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
112
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
113 # discard is only move
114 if node.action and node.action.to_pile == DISCARD and discard_only:
115 return True
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
116
62015956 » Pontiffx
2010-02-23 AI almost complete
117 # emptied hand without a discard
118 if node.action and len(node.state.get_player()[HAND]):
119 return True
120
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
121 # otherwise generate successors
122 node.child_nodes = self._successors(node)
123
124 # we've played center cards, so we want to see what the opponent can do
125 if node.action and node.action.to_pile == DISCARD and node.player == StateNode.SELF:
126 return False
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
127
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
128 # we can't determine any more moves for the other player
129 if node.player == StateNode.OTHER and not node.child_nodes:
130 return True
131
132 return False
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
133
134
135 def _successors(self, node):
136 """
137 Return a list of successor nodes for the current node. Each node is a valid move.
138 """
62015956 » Pontiffx
2010-02-23 AI almost complete
139 log.info("Generating successors for %s" % node)
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
140 node_list = []
141 # moves for the computer player
142 if node.player == StateNode.SELF and (not node.parent_node or \
143 node.parent_node.action.from_pile != DISCARD):
144
145 # moves to center
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
146 for pile_name, pile_len in [(HAND,1), (PAY_OFF,1), (DISCARD,4)]:
147 for pile_id in range(pile_len):
148 for action in self._get_center_move_from(node.state, pile_name, pile_id):
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
149 new_state = ComputerPlayer._new_state_from_action(node.state, action)
150 new_node = StateNode(new_state, action, node)
151 if new_node not in node_list:
152 node_list.append(new_node)
153
154 # moves to discard
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
155 for card in node.state.get_player()[HAND]:
156 for pile_id in range(len(node.state.get_player()[DISCARD])):
157 if Card.to_numeric_value(card) == 13:
158 continue
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
159 action = PlayerMove(card, from_pile=HAND, to_pile=DISCARD, to_id=pile_id)
160 new_state = ComputerPlayer._new_state_from_action(node.state, action)
161 new_node = StateNode(new_state, action, node)
162 if new_node not in node_list:
163 node_list.append(new_node)
164
165 return node_list
62015956 » Pontiffx
2010-02-23 AI almost complete
166
167 # TODO: assume apponent will always play pay_off if they can, do i need min/max ?
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
168 # opponent plays card on center
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
169 for pile_name, pile_len in [(PAY_OFF,1), (DISCARD,4)]:
170 for pile_id in range(pile_len):
171 for action in self._get_center_move_from(node.state, pile_name, pile_id, True):
62015956 » Pontiffx
2010-02-23 AI almost complete
172 new_state = ComputerPlayer._new_state_from_action(node.state, action, True)
173 new_node = StateNode(new_state, action, node)
174 if new_node not in node_list:
175 node_list.append(new_node)
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
176
177
178 @staticmethod
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
179 def _get_center_move_from(state, pile_name, pile_index, other_player=False):
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
180 " Get all the valid center stack placements from a pile "
181 moves = []
62015956 » Pontiffx
2010-02-23 AI almost complete
182
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
183 # set pile to HAND or PAY_OFF stacks
184 pile = state.get_player(other_player)[pile_name]
185 # otherwise, set it to top of DISCARD
186 if pile_name == DISCARD:
187 if len(state.get_player(other_player)[pile_name][pile_index]) < 1:
188 return moves
189 pile = [state.get_player(other_player)[pile_name][pile_index][-1]]
62015956 » Pontiffx
2010-02-23 AI almost complete
190
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
191 for i in range(len(pile)):
192 card = pile[i]
193 for center_id in range(len(state.center_stacks)):
194 if state.can_place_card_in_center(
195 state.center_stacks[center_id], card):
196 moves.append(PlayerMove(card, from_pile=pile_name, from_id=pile_index,
197 to_pile=CENTER, to_id=center_id))
198 return moves
199
200
201 @staticmethod
62015956 » Pontiffx
2010-02-23 AI almost complete
202 def _new_state_from_action(state, action, swap_player=False):
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
203 " Return a new state created from the previous state and the action "
204 new_state = deepcopy(state)
62015956 » Pontiffx
2010-02-23 AI almost complete
205 if swap_player:
206 new_state.swap_players()
43936276 » Pontiffx
2010-02-22 Some progress on AI. GameState now extends the game mode, so we can r…
207 new_state.place_card(action)
208 return new_state
209
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
210
211 def _utility(self, node):
62015956 » Pontiffx
2010-02-23 AI almost complete
212 """
213 Calculate the utility value for this state node.
214 Points:
215 +400 Play pay_off card
216 +120 Empty hand without a discard
217 +32 Discard on same value card
218 +10 Each time the discard card occures in the hard
219 +4 Each point away the closest center is from opponents pay off (max +48)
220 +2 Discard buries the least essential card
221 +1 Discard least essential card
222 -3 Each card in hand
223 -80 Opponent plays pay_off card
224 """
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
225 # TODO: small value for reducing size of discard, if it does not bring opponent closer
62015956 » Pontiffx
2010-02-23 AI almost complete
226 # shortcut vars
227 center_values = []
228 for pile in node.state.center_stacks:
229 if not pile:
230 center_values.append(0)
231 continue
232 center_values.append(Card.to_numeric_value(pile[-1]))
233 if node.player == StateNode.SELF:
234 myself = node.state.get_player()
235 other = node.state.get_player(True)
236 else:
237 myself = node.state.get_player(True)
238 other = node.state.get_player()
239
240 value = 0
241 if node.player == StateNode:
242 # pay off played
243 if node.action.from_pile == PAY_OFF:
244 value += 400
245 # empty hand without a discard
246 if len(myself[HAND]) == 0 and node.action.to_pile != DISCARD:
247 value += 120
248 # each time the discard cards value ocurs in the hand
249 if node.action.to_pile == DISCARD:
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
250 value += 10 * map(lambda c: Card.to_numeric_value(c), myself[HAND]).count(
62015956 » Pontiffx
2010-02-23 AI almost complete
251 Card.to_numeric_value(node.action.card))
252 # discard on same value card
253 if node.action.to_pile == DISCARD and \
254 len(myself[DISCARD][node.action.to_id]) > 1 and \
255 Card.to_numeric_value(myself[DISCARD][node.action.to_id][-1]) == \
256 Card.to_numeric_value(myself[DISCARD][node.action.to_id][-2]):
257 value += 32
258 # discad buries least essential card
259 elif node.action.to_pile == DISCARD:
260 discard_piles = []
261 for pile_id in len(range(myself[DISCARD])):
262 pile = myself[DISCARD][pile_id]
263 if len(pile) > 1 and node.action.to_id:
264 discard_piles.append(pile[-2])
265 elif len(pile) > 1:
266 discard_piles.append(pile[-1])
267 else:
268 discard_piles.append(None)
269 if node.action.to_id == self._find_least_essential_card(center_values,
270 discard_piles, myself[PAY_OFF][-1]):
271 value += 2
272 # discard least essential card
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
273 if node.action.to_pile == DISCARD and 0 == self._find_least_essential_card(
62015956 » Pontiffx
2010-02-23 AI almost complete
274 center_values, [node.action.card] + myself[HAND], myself[PAY_OFF][-1]):
275 value += 1
276
277 # each point away the closest center is from opponents pay off
278 value += 4 * self._distance_between_values(self._find_closest_center_stack_value(
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
279 center_values, other[PAY_OFF][-1]), other[PAY_OFF][-1])
62015956 » Pontiffx
2010-02-23 AI almost complete
280
281 # each card in hand
282 value -= 3 * len(myself[HAND])
283
284 else:
285 # opponent plays pay_off
286 if node.action.from_pile == PAY_OFF:
287 value -= 80
288
289 # cummulative utils
290 return value + node.parent_node.util_value
291
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
292
62015956 » Pontiffx
2010-02-23 AI almost complete
293 @staticmethod
294 def _find_least_essential_card(center_values, pile, pay_off_card):
295 """
296 Return the id in pile that is considered least essential relative to the
297 pay off card.
298 """
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
299 center_value = ComputerPlayer._find_closest_center_stack_value(center_values, pay_off_card)
300 list_values = map(lambda c: ComputerPlayer._distance_between_values(
301 center_value, Card.to_numeric_value(c)), pile)
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
302
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
303 return list_values.index(max(list_values))
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
304
305
62015956 » Pontiffx
2010-02-23 AI almost complete
306 @staticmethod
307 def _find_closest_center_stack_value(center_stacks, pay_off_card):
308 """
309 return the value from the center stack that is closest available
310 for playing the pay_off_card.
311 """
312 po_value = Card.to_numeric_value(pay_off_card)
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
313 return min(map(lambda c: ComputerPlayer._distance_between_values(Card.to_numeric_value(c), po_value), center_stacks))
62015956 » Pontiffx
2010-02-23 AI almost complete
314 # distance = ComputerPlayer.MAX_VALUE
315 # closest_value = None
316 # for stack_id in range(len(center_stacks)):
317 # card = center_stacks[stack_id]
318 # new_dist = self._distance_between(Card.to_numeric_value(card), po_value)
319 # if new_dist < distance:
320 # distance = new_dist
321 # closest_value = stack_id
322 # return closest_value
323
324
325 @staticmethod
326 def _distance_between_values(pile_card, play_card):
327 " find the distance between the pile card, and the play card values"
328 if pile_card == None:
329 return play_card
330 if play_card > pile_card:
331 return play_card - pile_card
332 if play_card == pile_card:
333 return 12
334 return 12 - pile_card + play_card
335
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
336 def _build_play_queue(self):
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
337 """
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
338 Find the best path, and build the play queue for this path.
339 In the case of a tie, pick a random path
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
340 """
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
341 node = max(self.terminal_nodes, key=lambda s: s.util_value)
342
343 chain = []
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
344 # loop while there are still nodes in the chain
345 while node:
59314717 » Pontiffx
2010-02-25 Adding logger for AI, AI running, still some bugs with util of discards
346 # skip any opponent nodes we have in the chain
347 if node.player == StateNode.OTHER:
348 node = node.parent_node
349 continue
350 chain.append(node.action)
351 node = node.parent_node
352
353 # remove the starting state, and reverse the list, so we can traverse the path
354 chain.pop()
355 chain.reverse()
356 log.info("Chosing path: %s" % (" ".join(map(str, chain))))
357 self.play_queue = chain
4306df92 » Pontiffx
2010-02-21 Refactored the game so the view is actually in the view, and players…
358
359
Something went wrong with that request. Please try again.