-
Notifications
You must be signed in to change notification settings - Fork 1
/
README
234 lines (211 loc) · 9.6 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
Help on module mathgame:
NAME
mathgame - A Python combinatorial game class.
DESCRIPTION
Learn about Combinatorial Game Theory:
http://www.ics.uci.edu/~eppstein/cgt/
http://en.wikipedia.org/wiki/Combinatorial_game_theory
Combinatorial games can behave like numbers, but their iterative
nature makes them extremely difficult to compute.
One could also construct a subclass defining the surreal numbers
using the ordering methods (<=) in order to perform a member check.
The hope is that this can be used as a superclass to make programs
such as a nimber calculator, etc. and could even be used to make
on-the-fly calculations of a game in play.
For the time being, I can only represent games with a finite birthday.
I don't like that, but what with the reality constraints, it would be
pretty difficult to hold infinitely large numbers in a computer's memory.
Due to the intensively iterative nature of combinitorial games, it is
necessary to keep track of how your games are defined, lest you wind up
with enormous but simple games. It seems like five sums-of-sums
either breaks python or gets incalculably large. This is either due to my poor
coding or just the reality of how complicated games can get. I recommend the
simp() method to simplify number, as it produces an alike game.
This is my way of learning some Python and OOP in general,
please forgive/fix any inefficiencies. Please send comments/criticism to
prairie.squidman@gmail.com or improve the code at its home on GitHub:
https://github.com/revslaughter/pyGCT
TODO:
-make a function to determine the best move for each player.
-elimiate the limitation on num()
-optimize the up function so that we can have better than 3up
-error check the initial values so that if you enter in a number or
a heap[0-9] or a col n* position that the class understands and reacts
so that you don't have to input @^*&($ functions every time you make
a new game.
-see if there's a way to make addition or multiplication, uh, work good.
CLASSES
builtins.object
game
class game(builtins.object)
| Usage: g = game("name", left position, right position)
|
| Sans arguments, initializes to the 0 = {|} game, add other positions using
| the Lput or Rput methods.
|
| Options or positions of a game are themselves games.
|
| Methods defined here:
|
| Lput(self, value)
| Lput and Rput methods simply append using the List method
| to the appropriate list.
|
| Rput(self, value)
| Lput and Rput methods simply append using the List method
| to the appropriate list.
|
| __add__(self, other)
| Natural '+' operator overloading for adding ease-of-use.
| Rule is G + H = {[G.L + H, G + H.L] | [G.R + H, G + H.R]}
| When we reach g + empty, do nothing.
| WARNING: Iterations of addition deeper than 4 are very system-taxing.
|
| __eq__(self, other)
| The Equivalence Relation. In CGT that means 'alike'.
| x == y iff x <= y and y <= x. This will help to 'simplify' games
| as games' respective option sets need not be equal for two
| games to be alike. ex: 0 == {|} == {-1|1} == {-3, -2 | 4} == {*|*}
| In this sense, we are not defining strict equality
| here, only 'alikeness' in order to easily form equivalence classes.
| One could use List object methods to check true ==.
|
| __ge__(self, other)
| Greater than or equal to is the opposite of less than or equal to.
| Hooray for code reuse!
|
| __gt__(self, other)
| Strictly greater than
|
| __init__(self, nom='0', leftinit=None, rightinit=None)
| It is ideal to name your game cleverly so that you don't get lost.
|
| Initializes to the 0 = {|} game, optional arguments allow you to
| define the position of your game.
|
| __le__(self, other)
| The Less Than or Equal to Relation.
| All comparisons between games are based upon the <= relation.
| Rule: For x = { x.L | x.R } and
| y = { y.L | y.R }, x <= y if and only if:
| There is no g in x.L such that y <= g, and
| there is no h in y.R such that h <= x.
|
| __lt__(self, other)
| Strictly less than. (Not unalike or great than or equal to)
|
| __mul__(self, other)
| Multiplying games is extremely complicated by hand.
|
| The rule is
| X * Y = {((X.L * Y) + (X * Y.L) - (X.L * Y.L)),
| ((X.R * Y) + (X * Y.R) - (X.R * Y.R))
| |
| ((X.L * Y) + (X * Y.R) - (X.L * Y.R)),
| ((X * Y.L) + (X.R * Y) - (X.R * Y.L))}
|
| Division is a nightmare - anything that isn't a dyadic/binary rational
| is an infinite limit, and recall that this game class cannot hope to
| output games born on day omega as their lists have an infinite number
| of members. Not too worried about it - mul isn't well-defined for
| games, just numbers.
|
| __ne__(self, other)
| Implements 'Not Alike'
|
| __repr__(self)
| Shows the game in {L|R} format, according to the option's names
| If you name your games smartly, you should be able to tell what's
| inside them. Otherwise, this method may get pretty confusing.
|
| __sub__(self, other)
| Subtraction is easy when we have additive inverses!
|
| fuzzy(self, other)
| Fuzzy relation. This is a relation that games have that
| numbers don't. Games that are fuzzy to 0 are 0's 'opposite', as the
| first player has a winning strategy. Nimbers of the form n* = {n|n},
| n being any (surreal) number, n* || ('fuzzy to') n. It may be shown
| that any game that is either greater than, less than, or fuzzy to 0.
| We use this property to more easily define the fuzzy method.
|
| To check if a || b, use a.fuzzy(b)
|
| isnumber(self)
| This method checks to see if the given game is a surreal number.
|
| Example: * = {0|0}. *.isnumber() == False
| 1 = {0|}. 1.isnumber == True
|
| neg(self)
| Returns a game negative to the input. 0 is its own negative.
| The rule is for G = {L|R}, -G = {-R|-L}
|
| put(self, a=None, b=None)
| Puts the first argument in the left, the second argument in the right.
|
| simp(self)
| Simplifies a game to an alike game with fewer options, useful when
| repeatedly adding or multiplying games. Rule is that any number
| g = {a, b, ... | d, ...} is equivalent to {a | d} if a is the
| greatest option in the left side and d is the least option in the
| right side.
|
| winner(self)
| Determines who has the advantage to a particular game. Useful if you
| have an interesting game constructed and can't tell by looking.
|
| This is sort of the point of the whole thing. Should probably just
| return numbers or some other signal beside strings: 0,1,2,3
|
| That way people can actually use them in their programs and stuff.
|
| The question of who has the winning strategy all depends on how the
| game relates to zero.
|
| ----------------------------------------------------------------------
| Data descriptors defined here:
|
| __dict__
| dictionary for instance variables (if defined)
|
| __weakref__
| list of weak references to the object (if defined)
|
| ----------------------------------------------------------------------
| Data and other attributes defined here:
|
| __hash__ = None
FUNCTIONS
col(n)
Makes a col position n* = {n|n} from number n.
nim(n)
Makes a nim-heap of blocks n. n needs to be an integer.
num(n)
Makes a surreal integer n.
Can't make numbers larger than +994, -993 due to maximum recursion depth
(default 1000).
See Guido's post at:
http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html
For values between the above, this function is nice and fast. (as opposed
to before!!)
TODO: Make this based on iteration rather than recursion. How?
up(n)
Makes up and up-games. For instance, up(0) is 0,
up(1) is up, up(2) is double-up, etc.
Algorithm is super super clunky. Python quits on up(4).
Addition is waaay better than multiplication though
as addition has only 4 self-calls while multiplication has 12 along with 6
addition calls, each of which having 4 self-calls. Awesome.
What's cool about up is that it's a surreal number that has no analog
in the real numbers -- up is the proverbial 'smallest number' that is
'right next to' zero! Its equivalent is 1/infinity.
windecode(num)
Just a function wrapper for a dictionary to return strings
that interpret the value of game.winner()
DATA
negone = {|0}
one = {0|}
star = {0|0}
up1 = {0|1}
zero = {|}