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

122

Author

June 04, 2007 09:13 AM

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:

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;
  
  return 0;	
  }

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

rachil0

122

Author

June 04, 2007 09:17 AM

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]

Zanshibumi

334

June 04, 2007 10:21 AM

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.

Timkin

864

June 05, 2007 07:49 PM

*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

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

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

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

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines