Monday, June 16, 2014

The Legacy of GOAL

GOAL was a programming environment created by the incredibly smart co-founder of Naughty Dog -- Andy Gavin -- for the PlayStation 2 generation. It was never released to the public, hence only rumors of its greatness has trickled into the general game development scene.

Why was GOAL so awesome?


There is no doubt about it, GOAL was simply awesome. But why?

In my opinion it was due to one single idea: Interactivity. Think about it: These days we revel in the idea of hot-loading assets, changing shaders on the fly, and interacting via scripting languages such as Lua and advanced level editors. What if your whole engine was interactive. Not just parts of it, but all of it.

The Listener


Let us think about what interactivity for your entire (run-time) code-base entails. First, we need a method for adding/removing code and data on our target machine where the game is currently running. That means that the game will have to run code at a dedicated safe-point that can patch the memory that holds code and static data. It also needs a mechanism to make use of the new code/data, so it needs to patch calls to functions and reads of global data. Now, the target (the game) is often resource constrained, so it is vital that the target code for this is compact. We don't want to implement a linker or a JIT-compiler on the target. But what we will need is a listener on the target that can receive code, execute allocation and deletion of code and patch in calls to new code. Since this will also be part of the debugging infrastructure, it will also be convenient to be able to inspect data, i.e. be able to respond to debugging commands sent from outside the game. So, the listener is a (thin) server that runs on the target. 

The Linker


Given that the listener is supposed to be a thin server, something else needs to know where code and static data is on the target. This is typically done by a linker, but a linker is not a server. It also does not know how to change code on the fly. So, what is needed is a linker service. We could certainly do that, but it turns out that the linker has an almost trivial task. Most of the complexity for a linker is due to things like linker scripts and arcane file formats. If you distill the essence of a linker it is almost trivial. It is a data-base of names to real addresses. It takes "object files" that contain code and static data (along with some meta-information) and produces and actual executable where all names have been resolved into final addresses. We are going to need this information at a higher level, so it makes sense to make the linker an integrated component of the system.

The Debugger


Most debuggers (like e.g. gdb) are written as a stand-alone system. The big flaw with it is that the debugger needs to execute code. If I have an array of 10,000 structures, I don't want to inspect it by clicking on the array and manually search for the structure that has the name 'crate-b-01'. Instead, I'd like to execute some kind of code to find it for me. Some debuggers support scripting languages for these tasks, but that just introduces yet another language to our system. Why not implement the debugger as an extension of the language itself? After all, we are creating the one-and-only language we need. An we have everything we need, we have a listener on the target that can execute any commands that we send it. For more advanced queries, we can do it in two ways. We either compile the debugging code (our search function) on the host, boiling down the result into commands to be executed on the listener, or we compile the debugging code into code that is to be executed on the target. We might need both, for the cases where the game or the listener crashes on the target.

The Dependency Manager


When programmers talk about interactivity, they often refer to the "REPL". The REPL is basically a command line system where you can write code and have the compiler interpret (or compile) the code, execute it and then give back control to the command line. 

While this is powerful, that's not really what we want. We want to be able to create or change some code in our project, hit a key (or click button) in our favorite editor and have the system magically compile all changed code, send the deltas to the listener and let it update the code on the target to reflect our changes. In order for this to be possible, we need detailed knowledge of dependencies within the entire code base.

This means that "make" won't be enough, instead it has to be a crucial component of our system.

The Language


It is interesting that syntax of the actual language that we use is not that important. However, given our environment there are some rather important restrictions that has to be considered.

First, in order to have an interactive experience we must avoid anything like C/C++'s #include system. Instead, the compiler will need to support a module system. Each source file corresponds to a module, so that every function (and static data) name at the source file level is scoped uniquely. Type information, exported names and dependencies needs to be cached by the compiler in order to facilitate code patches as quickly as possible. The Go language definitely has the right approach here.

Second, since we want to be able to use the language as part of the debugger, we probably want to be able to reason about types and other meta-data. It might also be useful to execute code on the host during compilation, in other words - macros. If we do support macros and a debugger language, the language should be very similar to the target language. Lisp languages do this automatically, but there are other solutions in languages with syntax.

GOAL


