Gin Rummy AI – Planning

So, it is time for the next project for my Artificial Opponents class. This time, the game is Gin Rummy. Time to make a plan, I guess.

First off, Gin Rummy is a card game. In other words, it is a “game” you play with “cards.” Like many a card game, you cannot see the opponent’s hand. More importantly, the hand size (10 cards) is quite large – I’ll explain why this is important a bit later.

So I started doing some research to get some ideas of where to go with a card game AI. That led me to a few different places:

• Heuristics – One way to play is to assume that other players will attempt to make the most optimal choices, and then try to gain information and make choices based on this fact. For example, in Gin Rummy, you are trying to minimize your deadwood. So, if a player discards a card (and they are playing optimally), then one could theorize that this might be one of their higher cards. Ultimately, this is a strategy that can be combined with others, as I’ll talk about later on.
• Monte Carlo methods – In the context of game AI, Monte Carlo methods usually refer to using a tree search combined with simulating a bunch of possible games (and their outcomes) to pick the optimal move in a game. I’m not sure how useful that would be here, since (as I’ll mention further on) Gin Rummy is a game where the players have a lot of incomplete information, as opposed to a game like chess or tic-tac-toe (where both players have complete information about the board and each other).
• Minimax – Minimax is a method to choose the option that will minimize the loss of the player in a worst-case scenario. I initially counted this one out at first, since (like the Monte Carlo methods) it seems like you would need more information than Gin Rummy provides to the players. However, I then stumbled across this Stack Overflow post, which seems to suggest that, in a card game with incomplete information, you can build up and gather knowledge as the game progresses and then start using minimax.

As I previously mentioned, what we’re working with is incomplete information. In most multiplayer board games (such as chess, checkers, etc.), both players know everything about the board and position of each other’s pieces. In most multiplayer card games, however, there is at least some hidden information. For example, in blackjack, the dealer’s hand – as well as the cards that have not been played – are unknown.

But, while we may not know the other player’s hand, we do have a few tools at our disposal to gain knowledge:

• Likelihood of opponent knocking – While we do not know what is in our opponent(s) initial hand, we do know what cards they remove from their hand, as well as whatever cards they add to their hand from the face-up discard pile. So, at the very least, we can try to keep a running total of their deadwood. If we see them pick up several cards of the same rank, then perhaps they have just created a set, and we can subtract the total of those cards from our approximation of their deadwood. This could be useful if you want to make sure you will not be undercut by your opponent.
• Opponent’s choice of card to pick up – Every turn, a player must pick up a card, either from the discard pile or from the face-down pile of remaining cards (the “stock”). Since the discard pile is face-up, if the opponent does not choose from the discard pile but rather from the stock, then we can make a safe bet that their hand does not contain anything relevant to the card on top of the discard pile. This allows us to (potentially) grow our knowledge of the opponent’s hand as the game progresses.
• Card counting – This is probably the strategy I will make the most use of in this project. Since human memory isn’t holding us back, it will be very easy to count cards. Starting off, we already know our hand, so right off the bat that’s 10 cards that we know will not appear in the “stock” (the face-down pile of remaining cards next to the discard pile). Next, we know every card that both us and our opponent(s) discard, so as the game goes on, our knowledge of what could possibly be in the “stock” (or the opponent’s hand) improves. I think that this will be a very effective tool, and I’ll be testing out a few different card-counting methods to see which one will work best in the context of this AI.

So, those are a few strategies I’ll be attempting to incorporate. It seems like I’ll be doing a lot of trying to gather information about the remaining cards and the opponent’s hand. At the end of the day, knocking early seems to be the best strategy (unless your opponent can undercut you), but I’ll have to test that, I guess.

– wednesday

References

http://stackoverflow.com/questions/12666119/using-minimax-search-for-card-games-with-imperfect-information/12684468#12684468

http://stackoverflow.com/questions/21015352/monte-carlo-method-for-calculating-poker-equities

http://www.aihorizon.com/basiccs/trees/minimax.htm

Capstone – Week 4

The End of Week 3

