Category Archives: Technology

Dominion Strategies

What is Dominion?

I was recently introduced to a game called Dominion. As any nerd would do, I wrote a program that pits different strategies against each other over thousands of games and collects statistics about how each strategy did. This is some early data.

Note that this entire post will only make sense if you know how to play the game.

Strategies

These are the three strategies I’ve coded so far:

  • BigMoney
    • Summary: Build up your buying power and buy provinces whenever you can
    • Action phase: No action cards to use
    • Buy phase:
      • If it has 0-2 buying power: Buy nothing
      • 3-5: Buy silver
      • 6-7: Buy gold
      • 8+: Buy province
  • 1Smithy
    • Summary: Do the same thing as BigMoney, but buy a smithy at the first opportunity
    • Action phase: Whenever the smithy is drawn, use it to draw 3 more cards
    • Buy phase:
      • 0-2: Buy nothing
      • 3: Buy silver
      • 4-5: If it has no smithies, buy one; otherwise, buy silver
      • 6-7: Buy gold
      • 8+: Buy province
  • GardenWorkshop
    • Summary: Using workshops to gain more cards, buy lots of cards to maximize the points from gardens
    • Action phase: Whenever a workshop is drawn, use it to:
      • Gain another workshop until there are no more
      • If there are no more workshops, gain a garden
      • If there are no more gardens, gain an estate
    • Buy phase:
      • 0-1: Buy copper
      • 2: Buy estate
      • 3: Buy workshop
      • 4+: If it has no workshop, buy one; otherwise, buy garden

Methodology

I pitted each of the strategies against each other over 10,000 games and plotted the results below.

  • The blue line shows the victory points of the first strategy as the games progressed
  • The red line shows the victory points of the second strategy as the games progressed
  • The green bars show how many games out of those 10,000 actually had that many turns. When the green bar is low, that means the blue and red lines don’t mean much because the sample size is small. This means that you should just pay attention to the blue and red lines up until the green bars start to fall below 10,000.

1Smithy vs. BigMoney

Deck stats:

1Smithy BigMoney
Average Buying Power: 32.8 36.1
Average Deck Size: 26 25.5

Turn and win stats:

Average Turns: 16.4185
Wins:
1Smithy: 4966 49.60%
BigMoney: 1745 17.40%
Ties: 3289 32.80%

GardenWorkshop vs. 1Smithy

Deck stats:

GardenWorkshop 1Smithy
Average Buying Power: 11.7 36
Average Deck Size: 38.1 28

Turn and win stats:

Average Turns: 19.517
Wins:
GardenWorkshop: 8808 88.00%
1Smithy: 1192 11.90%
Ties: 0 0.00%

GardenWorkshop vs. BigMoney

Deck stats:

GardenWorkshop BigMoney
Average Buying Power: 11.6 40.3
Average Deck Size: 38 28.1

Turn and win stats:

Average Turns: 19.5507
Wins:
GardenWorkshop: 9702 97.00%
BigMoney: 298 2.90%
Ties: 0 0.00%

Conclusion

BigMoney is a pretty good strategy. It can end the game pretty quickly and it racks up provinces pretty fast.

1Smithy improves on that by getting those extra cards when you draw the Smithy. I tried 2Smithy, 3Smithy, etc. but they all performed worse than 1Smithy.

I was surprised just how much better 1Smithy performs over BigMoney. 50% win rate / 33% tie rate is quite good.

The most unexpected result from this initial data was just how good GardenWorkshop performed. It completely blows both BigMoney and 1Smithy out of the water.

Next time you play me in Dominion, you know what strategy I’ll go =]

I’d love to hear other strategies you want me to code up. Leave a comment if you like!

KenKen Flash Game

Two weeks ago, I got a free copy of Adobe Flex 3 since Jo is a teacher! So I’ve been learning Flash and it’s been a lot of fun.

I started by porting my old Texas Hold’em Odds calculators from Java to Flash (since no one has Java =p). I still wanted to use Java for the back end calculations, so I also had to learn how to write Java Servlets. It’s been a lot of fun. Mostly because I’m a big fat nerd.

