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