After spending two weeks working on prototypes for our 4 ideas, it was time to get some feedback, and make a decision.

On the Saturday of Week 3, we each collected feedback on our prototypes (mostly from friends and roommates). The following day, we reconvened in our usually library meetup spot to chat about the QA feedback, then have a discussion to decide our fate (which game we would try to move forward with). After our discussion of the QA feedback, we then had an anonymous vote where we each voted for our two favorite ideas. A few of us (including myself) started to think that maybe Layers had some hidden potential. Nobody voted for the Lemon game. Since both Layers and Footsteps both got three votes, we decided to choose between those two. After going back and forth on the pros and cons of each for about 2 or 3 hours, we still couldn’t make a decision.

We reconvened for an online meeting later that night. Fortunately, this one took a lot less time, and we ended up deciding on the Footsteps game. Ultimately, it seemed like the game we were most prepared to present. In class the following day, we presented our ideas and received some good feedback.

Week 4

After our presentation to the class it seemed that we basically had 2 frontrunners: ACTF and Footsteps. The other two games (Layers and Mutant Lemon), we had decided as a team, had reasons why we didn’t want to go forward with them. I had been considering Layers on Sunday, I guess because I thought it had some kind of hidden potential. But ultimately, it’s downfall was that it would take at least another week to develop the idea to the point where we could feel comfortable presenting it as something we would go forward with. At this point, we need all the time we can get. Mutant Lemon, while an idea that we liked, was ultimately a bit too silly for our collective tastes. I think we realized that if we didn’t pull it off correctly, it either wouldn’t be taken seriously or it could be seen as too similar to the dreaded ball-roller genre. I can see myself working on it in other contexts, but just not for this capstone.

And that brings us to ACTF and Footsteps. I had counted out ACTF a bit at our decision meeting, probably because I just kept having thoughts about possible worst-case scenarios. But, in reality, networking is a lot easier in Unity than in the lower-level format Ben and I had learned it in. Even so, networking adds additional time and complexity to any project you decide to use it on, but still. ACTF was an idea that people seemed to get excited about, in regards to the traps especially. Additionally, it was a game that fit our strengths as a team: Alexis wants to specialize in hard-surface modeling (robots, metallic sci-fi environments, etc) – which this game would have a lot of, the game would have a lot of level design (which Eva really enjoys), and Ben and I could divide the programming tasks between ourselves according to our strengths.

Meanwhile, Footsteps provides some advantages, mostly being that it would be a lot easier to make (in theory) – it’s single player, has no networking, and could potentially have a lot of modular low-poly art.

But, in our meeting the day after the presentation, we decided that if Layers was off the table (no one had voted for the Lemon game in the decision meeting), we would consider ACTF. And soon after that point had been brought up, and after considering the feedback from class, we decided to switch to ACTF as the idea we would move forward with. It was just an idea that we seemed to be more excited about.

So that’s where we stand right now. We’re moving forward with ACTF. It’ll probably be more work than the Footsteps game, but it’ll also probably be a lot more rewarding if we manage to pull it off.

Minesweeper AI – Postmortem

So, my AI ended up performing decently, but not great.

Since last time

At the time of my last minesweeper post, I was trying to fix the brute force algorithm. However, as I was testing some modifications, I decided to see how often each portion of my AI was being called. As I might have stated before, the three components of my AI implementation were:

1. “Basic strat” – flagging cells that were guaranteed to be mines (when the number of hidden cells adjacent to a revealed cell are equal to the revealed cell’s mine number) and then revealing cells based off of the flags that were guaranteed to not be mines
2. Weighted pick – get all hidden cells bordering revealed cells and calculate the local probability of it being a mine, then reveal the cell with the lowest weight
3. Brute force algorithm – go through all possible mine configurations for the hidden cells bordering revealed cells and choose the cell that appears in the least configurations

