Gin Rummy AI Planning Stage

My approach for this project is going to be a bit different from how I approached the Minesweeper project. Instead of learning about algorithms for the game and basing how I play on those, I’ve spent some time just playing game after game of Gin Rummy and will be translating what I’ve learned from there into an algorithm.

There are two major decisions that need to be made each turn in Gin Rummy. I plan on making my AI focused on two major ideas: choosing what to discard and choosing from which pile to draw.

The containing class I write for the AI will have at minimum:

  • A list of cards in hand
    • Each will have a value associated with it based on how many deadwood points it’s worth, and how close to a meld it currently is
  • A list of cards in the discard
    • This will allow me to toss melds that I have less/no chance of making
  • A list of cards still in the deck
    • This allows for decisions to be made based on probability of drawing a card that completes a meld
  • Two major decision making functions
    • One for choosing which pile to draw from
    • One for choosing what card to discard

The decision to discard a card should be simple as long as the AI keeps up with the current game state, as each card in hand will have a value associated with it based on how many points it will cost to still have as deadwood, and how likely it is to be used in a meld.

Drawing should also be simple, I just need to check for each card still in the deck, if on average, it yields a better result than taking the top card from the discard pile.

If you want to keep up with current progress in the AI, feel free to check out the github project.

Minesweeper AI Code Report

My approach to the AI ended up not being very different from what I had planned in my last post.

I ended up making a single class to contain all of the tiles marked as either safe or as a mine. That same class has all of the functions that do checking on tiles as well. It’s called SpikerSweeper.

SpikerSweeper contains two int vectors, each containing a list of mines, either the known safe locations, or known mine locations.

Mines and safes get added to those vectors from my two major algorithms methods: detectMines() and detectSafes().

My mine detection works approximately like:

for every square with value N:
if it has exactly N adjacent-unopened squares:
add each of those squares as mines.

Safe detection is similar:

for every square with value N:
if it has exactly N adjacent-mine squares:
add each of those squares as safes.

The major article I used when developing my strategy for playing the game, that I then put into code for the AI, was a post on Bai Li‘s programming/math/tech blog, located here.

The major feature I didn’t have time to implement that I was hoping to, was Bai Li’s tank algorithm, which would have helped to solve the larger boards with much more consistency. As it is now, the program has a pretty high win rate on the beginner boards, but struggles with higher difficulties.

If anyone is interested in taking a look at the code, in it’s final form, check out my github.

Minesweeper AI Planning Stage

My approach to this project is going to be to try and solve it similarly to how a person would, with some changes to better utilize the computer’s ability to do large amounts of data processing very quickly.

A quick, off-the top, very rough idea of what this could look like would be:

  • A “controller” class that holds general data and drives the rest
    • Creates and holds references to the other classes
    • Stores some of the data needed by all other pieces
      • The board state in whatever format I decide to use
      • A list of tiles know to have mines, basically the flag system
  • A 3×3 “chunk” class that will hold the nine tiles needed for the quick-and-dirty algorithm
    • Holds the data for the chunk
    • Runs the quick square check to determine if there are any very-easily locatable mines
    • Returns the location of one if it finds it
  • An NxM chunk class that should solve most areas the 3×3 class can’t easily resolve
    • This separation means that the more time-intensive algorithm is only used as needed
    • This class will check every possible square and see if there is a possibility for it to contain a mine
      • Depending on how large NxM is, this could take a VERY long time, so it’s imperative that the controller class does a bit of legwork and sanity-checks areas and cuts them into more manageable pieces
    • The class then returns every square that it didn’t mark
      • In other words, squares that cannot contain a mine

The singularly most useful resource in forming both my ideas for this project, and for having really good starts (especially as I’ve never played minesweeper before) was a post on Bai Li‘s programming/math/tech blog, located here.

Next week, I’ll have my code up and (at least somewhat) implemented. Until then, you can take a look at what I’ve got so far on my github.