Sign in to follow this  
rachil0

Good heuristic for "Yoshi's Cookie" full-clear AI.

Recommended Posts

Hi, long-time lurker first-time poster here. I am writing a Yoshi's Cookie clone that just implements the battle mode (no plans for a single player mode for now). I plan to create computer opponents that will battle against the human players, and have some finite-state-machine based opponents of various skill levels that look good on paper. But I also wanted to make an "insane" AI level that really showed off for the player, it would only score by setting up "full-clear" chain reactions. Here's a google video that demonstrates a human (I think) player with that level of skill: http://www.youtube.com/watch?v=lPtMygZYzqM Treating this as a graph searching problem, I have solved the 4x4 board (with 5 tile types) using uninformed breadth first search. When I try to upgrade to the real case, a 5x5 board with 6 tile types, the problem is too large to solve (4x4 case has up to 5^16 states with branching factor 16, the 5x5 case has up to 6^25 states with branching factor 20). I would like to try an informed heuristic search method like greedy search or A*, but it is not clear to me how the heuristic should work - it is tough to come up with a heuristic that guides the search towards full clears _without_ guiding it towards single row/column clears too. I would like opinions on writing a good heuristic for this goal. Below is a C code for the 4x4 case, the eventual target platform is flash / actionscript 3. I need quite a bit of speedup before this opponent will be able to function in real time - it might not be possible to do it using searching algorithms (maybe there is a clever state machine that can construct the board from the bottom up?). Thanks for the help!
#include <iostream>
#include <queue>
#include <map>
#include <string>
#include <vector>
#include <cstdlib>
#include <time.h>

using namespace std;

#define NX 4
#define NY 4
#define NT 5 

class GameBoard
  {
  public:	
    GameBoard();
    int tiles[NX][NY];
    // Make this GameBoard into a string. 
    string toString();      
    // Fill with random data.
    void initRandom();    
    void initString (string s);
    void cycleColumn (int direction, int x);
    void cycleRow (int direction, int y);
    void print ();
    int detectWin();
    int detectX (int shrink_x, int shrink_y);
    int detectY (int shrink_x, int shrink_y);
    int detectFullClear();
    void printFullClear();
  };

GameBoard::GameBoard()
  {
  }

void GameBoard::initRandom()
  {
  for (int ix = 0; ix < NX; ix++)
    for (int iy = 0; iy < NY; iy++)
      tiles[ix][iy] = rand() % NT;
  }

string GameBoard::toString()
  {
  string s = "";	
  for (int iy = 0; iy < NY; iy++)
    for (int ix = 0; ix < NX; ix++)    
      s += ( tiles[ix][iy] + '0' );	
  return s;    
  }

void GameBoard::initString(string s)
  {
  int used = 0;
  for (int iy = 0; iy < NY; iy++)
    for (int ix = 0; ix < NX; ix++)    
      tiles[ix][iy] = ( s[used++]-'0' );	
  	
  }

void GameBoard::cycleColumn (int x, int direction)
  {
  int temp;	
  switch (direction)
    {
    case 1:
      // Cycle positive.
      temp = tiles[x][NY-1];
      for (int iy = NY-1; iy > 0; iy--)
        tiles[x][iy] = tiles[x][iy-1];
      tiles[x][0] = temp;  
    break;
    case -1:
      // Cycle negative.
      temp = tiles[x][0];
      for (int iy = 0; iy < NY-1; iy++)
        tiles[x][iy] = tiles[x][iy+1];
      tiles[x][NY-1] = temp;  
    break;	
    }
  }

void GameBoard::cycleRow (int y, int direction)
  {
  int temp;	
  switch (direction)
    {
    case 1:
      // Cycle positive.
      temp = tiles[NX-1][y];
      for (int ix = NX-1; ix > 0; ix--)
        tiles[ix][y] = tiles[ix-1][y];
      tiles[0][y] = temp;  
    break;
    case -1:
      // Cycle negative.
      temp = tiles[0][y];
      for (int ix = 0; ix < NX-1; ix++)
        tiles[ix][y] = tiles[ix+1][y];
      tiles[NX-1][y] = temp;  
    break;	
    }	
  	
  }

void GameBoard::print ()
  {  
  for (int iy = 0; iy < NY; iy++)
    {
    for (int ix =0; ix < NX; ix++)
      cout << tiles[ix][iy];
    cout << endl;
    }
  }

int GameBoard::detectWin ()
  {
  
  int ans = 0;
  // Detect along x.
  for (int iy = 0; iy < NY; iy++)
    {
    int thisRowMatches = 1;	
    int detecttype = tiles[0][iy];
    for (int ix = 1; ix < NX; ix++)
      if (tiles[ix][iy] != detecttype)
        thisRowMatches = 0;
    if (thisRowMatches)
      ans = 1;
    }
  
  // Detect along y.
  for (int ix = 0; ix < NX; ix++)
    {
    int thisColMatches = 1;	
    int detecttype = tiles[ix][0];
    for (int iy = 1; iy < NY; iy++)
      if (tiles[ix][iy] != detecttype)
        thisColMatches = 0;
    if (thisColMatches)
      ans = 1;
    }  
  
  return ans;     	
  }

