Monthly Archives: August 2011

Abstraction and MagicStove Beta

This is a continuation of the project I first discussed in: How Many Hill Giants?

While I’ve been programming my experimental husk of what Magic is for the purposes of my Hill Giant question, there has been a recurring abstraction question:  what is a player?  The definition of a player is different depending on who you ask.  To WotC and perhaps tournament organizers, a player is a consumer.  To the head judge and the DCI, a player is a rating, a set of qualifications, a history of warnings.  To the unseen force that propels a game forward (which I refer to as a Game), a player is an agent of change within a continually progressing system.  Thus, we have a notion of the variable scope that a player can exist in.

For the purposes of the Hill Giant problem, a player consists of the following:

  • a deck
  • lands in hand
  • creatures in hand
  • untapped lands
  • tapped lands
  • untapped creatures
  • tapped creatures
  • life total
  • player name

The implementation of this was not difficult, but navigating a player through the different levels of the experiment’s abstraction has proved cumbersome.  The objective of the project is to be able to run vastly different tests based on the simple alteration of several global variables; a basic design pattern.  But the responsibility of data crunching is passed between different aspects of the program, and at some points the buck must be passed while the passer maintains a copy of the buck he is passing, lest its integrity be lost.  For example, one bug that had to be ironed out recently had to do with the necessity of copying the original player object, whose deck had 50 Hill Giants, the starting number.  If he wasn’t copied before the buck was passed, the passed deck would be mutated by the fact that, during Magic, a player draws spell cards, putting them in a different zone.  This would make it impossible to tell the starting contents of a match iteration’s decklists, and therefore make it impossible to gather stats on different overall decklists, muddling the entire experiment.

Not only do I have to maintain a clone as I pass a player from the main method to the match, but also as I pass him from the match to each game within it.  Which brings me to a more recent problem:

Turn: 3; Active player: Clarence

Clarence has 9 untapped lands and 9 untapped creatures.

Clarence draws Grey Ogre*. Clarence has 2 lands in hand and 13 Grey Ogres in hand.

Clarence plays a land.

Clarence plays 3 dude(s).

Clarence attacks with 9 Grey Ogres

Danielle blocks with 2 Grey Ogres.

2 trades occur and Danielle takes 14 damage.

End turn. Clarence is at 20 /// Danielle is at -6

Clarence draws land. Clarence has 2 lands in hand and 13 Grey Ogres in hand.

Clarence draws Grey Ogre. Clarence has 2 lands in hand and 14 Grey Ogres in hand.

*The change from Hill Giants to Grey Ogres occurred during a code refactoring courtesy of Andrew Gray.  GreyOgre extends Card, the abstract class he created to encapsulate card data such as power, toughness, and casting cost, which I was putting in the deck class.

From this transcript, it’s not difficult to understand that something is wrong with the program.  The players’ life total fails to reset after each game and their hands and the board stays the same–and it’s pretty pointless to play a game of Magic in which your opponent can play three Grey Ogres on turn three while you start at less than one life.

My first thought was that it had to do with the player object I was pointing to within the game affecting variables that should only have been in the scope of the match, which would mean I hadn’t cloned the players properly into the game during each iteration of the match’s for loop.  This is a problem that would prevent the players from being adequately refreshed.  But as Andrew pointed out while looking at the code, we hadn’t put “creaturesInHand- -;” under the playCreatures() method.  This allowed a player to play as many Grey Ogres a turn as he wanted to as long as he had one Grey Ogre in his hand, because deploying a Grey Ogre did not actually cause a Grey Ogre to leave your hand.  This also explains why Clarence is holding 13 Grey Ogres at one point.  The bug was solved when Andrew and I were running early tests and noticed an inordinate number of games being won by the deck with 1 Grey Ogre and 99 Mountains–10%.

But that doesn’t solve the question as to why the life totals weren’t replenishing after the game.  Andrew noted that it was probably negative damage being dealt somehow.  I confirmed this when I noticed a game in which a player attacked with 2 Ogres and the opponent blocked with 3.  After that, the output read that defending player had gained 2 life during the exchange.  This required a minor change in combat logic, which is in the Player class within his attack(creaturesWithoutSummoningSickness, defendingPlayer) method.  There was also a bug that was letting players continue living despite being at negative life, under some circumstances.  I cleaned that up at some point.

When we started abstracting away the game state details and looking at the match-up percentages themselves, Andrew and I eventually had some decisive results, which I give an example of below.  The data in the first column represents Clarence’s starting count of Hill Giants within his deck for each game that he plays during a 65,000 game series.  The difference between that and 100 is the number of Mountains Clarence plays (which would be 80 for the first row).  The second column is Clarence’s win percentage vs. the field and the third column is his loss percentage vs the field.

