1# 2# This file is part of Gambit 3# Copyright (c) 1994-2016, The Gambit Project (http://www.gambit-project.org) 4# 5# FILE: src/python/gambit/lib/stratspt.pxi 6# Cython wrapper for strategy supports 7# 8# This program is free software; you can redistribute it and/or modify 9# it under the terms of the GNU General Public License as published by 10# the Free Software Foundation; either version 2 of the License, or 11# (at your option) any later version. 12# 13# This program is distributed in the hope that it will be useful, 14# but WITHOUT ANY WARRANTY; without even the implied warranty of 15# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16# GNU General Public License for more details. 17# 18# You should have received a copy of the GNU General Public License 19# along with this program; if not, write to the Free Software 20# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 21# 22import itertools 23from cython.operator cimport dereference as deref 24from gambit.lib.error import UndefinedOperationError 25 26cdef class StrategySupportProfile(Collection): 27 """ 28 A set-like object representing a subset of the strategies in game, incorporating 29 the restriction that each player must have at least one strategy in the set. 30 """ 31 cdef c_StrategySupportProfile *support 32 33 def __init__(self, strategies, Game game not None): 34 self.support = (<c_StrategySupportProfile *>0) 35 if self.is_valid(strategies, len(game.players)): 36 temp_restriction = <StrategicRestriction>game.mixed_strategy_profile().restriction() 37 self.support = new c_StrategySupportProfile(deref(temp_restriction.support)) 38 for strategy in game.strategies: 39 if strategy not in strategies: 40 self.support.RemoveStrategy((<Strategy>strategy).strategy) 41 else: 42 raise ValueError("invalid set of strategies") 43 def __dealloc__(self): 44 if self.support != (<c_StrategySupportProfile *>0): 45 del self.support 46 def __len__(self): return self.support.MixedProfileLength() 47 def __richcmp__(StrategySupportProfile self, other, whichop): 48 if isinstance(other, StrategySupportProfile): 49 if whichop == 1: 50 return self.issubset(other) 51 elif whichop == 2: 52 return deref(self.support) == deref((<StrategySupportProfile>other).support) 53 elif whichop == 3: 54 return deref(self.support) != deref((<StrategySupportProfile>other).support) 55 elif whichop == 5: 56 return self.issuperset(other) 57 else: 58 raise NotImplementedError 59 else: 60 if whichop == 2: 61 return False 62 elif whichop == 3: 63 return True 64 else: 65 raise NotImplementedError 66 def __getitem__(self, strat): 67 if not isinstance(strat, int): 68 return Collection.__getitem__(self, strat) 69 cdef Array[int] num_strategies 70 cdef Strategy s 71 num_strategies = self.support.NumStrategies() 72 for i in range(1,num_strategies.Length()+1): 73 if strat - num_strategies.getitem(i) < 0: 74 s = Strategy() 75 s.strategy = self.support.GetStrategy(i, strat+1) 76 s.restriction = self.restrict() 77 return s 78 strat = strat - num_strategies.getitem(i) 79 raise IndexError("Index out of range") 80 # Set-like methods 81 def __and__(self, other): 82 if isinstance(other, StrategySupportProfile): 83 return self.intersection(other) 84 raise NotImplementedError 85 def __or__(self, other): 86 if isinstance(other, StrategySupportProfile): 87 return self.union(other) 88 raise NotImplementedError 89 def __sub__(self, other): 90 if isinstance(other, StrategySupportProfile): 91 return self.difference(other) 92 raise NotImplementedError 93 94 def remove(self, strategy): 95 if isinstance(strategy, Strategy): 96 if len(filter(lambda x: x.player == strategy.player, self)) > 1: 97 strategies = list(self)[:] 98 strategies.remove(strategy) 99 return StrategySupportProfile(strategies, self.game) 100 else: 101 raise UndefinedOperationError("cannot remove last strategy"\ 102 " of a player") 103 raise TypeError("delete requires a Strategy object") 104 105 def difference(self, StrategySupportProfile other): 106 return StrategySupportProfile(filter(lambda x: x not in other, self), self.game) 107 108 def intersection(self, StrategySupportProfile other): 109 return StrategySupportProfile(filter(lambda x: x in other, self), self.game) 110 111 def is_valid(self, strategies, num_players): 112 if len(set([strat.player.number for strat in strategies])) == num_players \ 113 & num_players >= 1: 114 return True 115 return False 116 117 def issubset(self, StrategySupportProfile other): 118 return reduce(lambda acc,st: acc & (st in other), self, True) 119 120 def issuperset(self, StrategySupportProfile other): 121 return other.issubset(self) 122 123 def restrict(self): 124 cdef StrategicRestriction restriction 125 restriction = StrategicRestriction() 126 restriction.support = new c_StrategySupportProfile(deref(self.support)) 127 return restriction 128 129 def undominated(self, strict=False, external=False): 130 cdef StrategicRestriction restriction 131 restriction = StrategicRestriction() 132 restriction.support = new c_StrategySupportProfile(self.support.Undominated(strict, external)) 133 new_profile = StrategySupportProfile(restriction.strategies, self.game) 134 return new_profile 135 136 def union(self, StrategySupportProfile other): 137 return StrategySupportProfile(self.unique(list(self) + list(other)), self.game) 138 139 def unique(self, lst): 140 uniq = [] 141 [uniq.append(i) for i in lst if not uniq.count(i)] 142 return uniq 143 144 property game: 145 def __get__(self): 146 cdef Game g 147 g = Game() 148 g.game = self.support.GetGame() 149 return g 150 151cdef class RestrictionOutcomes(Collection): 152 "Represents a collection of outcomes in a restriction." 153 cdef StrategicRestriction restriction 154 155 def __init__(self, StrategicRestriction restriction not None): 156 self.restriction = restriction 157 def __len__(self): return (<Game>self.restriction.unrestrict()).game.deref().NumOutcomes() 158 def __getitem__(self, outc): 159 if not isinstance(outc, int): return Collection.__getitem__(self, outc) 160 cdef Outcome c 161 c = Outcome() 162 c.outcome = (<Game>self.restriction.unrestrict()).game.deref().GetOutcome(outc+1) 163 c.restriction = self.restriction 164 return c 165 166 def add(self, label=""): 167 raise UndefinedOperationError("Changing objects in a restriction is not supported") 168 169cdef class RestrictionStrategies(Collection): 170 "Represents a collection of strategies in a restriction." 171 cdef StrategicRestriction restriction 172 173 def __init__(self, StrategicRestriction restriction not None): 174 self.restriction = restriction 175 def __len__(self): return self.restriction.support.MixedProfileLength() 176 def __getitem__(self, strat): 177 if not isinstance(strat, int): 178 return Collection.__getitem__(self, strat) 179 cdef Array[int] num_strategies 180 cdef Strategy s 181 num_strategies = self.restriction.support.NumStrategies() 182 for i in range(1,num_strategies.Length()+1): 183 if strat - num_strategies.getitem(i) < 0: 184 s = Strategy() 185 s.strategy = self.restriction.support.GetStrategy(i, strat+1) 186 s.restriction = self.restriction 187 return s 188 strat = strat - num_strategies.getitem(i) 189 raise IndexError("Index out of range") 190 191cdef class StrategicRestriction(BaseGame): 192 """ 193 A StrategicRestriction is a read-only view on a game, defined by a 194 subset of the strategies on the original game. 195 """ 196 cdef c_StrategySupportProfile *support 197 198 def __init__(self): 199 self.support = (<c_StrategySupportProfile *>0) 200 def __dealloc__(self): 201 if self.support != (<c_StrategySupportProfile *>0): 202 del self.support 203 def __repr__(self): 204 return self.write() 205 206 def __richcmp__(StrategicRestriction self, other, whichop): 207 if isinstance(other, StrategicRestriction): 208 if whichop == 2: 209 return deref(self.support) == deref((<StrategicRestriction>other).support) 210 elif whichop == 3: 211 return deref(self.support) != deref((<StrategicRestriction>other).support) 212 else: 213 raise NotImplementedError 214 else: 215 if whichop == 2: 216 return False 217 elif whichop == 3: 218 return True 219 else: 220 raise NotImplementedError 221 222 def __hash__(self): 223 return long(<long>&self.support) 224 225 property title: 226 def __get__(self): 227 return "Restriction from Game '%s'" % self.unrestrict().title 228 229 property players: 230 def __get__(self): 231 cdef Players p 232 p = Players() 233 p.game = (<Game>self.unrestrict()).game 234 p.restriction = self 235 return p 236 237 property strategies: 238 def __get__(self): 239 cdef RestrictionStrategies s 240 s = RestrictionStrategies(self) 241 return s 242 243 property outcomes: 244 def __get__(self): 245 cdef RestrictionOutcomes o 246 o = RestrictionOutcomes(self) 247 return o 248 249 property is_tree: 250 def __get__(self): 251 # Any strategic restriction is automatically not a tree 252 # representation, even if the parent game does have one. 253 return False 254 255 property is_const_sum: 256 def __get__(self): 257 return self.unrestrict().is_const_sum 258 259 property is_perfect_recall: 260 def __get__(self): 261 return self.unrestrict().is_perfect_recall 262 263 property min_payoff: 264 def __get__(self): 265 return self.unrestrict().min_payoff 266 267 property max_payoff: 268 def __get__(self): 269 return self.unrestrict().max_payoff 270 271 def write(self, format='native'): 272 if format != 'native' and format != 'nfg': 273 raise NotImplementedError 274 else: 275 return WriteGame(deref(self.support)).c_str() 276 277 def undominated(self, strict=False): 278 cdef StrategicRestriction new_restriction 279 new_restriction = StrategicRestriction() 280 new_restriction.support = new c_StrategySupportProfile(self.support.Undominated(strict, False)) 281 return new_restriction 282 283 def num_strategies_player(self, pl): 284 return self.support.NumStrategiesPlayer(pl+1) 285 286 def support_profile(self): 287 return StrategySupportProfile(list(self.strategies), self.unrestrict()) 288 289 def unrestrict(self): 290 cdef Game g 291 g = Game() 292 g.game = self.support.GetGame() 293 return g 294 295 ### 296 # Methods below here have been borrowed from the basic Game 297 # implementation, and may not be fully correct in handling 298 # all cases 299 ### 300 301 def _get_contingency(self, *args): 302 cdef c_PureStrategyProfile *psp 303 cdef Outcome outcome 304 psp = new c_PureStrategyProfile(deref(self.support).GetGame().deref().NewPureStrategyProfile()) 305 306 307 for (pl, st) in enumerate(args): 308 psp.deref().SetStrategy(deref(self.support).GetStrategy(pl+1, st+1)) 309 310 outcome = Outcome() 311 outcome.outcome = psp.deref().GetOutcome() 312 del psp 313 return outcome 314 315 # As of Cython 0.11.2, cython does not support the * notation for the argument 316 # to __getitem__, which is required for multidimensional slicing to work. 317 # We work around this by providing a shim. 318 def __getitem__(self, i): 319 try: 320 if len(i) != len(self.players): 321 raise KeyError, "Number of strategies is not equal to the number of players" 322 except TypeError: 323 raise TypeError, "contingency must be a tuple-like object" 324 cont = [ 0 ] * len(self.players) 325 for (pl, st) in enumerate(i): 326 if isinstance(st, int): 327 if st < 0 or st >= len(self.players[pl].strategies): 328 raise IndexError, "Provided strategy index %d out of range for player %d" % (st, pl) 329 cont[pl] = st 330 elif isinstance(st, str): 331 try: 332 cont[pl] = [ s.label for s in self.players[pl].strategies ].index(st) 333 except ValueError: 334 raise IndexError, "Provided strategy label '%s' not defined" % st 335 elif isinstance(st, Strategy): 336 try: 337 cont[pl] = list(self.players[pl].strategies).index(st) 338 except ValueError: 339 raise IndexError, "Provided strategy '%s' not available to player" % st 340 else: 341 raise TypeError("Must use a tuple of ints, strategy labels, or strategies") 342 return self._get_contingency(*tuple(cont)) 343 344 def mixed_strategy_profile(self, rational=False): 345 cdef MixedStrategyProfileDouble mspd 346 cdef MixedStrategyProfileRational mspr 347 cdef c_Rational dummy_rat 348 if not rational: 349 mspd = MixedStrategyProfileDouble() 350 mspd.profile = new c_MixedStrategyProfileDouble(deref(self.support).NewMixedStrategyProfileDouble()) 351 return mspd 352 else: 353 mspr = MixedStrategyProfileRational() 354 mspr.profile = new c_MixedStrategyProfileRational(deref(self.support).NewMixedStrategyProfileRational()) 355 return mspr 356