int GameBoard::detectX (int shrink_x, int shrink_y)
  {  
  // Try to clear along x.
  int iy = 0;
  int matchedY = -1;
  while (iy < shrink_y && (matchedY == -1) )
    {
    int thisRowMatches = 1;
    int detecttype = tiles[0][iy];	
    for (int ix = 1; ix < shrink_x; ix++)
      if (tiles[ix][iy] != detecttype)
        thisRowMatches = 0;
    if (thisRowMatches)
      matchedY = iy;
    else
      iy++;        
    }	
  
  return matchedY;	
  }


int GameBoard::detectY (int shrink_x, int shrink_y)
  {  
  // Try to clear along x.
  int ix = 0;
  int matchedX = -1;
  while (ix < shrink_x && (matchedX == -1) )
    {
    int thisColMatches = 1;
    int detecttype = tiles[ix][0];
    for (int iy = 1; iy < shrink_y; iy++)
      if (tiles[ix][iy] != detecttype)
        thisColMatches = 0;
    if (thisColMatches)
      matchedX = ix;
    else
      ix++;        
    }	
  
  return matchedX;	
  }


void GameBoard::printFullClear()
  {
  int shrink_x = NX;
  int shrink_y = NY;
  
  int could_clear_something = 1;
  
  while (could_clear_something && (shrink_x > 0) && (shrink_y > 0) )
    {    	    
    // Print the partial board.
    for (int iy = 0; iy < shrink_y; iy++)
      {
      for (int ix = 0; ix < shrink_x; ix++)
        cout << tiles[ix][iy];
      cout << endl;
      }
    cout << endl;    
    
    could_clear_something = 0;
    int matchedY = detectX(shrink_x, shrink_y);
    if (matchedY != -1)
      {
      could_clear_something = 1;
      // Copy up from matchedY down..
      for (int ix = 0; ix < shrink_x; ix++)
        for (int iy = matchedY; iy < shrink_y-1; iy++)
          tiles[ix][iy] = tiles[ix][iy+1];
      shrink_y --;    
      }
    else
      {
      int matchedX = detectY(shrink_x, shrink_y);
      if (matchedX != -1)
        {
        could_clear_something = 1;
        // Copy left from matchedX right...
        for (int iy = 0; iy < shrink_y; iy++)
          for (int ix = matchedX; ix < shrink_x-1; ix++)
            tiles[ix][iy] = tiles[ix+1][iy];	
        shrink_x --;    
        }
      }
        
    }
 
 
  }

int GameBoard::detectFullClear ()
  {
  int shrink_x = NX;
  int shrink_y = NY;
  
  int could_clear_something = 1;
  
  while (could_clear_something && (shrink_x > 0) && (shrink_y > 0) )
    {    	
    /*
    // Print the partial board.
    for (int iy = 0; iy < shrink_y; iy++)
      {
      for (int ix = 0; ix < shrink_x; ix++)
        cout << tiles[ix][iy];
      cout << endl;
      }
    cout << endl;
    */
    
    could_clear_something = 0;
    int matchedY = detectX(shrink_x, shrink_y);
    if (matchedY != -1)
      {
      could_clear_something = 1;
      // Copy up from matchedY down..
      for (int ix = 0; ix < shrink_x; ix++)
        for (int iy = matchedY; iy < shrink_y-1; iy++)
          tiles[ix][iy] = tiles[ix][iy+1];
      shrink_y --;    
      }
    else
      {
      int matchedX = detectY(shrink_x, shrink_y);
      if (matchedX != -1)
        {
        could_clear_something = 1;
        // Copy left from matchedX right...
        for (int iy = 0; iy < shrink_y; iy++)
          for (int ix = matchedX; ix < shrink_x-1; ix++)
            tiles[ix][iy] = tiles[ix+1][iy];	
        shrink_x --;    
        }
      }
        
    }
 
  if (shrink_x == 0 || shrink_y == 0)
    return 1;  // wow, full clear.
  return 0;  
  	
  }

struct Searchnode
  {
  string state;
  Searchnode* predecessor;
  };