The field consists of lists with 20-85 Hill Giants and vs. each of those opponents 1000 games were played.  When Andrew and I were at the cusp of getting numerical results, he argued that playing matches actually adds variance and abstracts away a degree of statistical accuracy, so we effectively abandoned them (although there are always sideboarding experiments to be had).  This was convenient since we were still having logical issues with the way a match was an abstracted set of games.  Finally, the optimum creature count vs. a random deck from the defined field is listed at the bottom of these stats.  And with that, the program I have dubbed MagicStove has “solved” its first problem:

20|27.138462|72.86154

21|28.504616|71.495384

22|29.869232|70.13077

23|31.269232|68.730774

24|33.104618|66.895386

25|34.635387|65.36462

26|36.072308|63.927692

27|37.54154|62.45846

28|39.226154|60.77384

29|40.65231|59.347694

30|42.353848|57.646156

31|44.352306|55.647694

32|45.59077|54.40923

33|47.253845|52.746155

34|48.99231|51.007694

35|50.32461|49.675385

36|52.169235|47.83077

37|53.460003|46.54

38|55.4|44.600002

39|56.40154|43.59846

40|58.69077|41.30923

41|59.53231|40.46769

42|60.567696|39.43231

43|61.875385|38.124615

44|62.84769|37.15231

45|64.44769|35.552307

46|65.23692|34.763077

47|66.14923|33.85077

48|66.98615|33.013847

49|67.886154|32.113846

50|68.1723|31.827692

51|68.56308|31.436924

52|69.16462|30.835384

53|69.48615|30.513847

54|69.34154|30.658463

55|69.566154|30.433846

56|69.51538|30.484617

57|68.67385|31.326155

58|68.41692|31.583076

59|68.02462|31.975386

60|66.86|33.14

61|65.80308|34.196922

62|64.91692|35.083076

63|63.70923|36.290768

64|61.961536|38.038464

65|60.684616|39.315384

66|58.960003|41.04

67|57.01077|42.98923

68|55.344616|44.655384

69|53.267693|46.732307

70|50.566154|49.433846

71|48.075382|51.924618

72|45.552307|54.447693

73|43.563076|56.43692

74|40.301537|59.698463

75|37.43077|62.56923

76|34.92154|65.07846

77|32.270767|67.729225

78|29.284615|70.715385

79|26.533846|73.46615

80|23.703077|76.29693

81|21.263077|78.73692

82|18.747692|81.252304

83|16.136923|83.86308

84|13.698462|86.301544

The optimum creature count for HillGiant: 55

Total time: 34830ms

 

 

Basic Magic AI: How Many Hill Giants?

Andrew and I recently had a debate.  In a 100 card minimum deck size format with Mountain, Hill Giant, and no other cards, how many Hill Giants would be correct if there is no limit to how many you can play (the Relentless Rats mechanic)?  I decided to write a crude program to “solve” it, leaving modularity to run similar experiments if I so chose.  At this point, the program’s classes are defined and it will run, but will take some debugging to produce meaningful results.  Since the fickleness of my interests sometimes lead to unfinished projects such as this, I want to at least outline my program in English while I am in the thick of it.

I start off both players with 50 Hill Giant and 50 Mountain, and give them both the same simple set of parameters to produce plays that are strategically sound enough to simulate reality.

  • There are no mulligans.  This won’t be logically difficult to implement later on, but it will be a bit time consuming given the way I have implemented the program so far.  I realize it is a crucial element, but I need to keep the horse before the carriage if I ever want to get decisive results at all.
  • There is no discard step.  I guess this hedges against the lack of mulligans a bit.
  • First game of each match is decided randomly.  If you lose a game within a match, you always play first the next game.
  • If you have a land you must play it.
  • You must play as many Hill Giants in your precombat main phase as possible.
  • If you have more life than an opponent, you must attack with all of your Hill Giants every turn.
  • If you have less life than your opponent, you must attack with X Hill Giants every turn, where X is the number of Hill Giants you control minus the number of total Hill Giants your opponent controls.
  • Defending player must block as many Hill Giants as he can every turn.

This may seem like a watered-down form of Magic, but I think its combative interaction encourages attrition wars, which I think is the best way to delay a game for as long as possible and give the decks a chance to expose as many cards as possible and maximize the match’s turn sample size.  I’m not saying this is the best set of rules that will promote attrition, but it is a set nonetheless, and one that I think captures some basic methodical heuristics perhaps practiced by middle schoolers playing Magic on a cafeteria lunch table.  As a caveat, there might be attacking strategies that include swinging out every turn despite being at lower life than your opponent, perhaps based on your deck proportions vs. average proportions (or specific proportions, if I was to give the players each others’ decklists).

