Algorithm for making sets in a Rummikub game

Question

I'm developing an Okey game (a Turkish version of Rummikub/Rummy). In it, each players has a bunch of tiles. Tiles have a colour and a number, like playing cards. Now, the player needs to make sets of these tiles, with three options:

• Groups: Same number, different colours (Red 1, Blue 1, Black 1)
• Straights: Same colour, sequence of numbers (Red 1, Red 2, Red 3)
• Doubles: Two identical tiles

I'm now trying to create a simple AI for the game. I want it to be able to find and create sets in/from its own tiles.

I already have a TileSet class. Feed it a list of tiles and it will say whether it's a valid set and of what type.

Using this, what kind of algorithm can I use to find the sets in an unordered heap of tiles?

Answer 1

Since you have 52 distinct cards, you can represent them as bits and fit in a 64-bit int. E.g. taking suit as an int in 0-3 and card as an int in 0-12 one way of packing them would be

int64 ToBit(int suit, int card) { return ((int64)card) << (16 * suit); }

Then you can easily detect doubles and get a bitmask representing the cards present in a list:

List<int64> cardsAsBits = ...
int64 cardsAsBitset = 0, doubles = 0;
foreach (int64 card in cardsAsBits) {
    doubles |= (cardsAsBitset & card);
    cardsAsBitset |= card;
}

To check for doubles now you just have to look at the set bits in doubles. To check for straights and groups it's just a case of making a suitable mask and &ing.

for (int i = 0; i < 11; i++) {
    for (int suit = 0; suit < 4; suit++) {
        int64 straight = 7L << (i + 16 * suit);
        if ((cardsAsBitset & straight) == straight) handleSet(straight);
    }
}

for (int i = 0; i < 13; i++) {
    int64 group1 = 0x0000000100010001L << i;
    int64 group2 = 0x0001000000010001L << i;
    int64 group3 = 0x0001000100000001L << i;
    int64 group4 = 0x0001000100010000L << i;

    if ((cardsAsBitset & group1) == group1) handleSet(group1);
    if ((cardsAsBitset & group2) == group2) handleSet(group2);
    if ((cardsAsBitset & group3) == group3) handleSet(group3);
    if ((cardsAsBitset & group4) == group4) handleSet(group4);
}

Answer 2

use a nested loop.

outside loop is the tile sets on the board and the inside loop is the ai tile.

one at a time pass the tile set class a tile from the ai and a set on the board to see if it is a viable move.

if you want the ai to make mistakes the have a random generator in the loop so it dosn't check all of its tile for every set on the board or jumble the order it searches the tiles on the board and take the first move available so it doesn't always take the best move.

hope this helps

Answer 3

You could try something like this (using C# syntax, not verified for correctness). Note also that I'm not instantiating the inner-collections, for brevity.

Dictionary<int, HashSet<Color>> groupTest = new Dictionary<int, HashSet<Color>>();
Dictionary<Color, bool[]> straightTest = new Dictionary<Color, bool[]>();
HashSet<Tile> doubleTest = new HashSet<Tile>();
foreach (Tile tile in AllTiles)
{
  if (doubleTest.Contains(tile)) { /* Found a double */ }
  groupTest[tile.Number].Add(tile.Color);
  straightTest[tile.Color][tile.Number] = true;
  doubleTest.Add(tile);
}
foreach (int number in groupTest.Keys)
{
  HashSet<Tile> group = groupTest[number];
  if (group.Count >= 3) { /* Found a group */ }
}
foreach (Color color in straightTest.Keys)
{
  HashSet<int> straight = straightTest[color];
  int consecutive = 0;
  for (int i = 1; i < HIGHEST_NUMBER; ++i)
  {
    if (straight[i-1] && straight[i])
      consecutive++;
    else
      consecutive = 0;

    if (consecutive >= 3) { /* Found a straight. */ }
  }
}