After getting a little Flash experience I created a new KenKen application. Check it out and let me know what you think: http://www.ben61a.com/kenken/

Jo can beat a 4×4 in 30s. She’s also beat a 9×9 in 21 minutes.

Java Sudoku Solver

Jo has really been into Sudoku the past few months. Being the nerd that I am, I spent the past few weeks coding up a Sudoku solver that you can check out at http://www.ben61a.com/sudokusolver/. (If you’re not familiar with the game, read about it on its Wikipedia entry.) It has been, and continues to be, an interesting project because solving Sudoku turns out to be relatively complicated.

The first work item I completed was a fast solver. The solver first translates a Sudoku into an exact cover problem. It then uses the Dancing Links technique, originally suggested by Donald Knuth in this paper, to efficiently find all solutions to the exact cover problem. In the case of a well-formed Sudoku, there is only one solution. That exact cover solution is then translated back into a Sudoku solution grid.

Next, I used this Dancing Links solver to create a puzzle generator. This simple generator starts with a blank grid and adds a random digit to a random cell over and over. After each addition, I use the fast solver to see if there is only one solution; if so, then we have a new Sudoku. If there are no solutions, we have to backtrack because the last digit added messed up the puzzle. I used my puzzle generator to create 50,000 puzzles (it took about 8 hours or so because of the massive number of fast solves that are done).

Unfortunately, the nature of the algorithm used by the fast solver suffers two problems:

  1. It can’t give any clues as to how to solve a Sudoku in a stepwise, human-logic-based manner
  2. There is no way to judge difficulty aside from counting the number of hints given in the Sudoku

To remedy both problems, I wrote a new solver that uses human-logic-based solving techniques. Whereas the fast solver can solve any well-formed Sudoku, my new logic-based solver can only solve around 98% of puzzles since some require more advanced logic techniques that I just haven’t coded yet. These are the major solving techniques I have coded so far:

  • Singles
  • Naked Pairs
  • Locked Candidates
  • Naked Triples
  • Naked Quads
  • Hidden Pairs
  • X-Wings
  • Coloring

Based on the number of types of techniques a puzzle requires to be solved, I was now able to classify puzzles in an (admittedly) subjective manner:

  • Easy if the only technique required is Singles
  • Medium if the only techniques required are Singles, Naked Pairs, or Locked Candidates (and it’s not an Easy puzzle)
  • Hard if it’s not an Easy or Medium puzzle
  • Evil if my logic-based solver cannot solve it using any of its techniques

Surprisingly, 47739 of the 50000 generated puzzles (95.5%) were classified as Easy (only required Singles). That’s crazy! As for the rest, 755 were Medium, 493 were Hard, and 1013 were Evil.

Finally, I put a user interface on top of the logic-based solver and put it online as a Java applet, linked above. It’s really just a first blush at a UI, so I know there can be much improvement.

Anyway, I’d love to hear your impressions and feature ideas, so leave a comment!

Several notes:

  • Because of the sheer size of storing 50000 puzzles even just as strings, I made a decision to only include 250 Easy, 250 Medium, and 250 Hard puzzles in the applet. This means that when you click “Easy,” you will only be given a puzzle from a pool of 250 puzzles.
  • I’m thinking about porting my poker and Sudoku applets to Flash since no one uses Java =p. It looks like I’d need to buy some Adobe software to do that though (not to mention learning Flash), but it sounds fun. Look for that in the future.

WikiMapia

I love maps and I am loving WikiMapia. It not only helps me identify landmarks when I’m going to an unfamiliar place, but it also lets me learn about things I didn’t know existed in places that I’m extremely familiar with. Last week, I learned that there are several pieces of the Berlin Wall right next to my church in some office complex.

Check out the South Bay and zoom in to see more: http://wikimapia.org/#lat=37.391164&lon=-121.997509&z=13&l=0&m=a&v=2

I’ve already added a few places =]

Edit: Jo found “Happy, happy, happy guy” !!!! Hahahahahaha