As I was observing how many times each component was being called, something seemed to be off – the the basic strategy was not being called a lot of the time and was failing when it was called. It ended up being a simple bug that was causing the basic strat to fail very often. After fixing that, my win percentage became a lot better. Now, I could consistently win around 90% games of each board size with the class (easy) parameters. When testing with the actual minesweeper settings, however, I was winning around 15/30, 7/30, and 1/30 games (S, M, L) with the actual minesweeper parameters.

So, now that the basic strat was fixed, I spent the rest of my time trying to fix the brute force algorithm and testing different combinations of brute force and weighted picking. In the end, it seemed like the brute force algorithm didn’t make too much of a difference.

Analysis

Anyway, here’s some stats on how well the AI performed. Most of the time I was testing 30 games of each difficulty. Here’s some stats for one of the 30/30/30 test sessions using the class parameters, and one of the test sessions using the minesweeper parameters.

parameter specs

class parameters

minesweeper parameters

So, I did quite well with the class parameters, and not-so-great with the minesweeper parameters. However, I did improve the win percentage quite a lot since my last post, but that was probably mostly due to fixing the bug with the basic strat.

Thus, my AI does better when there is a lower mines-to-cells ratio, and struggles once the mine start to take up a larger percentage of the board, as they did in the minesweeper parameters. This would in theory be the place where the brute force algorithm would pick up the slack, but unfortunately, that didn’t work out as well as I planned. However, my basic strat worked quite well and did win a lot of (easy) games, and a few difficult ones.

What went wrong

In terms of bringing my AI to the next level (going beyond the basic strat), I had mixed results. I do indeed believe that I made a brute force algorithm that was able to generate several possible mine configurations. However, it was very inefficient in that it did so in a random manner, placing mines at random (if possible) until a configuration was generated. Also, I was unable to get the actual maximum number of possible combinations, because I think you might need the number of mines remaining to do so (and this might be impossible in situations where configurations of different numbers of mines satisfy the conditions). I might be wrong about that. Anyway, I wrote the first pass on this brute force algorithm when I was quite tired, so there were some bugs that I fixed in the following days. But, I must’ve done something wrong, because ultimately, the algorithm did not strengthen my win percentage that much (sometimes not at all). I retraced my logic and went through the various functions I wrote (for the algorithm) a few times, but it definitely would’ve benefited from more rigorous testing and picking apart.

You would expect the brute force algorithm to be able to shine brightest in situations where there are lots of mines, because this typically means lots of data and fewer possible safe cells. However, like I said, the brute force algorithm did not improve my win percentage, and so was not very successful.

What went right

Although I had a few slip-ups getting the basic strat implemented, ultimately I got it working quite well – to the level that it would be expected to at least, it’s a very common strategy. But, that was sort of the base-line for this project. I felt like the List class I made did indeed help me and made my code a tad cleaner, so that was nice as well. And even though my brute force algorithm failed, I thought that it was a good exercise to try and sort out the logic for such an algorithm, even if my implementation was very inefficient.

If I had more time?

Time was one the primary constraint for this project (we had roughly 1.5 weeks to work on it). If I had more time to work on it, I definitely would write a proper brute force algorithm, or at the very least, I would test my current one much more extensively to see where its flaws are. Going along with that, I would try to improve the efficiency of the brute force algorithm. Aside from that, I would potentially add some logic for situations where it gets close enough to the endgame where you can use your knowledge of how many mines remain to choose the correct mine configuration.

Overall, it was pretty fun to work on this project. I like the idea of making an AI to play a game. Before this, I’d only done it a handful of times. One time I had made a simple flashpunk game, and I made it play itself in order to figure out if the memory used by the game was too much (it was, needed to recycle sprites more). Last semester, I made kind of a makeshift AI for my Production II game so I could test our game without needing 4 controllers (it sorta worked but had several bugs, so it didn’t make it into the final build). Ultimately, I liked working on this Minesweeper AI but I can’t wait to dive into our next project: making an AI to play Gin Rummy.

-wed

 

Capstone – In the middle of Week 3

Hi! I am [wednesday], one of the programmers for the capstone team Turtle Collective. Well, two weeks have gone by, so I figured I’d start out this post by recapping the last two weeks. Sorry if this ends up being a wall of text – once I’m on a more weekly posting schedule hopefully these will be shorter.