What I have described above isn't just possible, it has already been done. Andy's system was not just a compiler. It was also a linker, a debugger, a dependency manager and a macro expander, but more importantly -- it was a server. This is so fundamentally important. If you are going to change code on the fly, something needs to know "everything", and the compiler knew everything. It was live, so you could get access to everything, results of macros, memory on the target. 

GOAL's source language was very simple. Much simpler than Lisp, C/C++, Rust etc. There was not a lot of features, not much of functional programming (it was imperative). As a matter of fact, it was basically an assembly language compiler with register coloring. It used Lisp macro system to make things easier for the developer, and it had little of type-checking. But even without the more advanced features of other languages it was a beautiful system, because it was interactive and immediate. It still happens to be the best programming environment for games programming I have ever seen.

Tuesday, April 15, 2014

Mana Requirements for Gold Cards

Anyone having tried to cast Rakdos, Lord of Riots or other guild leaders in Return to Ravnica draft know that it is quite unlikely to be able to cast them on turn 4. Why (besides the Lord's additional restriction) is this?

In a 40-card draft deck with 17 basic lands, you are quite likely to only have 4 lands by turn 4. Assuming 4 lands, we need to turn to the hyper-geometry distribution to find out the likely-hood of having exactly two basics of type A and two of type B. Let #A = 9 and #B = 8:

chance_4 = H([9, 8], [2, 2]) = C(9, 2) C(8,2) / C(9+8, 2+2) = 42.35%

In other words, you are more likely to have the wrong colors. Even if you draw 5 lands by turn 4, you often fail to be able to cast your favorite guild leader:

chance_5 = H([9, 8], [2, 3]) + H([9, 8], [3, 2]) = 70.59%,

so three games out of ten you will fail. We call this condition "color-screw", i.e., you have enough lands to cast your spell, but they produce the wrong colors.

You might object and say that you would always draft dual-lands. How much better is the situation if we add lands capable of producing either mana? Again, turning to math, we will find [*]:

One dual land, L = [8,8,1], H(L, [2,2,0]) + H(L, [2,1,1]) + H(L, [1,2,1]) = 51.76%
Two dual lands, L = [8,7,2], H(L, [2,2,0]) + ... + H(L, [0, 2, 2]) = 59.71%
Three dual lands, L = [7,7,3], H(L, [2,2,0]) + ... + H(L, [0, 1, 3]) = 67.66%
Four dual lands, L = [7,6,4], H(L, [2,2,0]) + ... + H(L, [0, 0, 4]) = 73.95%

As you can see, even by drafting 4 red/black dual lands, there is still a significant chance (one out of four games), that we can't play the guild-leader. How many do we need to reach 90%, so that we are color-screwed only once every ten games? The answer is a whopping 8 duals (though 7 duals is close; 89.50%).

With 5 available lands, our chances improve somewhat:

0 duals = 70.59%
1 dual  = 77.83%
2 duals = 82.92%
3 duals = 88.01%
4 duals = 91.24%

By putting all of these calculations in a program, we can additionally take into account mulligans due to land-count problems, as well as the likelihoods of drawing exactly 4, 5, etc. lands by turn 4. We can also consider other spells, such as AB-spells (charms), 1AB-spells, nAAB-spells, and nAABB-spells. Combining all of this, we get the following table for hitting the 90% color success rate (top left indicates 17 lands in a 40-card deck, 0 out of the 17 are off-colored lands):

17/40(0)    --    1    2    3    4    5    6    7
       AB    4    -    -    -    -    -    -    -
      AAB    5    3    1    -    -    -    -    -
     AAAB    5    3    2    -    -    -    -    -
     AABB    6    3    -    -    -    -    -    -
    AAAAB    4    3    1    1    -    -    -    -
    AAABB    6    3    1    -    -    -    -    -

Going back to our example (AABB), we see that 6 dual lands is required, which makes sense since drawing 4 or 5 lands by turn 4 is far more likely than drawing 6, 7, 8, 9 or 10 lands. (Remember, the 90% number assumes that you are not mana-screwed, i.e., you have at least 4 lands.) A card like Niv-Mizzet, Dracogenius costs 2AABB, requires no dual AB-lands, and Supreme Verdict costs 1AAB, requiring 3 dual lands.

Now, what happens if you have lands that can produce neither A nor B? Using charms as our example, we know from previous posts that to play a CC spell, we need 14 out of 17 sources of that color. Naturally, then, to play an AB spell, we need at least that many lands that produce either A or B. So, if we have 4 off-color sources, then we know that we can't reliably cast an AB spell, as seen below:

17/40(4)    --    1    2    3    4    5    6    7
       AB   **    5    2    -    -    -    -    -
      AAB   **   **    3    2    -    -    -    -
     AAAB   **   **    5    2    2    -    -    -
     AABB   **   **    6    2    1    -    -    -
    AAAAB   **   **   **    2    1    1    1    -
    AAABB   **   **   **    3    2    -    -    -

Here, ** indicates that you we reach the limit -- with that many off AB lands, there is more than 10% chance that we will be color-screwed, no matter how many dual-lands we have.

So, let's present the tables:

40-card decks

17/40(0)    --    1    2    3    4    5    6    7
       AB    4    -    -    -    -    -    -    -
      AAB    5    3    1    -    -    -    -    -
     AAAB    5    3    2    -    -    -    -    -
     AABB    6    3    -    -    -    -    -    -
    AAAAB    4    3    1    1    -    -    -    -
    AAABB    6    3    1    -    -    -    -    -


17/40(1)    --    1    2    3    4    5    6    7
       AB    5    1    -    -    -    -    -    -
      AAB    7    3    2    -    -    -    -    -
     AAAB   10    3    2    1    1    -    -    -
     AABB   13    4    1    -    -    -    -    -
    AAAAB   **    3    2    2    -    -    -    -
    AAABB   **    4    2    -    -    -    -    -


17/40(2)    --    1    2    3    4    5    6    7
       AB    6    3    -    -    -    -    -    -
      AAB   **    4    2    1    -    -    -    -
     AAAB   **    4    2    1    1    -    -    -
     AABB   **    6    2    -    -    -    -    -
    AAAAB   **    5    2    2    1    1    1    -
    AAABB   **    6    3    1    1    -    -    -


17/40(3)    --    1    2    3    4    5    6    7
       AB    9    4    1    -    -    -    -    -
      AAB   **    6    3    1    -    -    -    -
     AAAB   **   **    3    1    1    -    -    -
     AABB   **   **    4    1    -    -    -    -
    AAAAB   **   **    3    2    1    1    1    -
    AAABB   **   **    4    2    1    -    -    -


17/40(4)    --    1    2    3    4    5    6    7
       AB   **    5    2    -    -    -    -    -
      AAB   **   **    3    2    -    -    -    -
     AAAB   **   **    5    2    2    -    -    -
     AABB   **   **    6    2    1    -    -    -
    AAAAB   **   **   **    2    1    1    1    -
    AAABB   **   **   **    3    2    -    -    -

60-card deck

24/60(0)    --    1    2    3    4    5    6    7
       AB    6    2    -    -    -    -    -    -
      AAB    7    4    1    -    -    -    -    -
     AAAB    8    4    2    1    -    -    -    -
     AABB    9    5    1    -    -    -    -    -
    AAAAB    7    3    2    1    1    -    -    -
    AAABB    8    5    2    -    -    -    -    -


24/60(1)    --    1    2    3    4    5    6    7
       AB    7    3    -    -    -    -    -    -
      AAB   10    4    1    -    -    -    -    -
     AAAB   11    5    2    1    -    -    -    -
     AABB   13    6    2    -    -    -    -    -
    AAAAB   **    4    2    1    1    -    -    -
    AAABB   **    6    3    -    -    -    -    -


24/60(2)    --    1    2    3    4    5    6    7
       AB    9    4    -    -    -    -    -    -
      AAB   14    5    2    -    -    -    -    -
     AAAB   **    6    3    1    -    -    -    -
     AABB   **    7    3    1    -    -    -    -
    AAAAB   **    6    3    1    1    -    -    -
    AAABB   **    8    4    1    -    -    -    -


24/60(3)    --    1    2    3    4    5    6    7
       AB   11    5    1    -    -    -    -    -
      AAB   **    7    3    1    -    -    -    -
     AAAB   **    8    4    2    -    -    -    -
     AABB   **   10    4    2    -    -    -    -
    AAAAB   **   11    4    2    2    -    -    -
    AAABB   **   13    5    2    -    -    -    -


24/60(4)    --    1    2    3    4    5    6    7
       AB   15    6    2    -    -    -    -    -
      AAB   **    9    4    1    -    -    -    -
     AAAB   **   **    5    2    1    1    -    -
     AABB   **   **    6    3    -    -    -    -
    AAAAB   **   **    5    3    2    1    1    1
    AAABB   **   **    7    3    1    -    -    -

-------------------------------------------------------

25/60(0)    --    1    2    3    4    5    6    7
       AB    6    1    -    -    -    -    -    -
      AAB    8    3    1    -    -    -    -    -
     AAAB    8    4    2    -    -    -    -    -
     AABB    9    5    2    -    -    -    -    -
    AAAAB    7    4    2    2    1    1    -    -
    AAABB    9    5    2    -    -    -    -    -


25/60(1)    --    1    2    3    4    5    6    7
       AB    7    2    -    -    -    -    -    -
      AAB   10    4    2    -    -    -    -    -
     AAAB   12    5    2    1    1    -    -    -
     AABB   13    6    3    -    -    -    -    -
    AAAAB   **    5    2    2    1    1    -    -
    AAABB   **    6    3    1    -    -    -    -


25/60(2)    --    1    2    3    4    5    6    7
       AB    8    3    -    -    -    -    -    -
      AAB   13    6    3    -    -    -    -    -
     AAAB   **    6    3    1    1    -    -    -
     AABB   **    7    4    -    -    -    -    -
    AAAAB   **    6    3    2    1    1    -    -
    AAABB   **    8    4    2    -    -    -    -


25/60(3)    --    1    2    3    4    5    6    7
       AB   10    5    1    -    -    -    -    -
      AAB   **    7    3    1    -    -    -    -
     AAAB   **    8    4    2    1    -    -    -
     AABB   **    9    5    1    -    -    -    -
    AAAAB   **   11    4    3    1    1    -    -
    AAABB   **   11    5    3    1    -    -    -


25/60(4)    --    1    2    3    4    5    6    7
       AB   13    6    2    -    -    -    -    -
      AAB   **    8    4    2    -    -    -    -
     AAAB   **   13    5    3    2    -    -    -
     AABB   **   15    6    2    -    -    -    -
    AAAAB   **   **    5    3    2    2    -    -
    AAABB   **   **    7    3    2    -    -    -

-------------------------------------------------------

26/60(0)    --    1    2    3    4    5    6    7
       AB    5    1    -    -    -    -    -    -
      AAB    7    4    1    -    -    -    -    -
     AAAB    8    4    2    1    -    -    -    -
     AABB    9    5    1    -    -    -    -    -
    AAAAB    7    4    3    2    -    -    -    -
    AAABB    9    5    2    -    -    -    -    -


26/60(1)    --    1    2    3    4    5    6    7
       AB    7    2    -    -    -    -    -    -
      AAB    9    5    2    -    -    -    -    -
     AAAB   11    5    3    2    -    -    -    -
     AABB   12    6    2    -    -    -    -    -
    AAAAB   15    5    3    2    1    1    -    -
    AAABB   16    6    3    1    -    -    -    -


26/60(2)    --    1    2    3    4    5    6    7
       AB    8    3    -    -    -    -    -    -
      AAB   12    5    2    1    -    -    -    -
     AAAB   **    6    3    2    1    -    -    -
     AABB   **    7    3    1    -    -    -    -
    AAAAB   **    6    3    2    1    1    -    -
    AAABB   **    8    4    1    -    -    -    -


26/60(3)    --    1    2    3    4    5    6    7
       AB   10    4    -    -    -    -    -    -
      AAB   **    6    3    1    -    -    -    -
     AAAB   **    8    4    2    1    -    -    -
     AABB   **    9    4    2    -    -    -    -
    AAAAB   **    9    4    2    1    1    -    -
    AAABB   **   11    5    2    -    -    -    -


26/60(4)    --    1    2    3    4    5    6    7
       AB   12    5    1    -    -    -    -    -
      AAB   **    8    4    2    -    -    -    -
     AAAB   **   11    5    3    1    -    -    -
     AABB   **   13    5    3    -    -    -    -
    AAAAB   **   **    5    3    1    1    -    -
    AAABB   **   **    6    3    1    -    -    -


Conclusion

What can we conclude from these? 

The first is that in constructed, that being able to cast charms on turn 2 is hard, requiring 12-16 dual lands with just 4 off-colored lands. The same goes for 1AAB spells (like e.g. Supreme Verdict), requiring 8 dual lands. 1AB spells, however are not that hard to cast, often requiring only 4 dual lands. 

In sealed and draft, it tells us that AB spells (charms) are quite hard to cast on turn 2 due to the unlikely hood of having dual-lands. 1AB spells are okay if you have two dual lands, while 2AB spells require none. Finally that AABB and 1AABB are near impossible to cast on time, so they should be avoided.


[*] For the mathematically inclined, the sum is:

SUM_(a, b, d) H(L, [a,b,d]), where (a,b,d) is all combinations such that we can cast AABB, i.e.: a + b + d = 4, d >= 2 or else a+d >= 2 and b+d >= 2.

Monday, March 24, 2014

Further Examination of Karsten Frank's Analysis

In the previous post, as well as in Karsten Frank's analysis, there is a subtle nuance that we have to touch upon. In both his article and in my initial post we assumed that we can read off the table the number of lands that is required for a spell like Anger of the Gods by looking at double-casting spells on turn 3. But, the table doesn't show that -- it shows the number of colored lands required for casting a CC spell on turn 3, assuming we have enough lands (i.e. 2 lands on turn 3). This is not the same!

It turns out that casting a 1CC spell on turn 3 requires less colored sources than casting a CC spell on turn 3. This sounds absolutely crazy at first, but remember the first assumption, that we have enough lands to cast them in the first place. Consider for a second, that we want 0% color-failure in a 24-land 60-card deck. To have no color failures on turn 2 means that we need to have 24 colored mana. On turn 3, you might think that we can allow non-colored mana, but that is wrong since we are comparing against the chance of having enough lands and that includes the chance of having only 2 lands on turn 3 - in which case there is a non-zero chance that one of them is the off-colored mana source. 

In other words, the pre-condition "have enough lands to be able to cast the spell" over-inflates the colored-land tables that we have presented, and it may be more useful to make a table consisting of the required number of lands in order to avoid color-failures for each of the consecutive spells. So, for instance, a table comprising C, 1C, 2C, 3C, 4C, 5C and 6C for single-colored spells and a table CC, 1CC, 2CC, 3CC, 4CC, 5CC for double-colored spells and so on, given at the first turn you can cast them:

Spell TypeC1C2C3C4C5C6C
90.00%1413119876
As you can see, this is quite different from the previous table. For double-colored spells:

Spell Type-CC1CC2CC3CC4CC5CC
90.00%-201715131110

And finally for triple-colored spells

Spell Type--CCC1CCC2CCC3CCC4CCC
90.00%--2219171513

From this, we can revise our numbers for Anger of the Gods, which requires 17 out of 24 red sources, and Cryptic Command that requires 19 blue sources out of 24.

For completeness, here's a few variations:

------------------------------------------------

16/40    --    1    2    3    4    5    6    7
     C    9    8    7    6    5    4    4    3
    CC   13   12   10    9    7    7    6    5
   CCC   15   13   11   10    9    8    7    6
  CCCC   16   14   12   11   10    9    8    7


17/40    --    1    2    3    4    5    6    7
     C   10    9    7    6    5    5    4    4
    CC   14   12   10    9    8    7    6    5
   CCC   16   14   12   11    9    8    8    7
  CCCC   16   15   13   12   10    9    9    8


18/40    --    1    2    3    4    5    6    7
     C   10    9    8    7    6    5    4    4
    CC   14   12   11    9    8    7    7    6
   CCC   16   14   13   11   10    9    8    7
  CCCC   17   15   14   12   11   10    9    8

------------------------------------------------

22/60    --    1    2    3    4    5    6    7
     C   13   12   10    9    7    6    6    5
    CC   19   16   14   12   10    9    8    7
   CCC   21   18   16   14   12   11   10    9
  CCCC   21   19   17   15   14   12   11   10


23/60    --    1    2    3    4    5    6    7
     C   14   12   10    9    8    7    6    5
    CC   20   17   14   12   11   10    9    8
   CCC   22   19   16   15   13   12   10   10
  CCCC   22   20   18   16   14   13   12   11


24/60    --    1    2    3    4    5    6    7
     C   14   13   11    9    8    7    6    5
    CC   20   17   15   13   11   10    9    8
   CCC   22   19   17   15   13   12   11   10
  CCCC   23   21   18   17   15   14   12   11


25/60    --    1    2    3    4    5    6    7
     C   14   13   11    9    8    7    6    6
    CC   21   18   15   13   12   10    9    8
   CCC   23   20   18   16   14   13   11   10
  CCCC   24   21   19   17   16   14   13   12


26/60    --    1    2    3    4    5    6    7
     C   15   13   11   10    8    7    7    6
    CC   21   18   16   14   12   11   10    9
   CCC   24   21   18   16   15   13   12   11
  CCCC   25   22   20   18   16   15   13   12

------------------------------------------------

Thursday, March 6, 2014

Further Analysis of Karsten Frank's Mana Consistency

Karsten Frank published a very nice article at Channel Fireball that looked into the question of how many colored mana-sources you need in order to cast a spell or creature.

I thought it would be nice to analyze Karsten Frank's results with my own analysis program. While Karsten programmed a simulation, I have programmed a set of routines that could easily be adapted to his prerequisites. In other words, I'm making use of the hypergeometric distribution function.

First, the numbers I present are all assumed for being on the play, not on the draw. The reason for that is that it is harder to successfully cast spells when you have one less draw step. Second, the "90%" rule refers to the chance of being able to cast your spell, given that you have enough lands in the first place. Third, I will focus on 60-card constructed decks. And finally, he assumed a fixed land count, but in later in this blog I will explore the effects of varying the number of lands in your deck.

But, what if I feel that 90% is too conservative?


A question often asked has been, what happens if you tighten or relax the 90% rule? 90% seems arbitrary, but it is a fairly good number to aim for. It means that 9 out of 10 games, you will not be in the situation where you have the lands to play a spell, but have the wrong colors to cast them.

Spells with a single colored mana:


For the case of hitting a single mana, the table is as follows (the percentages corresponds to $19/20, 9/10, 7/8, 6/7, 5/6$ and $4/5$):

Req\Turn 1 2 3 4 5 6 7
95.00% 16 15 14 13 12 12 11
90.00% 14 13 12 11 10 9 9
87.50% 13 12 11 10 9 9 8
85.71% 12 11 10 9 9 8 8
83.33% 11 10 10 9 8 8 7
80.00% 11 10 9 8 7 7 6

As you can see from this, normally, in order to cast Thoughtseize on turn 1 with the 90% rule, you would have to have 14 sources of black. What this table tells you is that if you want to have that black mana source in 19 games out of 20 (95%), then you better have 16 sources.

Conversely, if you are okay with having no black mana on turn 1 in 1 out of every 5 games, then you may go down to 11 black sources, and even lower if you expect to cast it on later turns.

Spells with double-colored mana:


For double-mana spells we get

Req\Turn1234567
95.00%-222120191817
90.00%-201918161514
87.50%-191817161514
85.71%-191716151413
83.33%-181716141313
80.00%-171615141412

Again, we see that in order to cast Anger of the Gods reliably on turn 3, we need at least 19 sources. If we skimp to 16 red sources then 1 out of every 5 games where we have 3 lands in play, we will not have enough red mana to cast it.

Conversely, if you can fit 21 red sources in your deck, then we will be color screwed only once every 20 games.

Spells with triple-colored mana:


For triple-mana spells such as Boros Reckoner or Cryptic Command, we get

Req\Turn1234567
95.00%--2323222221
90.00%--2222212019
87.50%--2221201918
85.71%--2121201918
83.33%--2120191817
80.00%--2020191817

The same story as before unfolds. With 23 blue sources, you will be color-screwed only once in every 20 games, but by reducing it to 20 you are looking at that happening once every 6 games (83.33%).

Wednesday, February 24, 2010

First Post

Welcome to the blog!

This will be my little blog where I can rant about the lost art of optimization. More on that later.

Thanks,

PKE