MySong – Microsoft Research

Most folks never get a chance to answer this question, since writing music takes years of experience… if you don’t play an instrument or spend lots of time around music, you’ll probably never get to write a song.

MySong, introduced in our CHI 2008 paper, automatically chooses chords to accompany a vocal melody, allowing a user with no musical training to rapidly create accompanied music. MySong is a creative tool for folks who like to sing but would never get a chance to experiment with creating real original music. Come on, you know who you are… you sing in the car, or in the shower, or you go to karaoke clubs, or you just once in a while find yourself singing along with catchy commercial jingles. MySong is also a great tool for songwriters who want to quickly experiment with melodies and accompaniments.

Check out the video!

http://research.microsoft.com/%7Edan/mysong/

Poker Programming

Nerd alert! I recently got back into programming in Java. I started by retrofitting my old Texas Hold’em Odds Calculator so 1) it runs about an order of magnitude faster, and 2) it includes icons for the card suits.

Tenis suggested a new applet to work on: He wants an applet for Texas Hold’em that, given his starting hand, tells him what opponent starting hands would likely beat him and what opponent hands he would likely beat. Because of the sheer combinatorics, I scoped the problem down and refined it a bit: Given your starting hand and the flop, list the percent chance that the given starting hand will beat or be beaten by all other possible starting hands.

I took up the challenge and tonight I finished the engine behind the applet; I still have to write the user interface, which can take a while. While I go do that, here’s some math and sample input/output (let me know if you see any bugs):

Math

  • There are 1,326 (52 choose 2) possible starting hands in Texas Hold’Em
  • Since we’re given your starting hand and the flop, we are left with 1,081 (47 choose 2) starting hands that oppose you
  • We compare your starting hand against each of the 1,081 opponent starting hands one at a time
    • For one such comparison, we know your starting hand, your opponents’ starting hand, and the flop, which leaves 45 cards in the deck for the turn and the river
    • In other words, there are 990 (45 choose 2) possible combinations for the river and turn
  • This means that to analyze one starting hand + flop combination, the applet examines 990 combinations for each of the 1,081 opponent starting hands, or 1,070,190 hand comparisons (990 x 1,081)

Edit: Here’s the first draft of the new Texas Hold’em Matchups calculator

The Great Double Standard

Disclosure: I am a Microsoft employee; however, the content of this blog does not necessarily reflect the views or policies of Microsoft Corporation.

Joe Wilcox recently discussed how Microsoft’s past mistakes have haunted itself by causing negative perception in the media and marketplace to a degree more severe than deserved. I liked the article a lot, but I think I took it in a slightly different way than he intended. I first reacted with a, “Word! This sucks! We don’t deserve that.” But then, I remembered that we really did this to ourselves and that, more importantly, we are responsible for digging ourselves out of this. It’s going to be extremely difficult, but I hope we can change that perception in the coming years.

I’ve peppered comments through selected portions of the article. Check out the link below for the full text.

Two closely timed events—today’s release of Mac OS X Leopard and yesterday’s big Microsoft earnings report—raise questions yet again about how Microsoft and Apple are perceived.Apple it seems can do no wrong, while Microsoft can do no right. If someone passes gas in the room, someone blames Microsoft. Yet Apple can “brick” iPhones for which customers paid $400 to $600 and sales just soar.

Microsoft reports solid earnings quarter after quarter—and yesterday beat earnings estimates by more than $1 billion. Yet Microsoft’s stock price is stuck at 2001 levels. Apple earnings results are good, but nowhere near what Microsoft delivers. Yet Apple’s stock just climbs and climbs—this morning to more than $185 a share, up from about 77 bucks 52 weeks earlier.

. . .

Apple’s success is one of perception, spurred on by some very smart marketing and branding decisions made over the past six years. Apple is a cool brand that people want to be associated with. When people really like something, they also tend to be more forgiving of faults.

[ben61a] I think the above statement goes a bit far; Apple makes some amazing products, which I believe is more a factor in their success than perception alone.[/ben61a]