int main ()
  {  
  GameBoard g;  
  srand ( time(NULL) );
  g.initRandom();
  
  cout << "Initial map state." << endl;
  g.print();
  cout << endl;
     
  // A queue to store search nodes.
  deque <Searchnode* > expandQ;
  
  // A map to record states we've already tried.
  map <string, int>  explored;
  
  // A search node that we'll new, over and over.
  Searchnode* s;
  
  // A list of search nodes to delete.
  vector<Searchnode*> garbageCollector;  
  
  // The winning game configuration.
  Searchnode* winNode = NULL;
    
  // Start searching. Origin node is the game state, as-is.
  s = new Searchnode;
  // Insertion procedure..
  s->state = g.toString();
  s->predecessor = NULL;
  expandQ.push_back(s);
  explored[s->state] = 1;
  garbageCollector.push_back(s);  
    
  // Search loop.
  while ( winNode == NULL && !expandQ.empty() )
    {
    // Pop the next node to expand.	
    s = expandQ.front();	
    expandQ.pop_front();
        
    
    g.initString( s-> state );
    
    // Does this node win?
    if (g.detectWin() )
      {
      if ( g.detectFullClear() )	
        winNode = s;
      }
    else
      {
      // Push all unexplored neighbor states of this node.
    
      // Cycle the rows +
      for (int iy = 0; iy < NY; iy++)
        {
        g.cycleRow(iy,1);
        // Is this state unexplored?
        if (explored.find( g.toString() ) == explored.end() )
          {
          // Add it to the explored map, and enqueue it.
          Searchnode* s_next = new Searchnode;
          s_next->state = g.toString();
          s_next->predecessor = s;
          expandQ.push_back(s_next);
          explored[ s_next -> state ] = 1;
          // Garbage collect this node later.
          garbageCollector.push_back(s_next);
          }
        g.cycleRow(iy,-1);
        }
    
      // Cycle the rows -
      for (int iy = 0; iy < NY; iy++)
        {
        g.cycleRow(iy,-1);
        // Is this state unexplored?
        if (explored.find( g.toString() ) == explored.end() )
          {
          // Add it to the explored map, and enqueue it.
          Searchnode* s_next = new Searchnode;
          s_next->state = g.toString();
          s_next->predecessor = s;
          expandQ.push_back(s_next);
          explored[ s_next -> state ] = 1;
          // Garbage collect this node later.
          garbageCollector.push_back(s_next); 
          }
        g.cycleRow(iy,1);
        }
    
      // Cycle the cols +
      for (int ix = 0; ix < NX; ix++)
        {
        g.cycleColumn(ix,1);
        // Is this state unexplored?
        if (explored.find( g.toString() ) == explored.end() )
          {
          // Add it to the explored map, and enqueue it.
          Searchnode* s_next = new Searchnode;
          s_next->state = g.toString();
          s_next->predecessor = s;
          expandQ.push_back(s_next);
          explored[ s_next -> state ] = 1;
          // Garbage collect this node later.
          garbageCollector.push_back(s_next);
          }
        g.cycleColumn(ix,-1);
        }
    
      // Cycle the cols -
      for (int ix = 0; ix < NX; ix++)
        {
        g.cycleColumn(ix,-1);
        // Is this state unexplored?
        if (explored.find( g.toString() ) == explored.end() )
          {
          // Add it to the explored map, and enqueue it.
          Searchnode* s_next = new Searchnode;
          s_next->state = g.toString();
          s_next->predecessor = s;
          expandQ.push_back(s_next);
          explored[ s_next -> state ] = 1;
          // Garbage collect this node later.
          garbageCollector.push_back(s_next);
          }
        g.cycleColumn(ix,1);
        }       
      }
    }
    
  
  if (winNode == NULL)   
    cout << "Full clear could not be found." << endl;
  else
    {
    cout << "Full clear animation:" << endl;
    g.initString( winNode -> state );	
    g.printFullClear ();
    	
    // Count back towards the goal.
    int pathlength = -1;    
    cout << "Reverse path:" << endl; 
    while (winNode != NULL)
      {
      g.initString( winNode -> state );
      g.print();
      cout << endl;
    
      winNode = winNode -> predecessor;	
      pathlength++;	
      }  
    cout << "Path length: " << pathlength << " moves. " << endl;    
    

    
    }
  
  cout << "Searched " << garbageCollector.size() << " different states." << endl;  
  // Delete all the searchnodes we new'd.
  for (unsigned int i = 0; i < garbageCollector.size(); i++)
    delete garbageCollector[i];
  
  return 0;	
  }


Edited by Timkin to fix the source tags [Edited by - Timkin on June 5, 2007 7:36:29 PM]

Share this post


Link to post
Share on other sites
I screwed up the source tags, what did I do wrong?


Edited by Timkin: we don't need two posts containing the same source code!

[Edited by - Timkin on June 5, 2007 7:17:32 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by rachil0
I screwed up the source tags, what did I do wrong?

*** Source Snippet Removed ***
You used '<' instead of '[' in your source tags. 
But you could edit the post anyway.

Share this post


Link to post
Share on other sites
*moderator hat on*
Please refrain from posting long excerpts of source code unless it is really necessary. Most people won't bother to read it anyway, for two reasons. (1) If you're after guidance in designing good AI, code isn't necessary; and, (2) if you need help optimising code for better speed, this is the wrong forum (General Programming would be a better forum for that sort of question).
*moderator hat off*

It's a tough problem simply because of the size of the state space. When you make a move (any move), it's value is not just related to the local arrangement of tiles, but also all possible future arrangements that can be derived from that local arrangement (so the value of a move depends on the value of the subtree of moves below it). This will be a highly nonlinear function and so designing a monotonic heuristic for this 'cost/value to go' will be difficult. I don't think I'd approach this from a search perspective, but rather from a reinforcement learning approach, since what you want (ideally) is a policy dictating the best move to make next given all possible moves (since you can't reasonably search for an optimal solution given a starting state). Policy or Value iteration algorithms can be applied offline for learning and then you need only store the result for use online (meaning you could run it on a platform with low processing capacity).

Cheers,

Timkin

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this