HOG2
TopSpin.h
Go to the documentation of this file.
1 /*
2  * TopSpin.h
3  * hog2
4  *
5  * Created by Nathan Sturtevant on 9/4/14.
6  * Copyright 2014 Nathan Sturtevant, University of Denver. All rights reserved.
7  *
8  */
9 
10 #ifndef TopSpin_H
11 #define TopSpin_H
12 
13 #include <stdint.h>
14 #include <iostream>
15 #include "SearchEnvironment.h"
16 #include "PermutationPuzzleEnvironment.h"
17 #include "UnitSimulation.h"
18 #include "GraphEnvironment.h"
19 #include "Graph.h"
20 #include <sstream>
21 #include <unordered_map>
22 
23 template <int N>
24 class TopSpinState {
25 public:
26  TopSpinState()
27  {
28 // puzzle.resize(N);
29  for (unsigned int x = 0; x < N; x++)
30  puzzle[x] = x;
31  }
32  void Reset()
33  {
34  for (unsigned int x = 0; x < N; x++)
35  puzzle[x] = x;
36  }
37  size_t size() const { return N; }
38  void FinishUnranking()
39  { }
40 // std::vector<int> puzzle;
41  int puzzle[N];
42 };
43 
47 typedef int TopSpinAction;
48 
49 template <int N>
50 static std::ostream& operator <<(std::ostream & out, const TopSpinState<N> &loc)
51 {
52  for (unsigned int x = 0; x < N; x++)
53  out << loc.puzzle[x] << " ";
54  return out;
55 }
56 
57 template <int N>
58 static bool operator==(const TopSpinState<N> &l1, const TopSpinState<N> &l2)
59 {
60 // if (l1.puzzle.size() != l2.puzzle.size())
61 // return false;
62  for (unsigned int x = 0; x < N; x++)
63  {
64  if (l1.puzzle[(x)%N] != l2.puzzle[(x)%N])
65  return false;
66  }
67  return true;
68 }
69 
70 template <int N>
71 static bool operator!=(const TopSpinState<N> &l1, const TopSpinState<N> &l2)
72 {
73  return !(l1 == l2);
74 }
75 
76 template <int N, int k>
77 class TopSpin : public PermutationPuzzle::PermutationPuzzleEnvironment<TopSpinState<N>, TopSpinAction> {
78 public:
79  TopSpin();
80  ~TopSpin();
81  void SetWeighted(bool w) { weighted = w; }
82  bool GetWeighted() { return weighted; }
83  void SetPruneSuccessors(bool val)
84  { if (val) ComputeMovePruning(); pruneSuccessors = val; history.resize(0); }
85  void GetSuccessors(const TopSpinState<N> &stateID, std::vector<TopSpinState<N>> &neighbors) const;
86  void GetActions(const TopSpinState<N> &stateID, std::vector<TopSpinAction> &actions) const;
87  void ApplyAction(TopSpinState<N> &s, TopSpinAction a) const;
88  void UndoAction(TopSpinState<N> &s, TopSpinAction a) const;
89  bool InvertAction(TopSpinAction &a) const;
90  static unsigned GetParity(TopSpinState<N> &state);
91  void SetPattern(const std::vector<int> &pattern);
92  double AdditiveGCost(const TopSpinState<N> &s, const TopSpinAction &d);
93 
94  OccupancyInterface<TopSpinState<N>, TopSpinAction> *GetOccupancyInfo() { return 0; }
95  double HCost(const TopSpinState<N> &state1, const TopSpinState<N> &state2) const;
96 
97  double GCost(const TopSpinState<N> &state1, const TopSpinState<N> &state2) const;
98  double GCost(const TopSpinState<N> &, const TopSpinAction &) const;
99  bool GoalTest(const TopSpinState<N> &state, const TopSpinState<N> &goal) const;
100  bool GoalTest(const TopSpinState<N> &s) const;
101  void GetGoals(std::vector<TopSpinState<N>> &goals)
102  {
103  goals.clear();
104  TopSpinState<N> s;
105  for (int x = 0; x < N; x++)
106  {
107  for (int y = 0; y < N; y++)
108  s.puzzle[y] = (y+x)%N;
109  goals.push_back(s);
110  }
111  }
112 
113  //void LoadPDB(char *fname, const std::vector<int> &tiles, bool additive);
114 
115  uint64_t GetActionHash(TopSpinAction act) const;
116  void OpenGLDraw() const;
117  void OpenGLDraw(const TopSpinState<N> &s) const;
118  void OpenGLDraw(const TopSpinState<N> &l1, const TopSpinState<N> &l2, float v) const;
119  void OpenGLDraw(const TopSpinState<N> &, const TopSpinAction &) const { /* currently not drawing moves */ }
120  void StoreGoal(TopSpinState<N> &); // stores the locations for the given goal state
121 
123  TopSpinState<N> Get_Goal(){
124  return goal;
125  }
126 
127  virtual const std::string GetName();
128 
129  void ClearGoal() { } // clears the current stored information of the goal
130 
131  bool IsGoalStored() const {return true;} // returns if a goal is stored or not
132 
133  bool State_Check(const TopSpinState<N> &to_check) { return true; }
134 
135  void PrintHStats()
136  {
137  printf("-\t");
138  for (int x = 0; x < hDist.size(); x++)
139  printf("%d\t", x);
140  printf("\n");
141  for (int y = 0; y <= 12; y++)
142  {
143  printf("%d\t", y);
144  for (int x = 0; x < hDist.size(); x++)
145  {
146  if (y >= hDist[x].size())
147  printf("0\t");
148  else
149  printf("%d\t", hDist[x][y]);
150  }
151  printf("\n");
152  }
153  }
154 private:
155  void ComputeMovePruning();
156  void RecursiveMovePruning(int depth, TopSpinState<N> &state);
157 
158  std::unordered_map<uint64_t,bool> pruningMap;
159  std::unordered_map<uint64_t,int> pruningCostMap;
160 
161  //unsigned int numTiles, swapDiameter;
162  std::vector<TopSpinAction> operators;
163  std::vector<bool> movePrune;
164 
165  // stores the heuristic value of each tile-position pair indexed by the tile value (0th index is empty)
166  unsigned **h_increment;
167  TopSpinState<N> goal;
168  std::vector<std::vector<int> > hDist;
169  bool pattern[N];
170 
171  mutable std::vector<TopSpinAction> history;
172  bool pruneSuccessors;
173  bool weighted;
174  bool additive;
175 };
176 
177 //typedef UnitSimulation<TopSpinState<N>, TopSpinAction, TopSpin> TopSpinSimulation;
178 
179 
180 
181 template <int N, int k>
182 TopSpin<N, k>::TopSpin()
183 :PermutationPuzzle::PermutationPuzzleEnvironment<TopSpinState<N>, TopSpinAction>()
184 {
185  weighted = false;
186  additive = false;
187  pruneSuccessors = false;
188  for (int x = 0; x < N; x++)
189  operators.push_back(x);
190 }
191 
192 template <int N, int k>
193 TopSpin<N, k>::~TopSpin()
194 {
195  ClearGoal();
196 }
197 
198 template <int N, int k>
199 const std::string TopSpin<N, k>::GetName(){
200  std::stringstream name;
201  name << "TopSpin(" << N << ", " << k << ")";
202 
203  return name.str();
204 }
205 
206 template <int N, int k>
207 void TopSpin<N, k>::SetPattern(const std::vector<int> &pattern)
208 {
209  if (pattern.size() == 0)
210  additive = false;
211  else
212  additive = true;
213  for (int x = 0; x < N; x++)
214  this->pattern[x] = false;
215  for (int i : pattern)
216  this->pattern[i] = true;
217 }
218 
219 template <int N, int k>
220 double TopSpin<N, k>::AdditiveGCost(const TopSpinState<N> &s, const TopSpinAction &a)
221 {
222  double cnt = 0;
223  for (int x = 0; x < k; x++)
224  {
225  if (pattern[s.puzzle[(a+x)%N]])
226  cnt++;
227  }
228  return cnt;
229 }
230 
231 
232 template <int N, int k>
233 void TopSpin<N, k>::ComputeMovePruning()
234 {
235  TopSpinState<N> start;
236  movePrune.resize(N*N*N);
237  //movePrune.resize(N*N);
238  history.resize(0);
239  RecursiveMovePruning(3, start);
240  //RecursiveMovePruning(2, start);
241  pruningMap.clear();
242  pruningCostMap.clear();
243 }
244 
245 template <int N, int k>
246 void TopSpin<N, k>::RecursiveMovePruning(int depth, TopSpinState<N> &state)
247 {
248  if (depth == 0)
249  {
250  if (pruningMap.find(this->GetStateHash(state)) != pruningMap.end())
251  {
252  int last = history.size()-1;
253  //assert(last >= 1);
254  assert(last >= 2);
255  //movePrune[history[last]*N+history[last-1]] = true; // prune this
256  movePrune[history[last]*N*N+history[last-1]*N+history[last-2]] = true; // prune this
257 // printf("Pruning the sequence %d %d %d\n", history[last-2], history[last-1], history[last]);
258  }
259  pruningMap[this->GetStateHash(state)] = true;
260  return;
261  }
262 
263  for (int x = 0; x < N; x++)
264  {
265  ApplyAction(state, x);
266  history.push_back(x);
267  RecursiveMovePruning(depth-1, state);
268  history.pop_back();
269  UndoAction(state, x);
270  }
271 }
272 
273 template <int N, int k>
274 void TopSpin<N, k>::StoreGoal(TopSpinState<N> &s)
275 {
276 }
277 
278 template <int N, int k>
279 bool TopSpin<N, k>::GoalTest(const TopSpinState<N> &s) const
280 {
281  for (int x = 0; x < N; x++)
282  if ((s.puzzle[x]+1)%N != s.puzzle[(x+1)%N])
283  return false;
284  return true;
285 }
286 
287 template <int N, int k>
288 void TopSpin<N, k>::GetSuccessors(const TopSpinState<N> &stateID,
289  std::vector<TopSpinState<N>> &neighbors) const
290 {
291  neighbors.resize(0);
292  for (unsigned int i = 0; i < N; i++)
293  {
294  TopSpinState<N> s(stateID);
295  ApplyAction(s, i);
296  neighbors.push_back(s);
297  }
298 }
299 
300 template <int N, int k>
301 void TopSpin<N, k>::GetActions(const TopSpinState<N> &stateID, std::vector<TopSpinAction> &actions) const
302 {
303  if (!pruneSuccessors || history.size() < 3)
304  //if (!pruneSuccessors || history.size() < 2)
305  {
306  actions = operators;
307  }
308  else {
309  actions.resize(0);
310 
311  for (int x = 0; x < N; x++)
312  {
313 // if (!movePrune[x*N+history.back()])
314  if (!movePrune[x*N*N+history.back()*N+history[history.size()-2]])
315  actions.push_back(x);
316  }
317  }
318 }
319 
320 template <int N, int k>
321 void TopSpin<N, k>::ApplyAction(TopSpinState<N> &s, TopSpinAction a) const
322 {
323  for (int x = 0; x < k/2; x++)
324  {
325  std::swap(s.puzzle[(a+x)%N], s.puzzle[(a+x+k-1-2*x)%N]);
326  }
327  if (pruneSuccessors)
328  history.push_back(a);
329 }
330 
331 template <int N, int k>
332 void TopSpin<N, k>::UndoAction(TopSpinState<N> &s, TopSpinAction a) const
333 {
334  if (pruneSuccessors && history.size() > 0)
335  {
336  assert(history.back() == a);
337  history.pop_back();
338  }
339  for (int x = 0; x < k/2; x++)
340  {
341  std::swap(s.puzzle[(a+x)%N], s.puzzle[(a+x+k-1-2*x)%N]);
342  }
343 }
344 
345 template <int N, int k>
346 bool TopSpin<N, k>::InvertAction(TopSpinAction &a) const
347 {
348  return true;
349 }
350 
351 // TODO Remove PDB heuristic from this heuristic evaluator.
352 template <int N, int k>
353 double TopSpin<N, k>::HCost(const TopSpinState<N> &state1, const TopSpinState<N> &state2) const
354 {
355 // return PermutationPuzzleEnvironment<TopSpinState<N>, TopSpinAction>::HCost(state1);
356  return 0;
357 }
358 
359 //static const int tsCostCount = 16;
360 //static int tscosts[tsCostCount] = {5,4,3,3,10,2,6,8,4,8,6,2,10,6,5,1}; // 1...10
361 //static const int tsCostCount = 16;
362 //static int tscosts[tsCostCount] = {16,1,8,15,22,29,17,14,9,20,26,28,3,16,12,18}; // 1...29
363 static const int tsCostCount = 21;
364 static int tscosts[tsCostCount] = {47,45,52,41,56,43,50,46,49,51,48,53,59,58,55,40,57,60,44,42,54}; // [40...60]
365 //static const int tsCostCount = 12;
366 //static const int tscosts[tsCostCount] = {191,467,63,266,691,697,916,534,486,619,581,766}; // duplicating results run in PSVN
367 template <int N, int k>
368 double TopSpin<N, k>::GCost(const TopSpinState<N> &node, const TopSpinAction &act) const
369 {
370  if (additive)
371  {
372  return k;
373  }
374  else if (!weighted)
375  {
376  return 1;
377  }
378  else {
379  assert(N <= tsCostCount);
380  return tscosts[act];
381  }
382 }
383 
384 template <int N, int k>
385 double TopSpin<N, k>::GCost(const TopSpinState<N> &s1, const TopSpinState<N> &s2) const
386 {
387 // return 1;
388  TopSpinAction a = this->GetAction(s1, s2);
389  return GCost(s1, a);
390 }
391 
392 template <int N, int k>
393 bool TopSpin<N, k>::GoalTest(const TopSpinState<N> &state, const TopSpinState<N> &theGoal) const
394 {
395  return GoalTest(state);
396 // return (state == theGoal);
397 }
398 
399 template <int N, int k>
400 uint64_t TopSpin<N, k>::GetActionHash(TopSpinAction act) const
401 {
402  return act;
403 }
404 
405 template <int N, int k>
406 void TopSpin<N, k>::OpenGLDraw() const
407 {
408 }
409 
410 static void LocalDrawCircle(float x, float y, float r1, float r2, int segments)
411 {
412  float angleStep = TWOPI/segments;
413  // glBegin(GL_LINE_LOOP);
414  glBegin(GL_QUAD_STRIP);
415  for (float angle = 0; angle < TWOPI; angle += angleStep)
416  {
417  glVertex3f(x+cos(angle)*r1, y+sin(angle)*r1, 0);
418  glVertex3f(x+cos(angle)*r2, y+sin(angle)*r2, 0);
419  }
420  glVertex3f(x+r1, y, 0);
421  glVertex3f(x+r2, y, 0);
422  glEnd();
423 }
424 
425 static void DrawTSTile(float x, float y, char c1, char c2, int w, int h)
426 {
427  glLineWidth(1.0);
428  int textWidth = 0;
429  //int textHeight = 0;
430  // if (c1 != 0)
431  // textWidth += glutStrokeWidth(GLUT_STROKE_ROMAN, c1);
432  //if (c2 != 0)
433  //textWidth += glutStrokeWidth(GLUT_STROKE_ROMAN, c2);
434  //printf("%d\n", textWidth);
435  glPushMatrix();
436  glTranslatef(x, y, -0.001);
437  glScalef(1.0/(w*120.0), 1.0/(h*120.0), 1);
438  glRotatef(180, 0.0, 0.0, 1.0);
439  glRotatef(180, 0.0, 1.0, 0.0);
440  glTranslatef(-textWidth/2, -60, 0);
441  //if (c1 != 0)
442  // glutStrokeCharacter(GLUT_STROKE_ROMAN, c1);
443  //if (c2 != 0)
444  // glutStrokeCharacter(GLUT_STROKE_ROMAN, c2);
445  glPopMatrix();
446 
447 }
448 
449 template <int N, int k>
450 static void DrawFrame(int w, int h)
451 {
452 }
453 
454 template <int N, int k>
455 void TopSpin<N, k>::OpenGLDraw(const TopSpinState<N> &s) const
456 {
457  glEnable(GL_LINE_SMOOTH);
458  char c1=0, c2=0;
459  double diam = 2.0;
460  diam /= N;
461  for (int x = 0; x < N; x++)
462  {
463  if (s.puzzle[x] > 9)
464  c1 = '0'+(((s.puzzle[x])/10)%10);
465  if (s.puzzle[x] >= 0)
466  c2 = '0'+((s.puzzle[x])%10);
467 
468  glColor3f(1.0, 1.0, 1.0);
469  DrawTSTile(-1+x*diam + diam/2, 0.0f, c1, c2, N, N);
470  glLineWidth(2.0);
471  glColor3f(0.0, 0.3, 0.8);
472  LocalDrawCircle(-1+x*diam + diam/2, 0, diam/2-diam/20, diam/2+diam/20, 50);
473  }
474 }
475 
476 template <int N, int k>
477 void TopSpin<N, k>::OpenGLDraw(const TopSpinState<N> &s1, const TopSpinState<N> &s2, float v) const
478 {
479 }
480 
481 
482 #endif
TopSpin::pruningCostMap
std::unordered_map< uint64_t, int > pruningCostMap
Definition: TopSpin.h:159
operator==
static bool operator==(const TopSpinState< N > &l1, const TopSpinState< N > &l2)
Definition: TopSpin.h:58
TopSpin::TopSpin
TopSpin()
Definition: TopSpin.h:182
UnitSimulation.h
TopSpin::GetOccupancyInfo
OccupancyInterface< TopSpinState< N >, TopSpinAction > * GetOccupancyInfo()
Definition: TopSpin.h:94
Graph.h
TopSpin::GetParity
static unsigned GetParity(TopSpinState< N > &state)
TopSpin::UndoAction
void UndoAction(TopSpinState< N > &s, TopSpinAction a) const
Definition: TopSpin.h:332
TopSpinState
Definition: TopSpin.h:24
TopSpin::HCost
double HCost(const TopSpinState< N > &state1, const TopSpinState< N > &state2) const
Definition: TopSpin.h:353
DrawTSTile
static void DrawTSTile(float x, float y, char c1, char c2, int w, int h)
Definition: TopSpin.h:425
TopSpin::weighted
bool weighted
Definition: TopSpin.h:173
TopSpinState::Reset
void Reset()
Definition: TopSpin.h:32
d
mcData d[]
Definition: MotionCaptureMovement.cpp:21
TopSpin
Definition: TopSpin.h:77
TopSpin::OpenGLDraw
void OpenGLDraw() const
Definition: TopSpin.h:406
TopSpin::GetActionHash
uint64_t GetActionHash(TopSpinAction act) const
Definition: TopSpin.h:400
TopSpin::RecursiveMovePruning
void RecursiveMovePruning(int depth, TopSpinState< N > &state)
Definition: TopSpin.h:246
TopSpin::ApplyAction
void ApplyAction(TopSpinState< N > &s, TopSpinAction a) const
Definition: TopSpin.h:321
TopSpin::pattern
bool pattern[N]
Definition: TopSpin.h:169
TopSpin::history
std::vector< TopSpinAction > history
Definition: TopSpin.h:171
operator!=
static bool operator!=(const TopSpinState< N > &l1, const TopSpinState< N > &l2)
Definition: TopSpin.h:71
TopSpin::pruningMap
std::unordered_map< uint64_t, bool > pruningMap
Definition: TopSpin.h:158
tsCostCount
static const int tsCostCount
Definition: TopSpin.h:363
TopSpin::pruneSuccessors
bool pruneSuccessors
Definition: TopSpin.h:172
TopSpinState::size
size_t size() const
Definition: TopSpin.h:37
TopSpin::StoreGoal
void StoreGoal(TopSpinState< N > &)
Definition: TopSpin.h:274
TopSpin::movePrune
std::vector< bool > movePrune
Definition: TopSpin.h:163
TopSpinState::TopSpinState
TopSpinState()
Definition: TopSpin.h:26
loc
Definition: MapGenerators.cpp:296
PermutationPuzzleEnvironment.h
TopSpinState::puzzle
int puzzle[N]
Definition: TopSpin.h:41
TopSpin::SetWeighted
void SetWeighted(bool w)
Definition: TopSpin.h:81
TopSpin::IsGoalStored
bool IsGoalStored() const
Definition: TopSpin.h:131
operator<<
static std::ostream & operator<<(std::ostream &out, const TopSpinState< N > &loc)
Definition: TopSpin.h:50
TopSpin::GoalTest
bool GoalTest(const TopSpinState< N > &state, const TopSpinState< N > &goal) const
Definition: TopSpin.h:393
TopSpin::GetName
virtual const std::string GetName()
Definition: TopSpin.h:199
TopSpin::SetPattern
void SetPattern(const std::vector< int > &pattern)
Definition: TopSpin.h:207
TopSpin::GCost
double GCost(const TopSpinState< N > &state1, const TopSpinState< N > &state2) const
Definition: TopSpin.h:385
TopSpin::h_increment
unsigned ** h_increment
Definition: TopSpin.h:166
TopSpinAction
int TopSpinAction
Actions are the first tile that gets swapped.
Definition: TopSpin.h:47
TopSpin::additive
bool additive
Definition: TopSpin.h:174
PermutationPuzzle::PermutationPuzzleEnvironment
Note, assumes that state has a public vector<int> called puzzle in which the permutation is held.
Definition: PermutationPuzzleEnvironment.h:26
LocalDrawCircle
static void LocalDrawCircle(float x, float y, float r1, float r2, int segments)
Definition: TopSpin.h:410
tscosts
static int tscosts[tsCostCount]
Definition: TopSpin.h:364
TopSpin::operators
std::vector< TopSpinAction > operators
Definition: TopSpin.h:162
TopSpin::ClearGoal
void ClearGoal()
Definition: TopSpin.h:129
TopSpin::OpenGLDraw
void OpenGLDraw(const TopSpinState< N > &, const TopSpinAction &) const
Definition: TopSpin.h:119
TopSpin::GetActions
void GetActions(const TopSpinState< N > &stateID, std::vector< TopSpinAction > &actions) const
Definition: TopSpin.h:301
TopSpin::PrintHStats
void PrintHStats()
Definition: TopSpin.h:135
TopSpin::Get_Goal
TopSpinState< N > Get_Goal()
Returns stored goal state if it is stored.
Definition: TopSpin.h:123
TopSpin::GetWeighted
bool GetWeighted()
Definition: TopSpin.h:82
TopSpin::AdditiveGCost
double AdditiveGCost(const TopSpinState< N > &s, const TopSpinAction &d)
Definition: TopSpin.h:220
TopSpin::goal
TopSpinState< N > goal
Definition: TopSpin.h:167
TWOPI
static const double TWOPI
Definition: GLUtil.h:65
TopSpin::ComputeMovePruning
void ComputeMovePruning()
Definition: TopSpin.h:233
PermutationPuzzle
Definition: PermutationPuzzleEnvironment.h:23
TopSpin::GetSuccessors
void GetSuccessors(const TopSpinState< N > &stateID, std::vector< TopSpinState< N >> &neighbors) const
Definition: TopSpin.h:288
TopSpin::hDist
std::vector< std::vector< int > > hDist
Definition: TopSpin.h:168
TopSpin::~TopSpin
~TopSpin()
Definition: TopSpin.h:193
swap
void swap(uint64_t &state, int loc1, int loc2)
Definition: RubiksCube7Edges.cpp:359
TopSpin::GetGoals
void GetGoals(std::vector< TopSpinState< N >> &goals)
Definition: TopSpin.h:101
TopSpin::SetPruneSuccessors
void SetPruneSuccessors(bool val)
Definition: TopSpin.h:83
DrawFrame
static void DrawFrame(int w, int h)
Definition: TopSpin.h:450
TopSpin::State_Check
bool State_Check(const TopSpinState< N > &to_check)
Checks that the given state is a valid state for this domain.
Definition: TopSpin.h:133
TopSpinState::FinishUnranking
void FinishUnranking()
Definition: TopSpin.h:38
TopSpin::InvertAction
bool InvertAction(TopSpinAction &a) const
Definition: TopSpin.h:346
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
SearchEnvironment.h
GraphEnvironment.h
OccupancyInterface
Definition: OccupancyInterface.h:36
Generated by   doxygen 1.8.17