The team

Our team is made up of four people: Eva (a designer), Alexis (an artist), me (a programmer), and Ben (another programmer).

Week 1

Arriving at school for our senior year of college, we were all eager to dive in to capstone. We had one preliminary meeting using Google Hangouts over the summer, mostly just to discuss some of Eva’s initial ideas. During the first week, we basically just thought up a bunch of ideas (most of them being Eva’s, much to her chagrin (she wanted the rest of us to talk more)) and fleshed them out a bit through the course of several meetings. After that, we voted on each one and threw out the ones that no one wanted to do, or to pitch. After voting on the ideas and consolidating a few, we ended up with 9 ideas.

Week 2

We pitched all 9 ideas in class on the Monday of Week 2. Two days later, we realized we had some tough decisions to make. To challenge for the Initial Concepts stage, we needed prototypes of at least 3 games (as well as informal QA for each). Ben, Eva, and I had already started prototypes for three of the games, but remember, we had 9 ideas at the time. It was clear that we would not be able to prototype all of them in one week. Initially, we wanted to challenge on the Monday of Week 3, but it soon became clear that even with a reduced number of prototypes to make, we would really need to take 2 weeks to fully flesh out the prototypes (thus, presenting on the Monday of Week 4). So, we decided to cut 5 of the ideas and we ended up with 4 game ideas to prototype and QA.

The Games

1. ACTF (Asymmetrical Capture-the-Flag) – A 2v2 CTF game
   • time element – the first “attacking” team (the one that takes the flag) sets a PR for how much time it takes them to take the flag. Once the teams switch sides, the other attacking team must beat their time.
   • verticality – the maps are more vertically based than most multiplayer action games. So, players have to climb to the top of the map to get the flag.
   • traps – the defending team can choose from a variety of traps to try and hinder the attacking team. Since the maps are vertically based, some of these (such as a trap door) involve sending a player to a lower position in the map, forcing them to waste time climbing up to the top again. Some traps are automatically activated, while some have to activated manually by a defending player.
   • Prototype: For this game, the element that sets it apart from other similar games is the traps. So, the prototype will focus on testing out these traps.
2. Layered Shooter – A platforming boss-rush game
   • layers – the screen is comprised of 4 different layers that the player can switch between. When a boss attacks, its attack will take place on one of the layers, so the player can switch between them to avoid a certain attack.
   • platforming – parts of a boss will be on different layers. To defeat a boss, the player might have to climb up the boss by platforming and switching between the different layers to reach the top of the boss, where there could be a weak spot or something similar.
   • Prototype: Prototype the layer-switching and platforming with the layer-switching.
3. Mutant Lemon – A stealthy 3d platformer
   • mutant lemon – you play as a mutant lemon in a supermarket attempting to mutate the other lemons
   • movement – your basic form of movement is just rolling around, which is quite slow (but quite stealthy). Since you are mutated, you have a few other movement options, however since these options incorporate mutant tentacles or something similar, these will freak people out if they see you (you are in a grocery store after all, so there will be plenty of people there). So, you must be careful to not alert any people while moving around with your various options.
   • NPC levels – while the average shopper may think nothing of a lemon rolling around, the store manager might think it’s a bit more suspicious. There will be various levels of NPCs, some more suspicious of certain actions than others.
   • duckling lemons – once you mutate other lemons, they follow you around like ducklings.
   • Prototype: Prototype the movement and a bit of the stealth gameplay.
4. Alt Fireflies – An isometric action-puzzle game
   • glowing creatures – you’re in a forest at dusk and there are many creatures around that you must navigate around to get to your destination.
   • lanterns – you have various lanterns that can charge up the creatures so that they glow more, make aggressive creatures passive, and attract fireflies.
   • you can throw lanterns
   • Prototype: Prototype creatures moving around with glow and darkness fog-of-war.

Week 3 so far