By contrast, Microsoft has huge perceptions problems, many of its own making. For years, Microsoft rushed OK products to market, leading to a popular (and usually right) perception that the company wouldn’t get it right until the third release. Marketing 101: The products are the company, and its image. I hear people complain about buggy, crashy Windows, years after Microsoft released the very stable and reliable XP and, later, its Service Pack 2 update; the days of perennial crashes are long gone, but not forgotten.

Microsoft’s past behavior has created some perception that its products aren’t good enough, that the company doesn’t care for customers. Windows Vista is a poster product for Microsoft’s perception problems: It’s got an undeserved bad reputation.

[ben61a] Someone out there is saying that Vista deserves the bad reputation. But why?

I love Vista and have had no major problems with it, even on my 5-year-old home desktop that only had 1 GB RAM. Things run just as fast as in XP, I had no driver problems, the sidebar is awesome (with the right gadgets), it’s pretty, the sleep mode is awesome – it lets me turn off the computer in a few seconds and it boots right back up in less than 5 seconds, and more. There are a lot of great things in Vista.

Sure, there are also a few bad things like the annoying security dialogs that pop up (which I turned off) and its cost. The most common complaint I hear is that it consumes more resources than XP. Big deal. It’s a next-generation OS that was actually design to use that extra memory very efficiently. Why shouldn’t Microsoft design for the ever-increasing, ever-cheaper amount of memory that comes in computers nowadays?

Given its strengths and improvements over XP, I don’t think these things validate the “suck” label.[/ben61a]

. . .

This week, a number of tech journalists gave glowing reviews of Leopard. They received the software on Mac Book Pro laptops provided by Apple. Nowhere have I seen anyone gripe about conflicts of interest. But when Microsoft’s PR agency sent bloggers preloaded Vista notebooks ahead of the operating system’s launch, there were ridiculous accusations of attempted bribery. The accusations made it difficult for those receiving the Vista units to say anything positive about the operating system.

[ben61a] Hahahahahaha TOTALLY. I saw like 5 articles about how Microsoft was bribing people with awesome laptops with Vista installed. IMO, this is the best example of the media and bloggers’ double-standard.[/ben61a]

. . .

Apple is perceived to be a progressive company. But it has a spotty record for green computing—even though one of its board members just won a Nobel prize for environmental work. Its record of giving is OK, but not exceptional. Apple has few programs (actually none that I know of) for helping people in emerging markets. Oh, but it’s cool, though, and has style.

By contrast, Microsoft’s focus for years has been the conversion to digital documents, which is hugely environmentally friendly. The company’s chairman is trustee for a charitable organization with billions of dollars to give away. Microsoft’s Unlimited Potential program seeks to use technology to empower people in emerging markets.

[ben61a] Beyond this, Microsoft also matches employee charitable giving dollar-for-dollar up to $12,000 per year. Last year alone, Microsoft and its employees gave $39.2 million in cash through our Employee Giving Campaign. That’s a big deal! I’m guessing that if one year, Apple or Google employees gave that much through a company-sponsored program, it’d be all over the media. Microsoft has been doing it for YEARS. Since 1983, Microsoft + employees have given $2.5 billion in cash, services, and software to non-profits around the world. Isn’t that weird for an “evil empire?”[/ben61a]

There’s perception, and there’s reality.

No question, Microsoft makes lots of boneheaded decisions, for which it is rightly vilified. But the company also deserves more praise than it gets. Meanwhile, strong brand perceptions—and their feel good association—lets Apple off even when it screws up.

Today will be no exception. The blogosphere will praise Leopard as the next best thing ever and use it as more proof why Vista sucks (It doesn’t). Meanwhile, there will be little good said about Microsoft’s colossal 2008 fiscal first quarter results. Those people acknowledging the earnings results will blame Microsoft for trying to kill Linux and babies in Africa as reasons for its success. The perception: When Microsoft competes, it cheats.

There is a double standard.

http://www.microsoft-watch.com/content/operating_systems/the_great_double_standard.html