Every match consists of a variable number of games.  Once the program is debugged it will be easy to run tests for decks with Grizzly Bears, Norwood Ranger, Scathe Zombies, Trained Orgg, and any number of vanilla favorites from throughout Magic’s history.  I will also be able to change the amount of games per match and the starting life totals, and make deck size as big as I want, so there can be a finer gradation for decklist changes, since taking one Hill Giant out of a deck with 50 Hill Giant and 50 Mountain is different than taking one Hill Giant out of a deck with 100 of each.

One thing that’s difficult is deciding how to make decklist changes.  Although I can’t get WordPress to format it in a less-than-hideous fashion, here is one way I could do it:

Random rand = new Random();

if(winsAlice > winsBob){

if(rand.nextBoolean())

Alice.makeChanges(NUM_CHANGES, “land”);

else

Alice.makeChanges(NUM_CHANGES, “creature”);

}

else{

if(rand.nextBoolean())

Bob.makeChanges(NUM_CHANGES, “land”);

else

Bob.makeChanges(NUM_CHANGES, “creature”);

}

NUM_CHANGES is a global variable defined before the main method to indicate the number of changes that will be made after each match.  If NUM_GAMES is 5, and Bob wins a 5 game match, Bob will make NUM_CHANGES changes to his deck before the next match, which will all be in the same direction (more lands or more creatures).  With the above methodology, the deck change would be completely random.  This should still drive deck construction in the proper direction in the long term as long as NUM_CHANGES is a reasonably small percentage of overall deck size.  The program runs for NUM_MATCHES.

To be frank, as interested as I am in this problem, I’m pessimistic about getting decisive results.  I have a suspicion that metagame will damn this entire exercise since deck strength is completely relative.  This is something I don’t know how to deal with, but perhaps I can graph it.  I’ll need to really show my programming chops to get anywhere.  As a gauge to show where I’m at right now, here is some sample output to show where I am at bug-wise:

Turn 0: Bob has 0 Hill Giants

Bob has 3 lands in hand and 5 Hill Giants in hand.

After playing permanents, Bob has 1 lands and 0 Hill Giants

Bob is at 20

Alice is at 20

 

Turn 1: Alice has 0 Hill Giants

Alice has 4 lands in hand and 3 Hill Giants in hand.

After playing permanents, Alice has 1 lands and 0 Hill Giants

Alice is at 20

Bob is at 20

 

Turn 2: Bob has 0 Hill Giants

Bob has 3 lands in hand and 5 Hill Giants in hand.

After playing permanents, Bob has 2 lands and 0 Hill Giants

Bob is at 20

Alice is at 20

 

Turn 3: Alice has 0 Hill Giants

Alice has 4 lands in hand and 3 Hill Giants in hand.

After playing permanents, Alice has 2 lands and 0 Hill Giants

Alice is at 20

Bob is at 20

 

Turn 4: Bob has 0 Hill Giants

Bob has 2 lands in hand and 6 Hill Giants in hand.

After playing permanents, Bob has 3 lands and 0 Hill Giants

Bob is at 20

Alice is at 20

 

Turn 5: Alice has 0 Hill Giants

Alice has 4 lands in hand and 3 Hill Giants in hand.

After playing permanents, Alice has 3 lands and 0 Hill Giants

Alice is at 20

Bob is at 20

 

Turn 6: Bob has 0 Hill Giants

Bob has 1 lands in hand and 7 Hill Giants in hand.

After playing permanents, Bob has 4 lands and 1 Hill Giants

Bob attacks with 0 Hill Giants.

Alice blocks with 0 Hill Giants.

0 trades occur and Alice takes 0 damage.

Bob is at 20

Alice is at 20

 

Turn 7: Alice has 0 Hill Giants

Alice has 4 lands in hand and 3 Hill Giants in hand.

After playing permanents, Alice has 4 lands and 1 Hill Giants

Alice is at 20

Bob is at 20

 

Turn 8: Bob has 1 Hill Giants

Bob has 0 lands in hand and 8 Hill Giants in hand.

After playing permanents, Bob has 4 lands and 2 Hill Giants

Bob attacks with 1 Hill Giants.

Alice blocks with 1 Hill Giants.

1 trades occur and Alice takes 0 damage.

Bob is at 20

Alice is at 20

…etc

Turn 33: Alice has 5 Hill Giants

Alice has 0 lands in hand and 10 Hill Giants in hand.

After playing permanents, Alice has 13 lands and 8 Hill Giants

Alice attacks with 5 Hill Giants

-1

Alice attacks with 2 Hill Giants.

Bob blocks with 3 Hill Giants.

3 trades occur and Bob takes 6 damage.

Alice is at 20

Bob is at 20

 

—————————————————————

Bob wins! His deck contained 46 Hill Giant