So far, I have prototyped movement, the camera, and NPC AI for the Lemon game, as well as 3 of the basic traps for ACTF. I’ll be working on them more this week to get them ready for QA this weekend. Ben is working on the Fireflies game, and Eva is working on the Layers game. We’re going to help each other out on the prototypes as needed. Alexis is doing concept art.

 

Minesweeper AI – Implementation

In my previous post I discussed my plan on how I was going to create my Minesweeper AI implementation. Now that I’m mostly finished, I will now discuss how my implementation turned out.

General Approach

Overall, my approach was pretty simple:

1. use the basic “guaranteed” Minesweeper novice strategy (looking for revealed cells that are touching a number of hidden cells equal to their mine number) until it cannot be used anymore
2. brute force through all the possible combinations of mines on the border cells to get the best probability of where the next mine is

Originally I thought about looking for patterns, like the 1-2-1 and 1-2-2-1 pattern, but overall, this is where I had to compromise a bit, as my the original way I set up my logic wasn’t really conducive to pattern matching.

Classes Used

List – this was a simple extension of the std::vector class that I made in order to make my code cleaner and more readable. Has various functions such as add(), remove(), getIndex(), contains(), etc., like you would find in the C# List class.

CellChecker – this is where I put all of my logic for choosing the next cell to reveal. I probably could’ve split this class up a bit more. It is separated into functions for the basic strategy and the brute force strategy, with copious helper functions to facilitate both.

• basic strategy
  • buildRevealedOpenList()
  • buildFlaggedList()
  • chooseCellsToReveal()
• brute force
  • bruteForceLogic()
  • checkIf2DVectorContainsVector() – checks to see if a board combination has been tried before
  • adjNumsZeroed() – checks to see if the current possible combination (that is being tested) has placed all the mines it needs to
  • getIfCanPlaceInvisibleFlag() – checks to see if a flag can be placed at a certain cell in the current possible combination (that is being tested)
• various helper functions

Algorithms?

The basic strategy was just based on the psuedocode I had created in the previous post, with some tweaking to get it “working.”

As for the brute force strategy, I based the idea of it on this post, as well as a few other resources (linked below in the references section) but I had no idea on how to create the actual algorithm for generating possible combinations. So, I came up with a really inefficient method that literally picks random border cells until it comes up with new combinations, and keeps doing that until it has a decent number of possible configurations. Very inefficient, possibly broken, likely flawed, but hey, that’s what I have right now.

Compromises

The brute force idea was much more difficult than I expected to implement. I think part of the problem was that I set up my initial logic for the AI more to suit the basic strategy, rather than anything more complicated than that. Had I set up a more sophisticated system of looking at possible configurations and patterns and such, I think I would be in a much better position now. As it stands, I’m just going to try and refine the brute force strategy and hope it combines well with the basic strategy to form something halfway decent.

Assessment

I don’t have very high hopes for my AI (in its current state). Here’s how it currently stands: on 3 board sizes (Large, Medium, Small) with much easier mine counts than in regular Minesweeper, it will win about 30% Large, 40% Medium, and 60% Small with just the basic strategy supplmented with random picking. However, these mine counts are not even close to what is used in an actual Minesweeper game. When I set the board sizes and mine counts to the classic Minesweeper standards (Large: 16×30 with 99 mines, Medium: 16×16 with 40 mines, Small: 9×9 with 10 mines), my AI won around 0% Large, 0% Medium, and 5% Small. I even played around with the mine counts and it was only when I got within a close range to the original easier constraints, that I was able to repeat my original moderately successful results. Of course, this is where the brute force part of the AI will be useful: situations where the basic strategy just isn’t enough. Unfortunately, as of right now, my brute force supplement is still a bit buggy, so I’m hoping that once I fix it (before this Friday), then it will provide the added competency needed in order to improve my AI’s win rate.

And that is how things stand at this moment, as far as my implementation goes. Next steps: fix brute force algorithm, make both the basic strategy and brute force logic more cohesive, and get a decent win rate by Friday.

– wednesday

References

http://www.minesweeper.info/wiki/Strategy

http://www.nothings.org/games/minesweeper/

https://luckytoilet.wordpress.com/2012/12/23/2125/

 

 

Minesweeper AI – Planning

So, Minesweeper is a game. As I have to implement an AI for my Artificial Opponents class that will play Minesweeper, what follows could be considered my plan regarding how I will go about implementing this AI logic.

A Preface

I’m somewhat of a novice when it comes to Minesweeper. I’ve played it casually, sure, but I don’t know much about the competitive scene. Thus, my plan for implementing this Minesweeper-solving logic will probably follow a more neophyte-level strategy. However, I may augment this with some more advanced strategies if it isn’t good enough.

General Approach

When playing minesweeper I try to build off of the corner tiles that you can essentially guarantee have a mine beneath them, and thus, flag. Corners like these:

A fresh corner

Thus, here is how the general logic of my AI implementation will work:

1. random guess

2. put every revealed numbered tile (that is not already in the closed list) in an “open” list
3. go through open list and find every tile that only has a number of unrevealed adjacent tiles equal to its “adjacency number” – flag those unrevealed tiles
4. move those numbered tiles to a “closed” list
5. put all flagged tiles in an “open” list
6. go through Adjacent Revealed Tiles of each open flagged tile – if the adjacency number requirement (of an Adjacent Revealed Tile) is met and there are any unrevealed tiles adjacent to a Adjacent Revealed Tile, flip those tiles

7. repeat 2 – 6 (if stuck, repeat steps 1 – 6)

Psuedocode

1

indexChoice = random

2

for each (tileNumber in tileArray)

if (!uncoveredClosedList.contains(tileNumber))

uncoveredOpenList.add(tileNumber)

3 – 5

for each (tileNumber in uncoveredOpenList)

if (checkNumOfHiddenAdjacent(tileNumber) == getAdjacencyNumber(tileNumber))

flaggedList.add(getHiddenAdjacentTiles(tileNumber))

uncoveredOpenList.remove(tileNumber)

uncoveredClosedList.add(tileNumber)

6

for each (tileNumber in flaggedList)

for each (adjacentTile in getRevealedAdjacentTiles(tileNumber))

if (adjacencyRequirementMet(adjacentTile))

for each (adjacentUnrevealed in getUnrevealedAdjacentTiles(adjacentTile))

flipTiles(adjacentUnrevealed)

Major Classes

I plan on having a few classes.

Firstly, I’m working in C++, which doesn’t have the convient List class that C# does, so I’ll probably make my own (using std::vector) and incorporate some simple list functions – like contains(), add(), remove() – in order to make my code a bit cleaner.

Secondly, I’ll probably have some sort of TileLogic class or something of the sort. Basically, this will have functions like getUnrevealedAdjacent(), getRevealedAdjacent(), etc. (all of the functions that gather certain indices based on data from the GameView and Cell classes), as well as functions to ensure that these indices checks don’t go out of range of the tile array. This class will also store flagged tiles and hold the various open and closed lists required for my implementation.

 

Scalability

The implementation I have described above is a somewhat beginner/intermediate strategy. While it may work on easier board arrangements, there will probably be times on more difficult boards when there is no clear-cut next move to take, and a random guess will be less than desirable. Fortunately, there are some more advanced tactics to be aware of in the world of competitive minesweeper. Of particular note is the two primary patterns (1-2-1 and 1-2-2-1), which be potentially be used on sections of board where there are no clear-cut “guaranteed” situations (at least according to my basic logic loop). Recognition of these two patterns could be added into my logic fairly easily and could potentially help in tough situations. Unfortunately, random guessing is sometimes necessary, but hopefully I can minimize the amount needed in my AI implementation.

Example of the 1-2-1 Pattern

Example of the 1-2-2-1 Pattern

 

– wednesday

References

General:

http://www.minesweeper.info/wiki/Strategy

http://www.minesweeper.info/wiki/Tournaments

Images:

minesweeper.info/wiki/Image:Pattern121.PNG

minesweeper.info/wiki/Image:Pattern1221.PNG