Tag Archives: games

Ladder Scoring

I was thinking about game ladder scoring recently. I recall being frustrated at Supreme Commander for putting me lower on the ladder than someone I’ve beaten. I want a ladder algorithm that won’t allow that.

In particular, I want a ladder function l: (P × P → Z) × P → R which assigns to each player a number and satisfies the following properties [P is the set of players, Z is the integers, R is the reals; the first argument to l is the set of games played: given two players p and q, it returns how many times p has defeated q]:

  1. If g(p,q) > g(q,p) then l(g,p) > l(g,q) (if I’ve beaten you more times than you’ve beaten me, then I have a higher ladder score than you).
  2. If for all players q, g(p,q) = h(p,q) and g(q,p) = h(q,p), then l(g,p) = l(h,p) (your score doesn’t change if you haven’t played any games).

Of course, property #1 already causes problems. Let’s say p has defeated q once, q has defeated r once, and r has defeated p once; the vice-versas are zero. Then l(g,p) > l(g,q) > l(g,r) > l(g,p), which is impossible. I really had no right to be mad at Supreme Commander for ranking someone I had defeated above me; it’s impossible to avoid.

That doesn’t solve the problem though. Saying it’s unsolvable isn’t a solution… we’ve got to find the best solvable solution.

I could relax the constraint in rule #1 to be ≥ rather than >, but then the problem becomes too solvable. A plethora of trivial solutions emerges: l(g,p) = 0 for all p, l(g,p) = 0 for all p but the one person who has beaten every player more times than he has been beaten by them, etc. We need to add another property to get rid of these trivial solutions.

The ≥ constraint forces every player in a cycle to be assigned the same number. We can’t get around that. So maybe we can try to say that if you’re not in a cycle with a player, then your score is distinct from his.

I knew I put that second property in there for a reason. That, too, is impossible. Picture two cycles of size, say, 50. Pick one element p from the first cycle, q from the second. Can you change a bunch of arrows, as long as you don’t change any arrows to or from p or q to make the two cycles one big cycle? Of course you can. By our axiom, p‘s and q‘s scores were distinct, but now they’re in a cycle together, so one of them must have changed. But neither p nor q needed to play any games for that to happen. This violates our second property.

So basically you can’t even get close to the two properties I stated above. The fact is that player rankings are nothing like real numbers, so don’t try to force them in.

You can satisfy the second property without the first by summing over all players q the function f(p,q) where f is defined by:

f(p,q) = 1 if g(p,q) > g(q,p), -1 if g(p,q) < g(q,p), and 0 otherwise.

Which has the nice property that you can have many rematches without taking advantage of the scoring. But, of course, it doesn’t have the other nice properties that I want…

Abstract State Machines for Game Rule Specification

Jude has been working on the design of a general board game programming engine. We brainstormed a bit, and I remembered something I had read about a little while ago: Abstract state machines.

An ASM is really nothing more than a formalization of a simultaneous chain of if-then statements. A common example is Conway’s life: given a lattice and a countNeighbors function you could define the rules for Conway’s life as an ASM as follows:

letDie(cell, n) =
  if status(cell) = Alive and (n  3) then
    status(cell) := Dead
letLive(cell, n) =
  if status(cell) = Dead and n = 3 then
    status(cell) := Alive

gameOfLife =
  forall cell in cells do
    letDie(cell, countNeighbors(cell))
    letLive(cell, countNeighbors(cell))

e only thing this is getting us over any type of program specification is the parallelism. But the idea of a list of rules, each of which has a condition and an action, is the right level of abstraction to make a board game engine.

We have to tweak a few things to get it just right. For example, you could have must and may combinators, which specify which moves are available to the player.

Let’s look at Pente. First, we assume a linked-list style lattice, where each cell has eight pointers indexed by direction (they could be abstract or just numbers or whatever), and then a link(direction, n) function gives us the cell in a particular neighbor. Then we could specify pente something like this (Haskellesque syntax now):

move s player =
  if color s == Empty then may $ do
    color s := player
    mapM_ capture directions
  where
  capture d = do
    let oneAway = link d s
    let twoAway = link d oneAway
    let threeAway = link d twoAway
    if color oneAway == color twoAway == otherPlayer player && color threeAway == player then do $
      color oneAway := Empty
      color twoAway := Empty

There are still a few issues to solve as far as expressing “you must do either A or B, then you must do C”. I actually used very little of the ASM model (just one may combinator) in expressing pente. Okay, idea on the backburner, let’s see what else comes.

Green Globs

When I was going to Fairview High School, I spent a lot of time in the basement math annex, a computer lab for math classes which was empty most of the time (except for me and my nerdy friends). There was a game installed on that computer called Green Globs, a little math game about graphing equations. I spent many, many hours playing this addictive game, and it also gave me a nice graphical mathematical intuition.

I recently started learning Flash (w/ActionScript 3.0) because I want to start prototyping games like a madman. As a learning project I cloned this game. This is an early version, but the nice thing about Flash is that it’s really easy to polish things. So this game is tolerable even though I’ve only worked on it for a couple days.

Here’s the link: Revenge of Green Globs.

Werepoker bidding

All week I have been trying to program Werepoker and giving up after the first 20 minutes or so. I think that’s partially because it’s needlessly tough networking and threading, and partially because I know there is a high probability that the program would never be used. Well, I want to play werepoker tonight at GameDev, so I want to implement something. I think I will implement the minimal computer assistant necessary for the game to function: the bidding.

The situation: a silent auction. Everyone puts in bids for the roles they want; i.e. how much they are willing to pay for a particular role. Then we assign roles according to the bids. But there are lots of little edge cases to worry about: what to do in case of a tie, what about when someone wins two roles, etc.? The metric we will use to decide these edge cases is fairly obvious, namely to maximize the total amount everyone pays (that’s what you want to do when you’re holding an auction).

Let’s formalize this. For each player p ε P, there is a bid function bp: R -> $, where R is the set of roles, and $ is the set of nonnegative amounts of money. We’re trying to find an assignment function a: P -> R that maximizes Σpbp(a(p)).

Thanks to Daniel Crumly for pointing me at the Hungarian algorithm to solve this problem.

Hmm, the Hungarian algorithm won’t work for this problem, because it needs to be predictable by players. If you bid higher than anyone else on something, it’s still possible that you won’t get your choice depending on other bids. I’m thinking I’ll use a simple heuristic greedy algorithm.

It goes like this. Sort all bids, highest first. Give the highest bidder his wish, and remove him from the candidates. If there is a tie for the highest bidder, choose the one with the lowest secondary bid (because he is likely to pay more for a different role), or tertiary in case of a tie for that, and so on. Of course, if the bids are identical then just choose randomly.

Werepoker

The other day I was trying to think of a way that you could choose your role in Werewolf. This led me to the idea that you start people with money, and they can bid on the role they want. I mentioned this to Jude, Cami, Paul, and Travis, and Jude said that there has to be some incentive to keep the money. Travis suggested that people get paid for winning, and I took that to mean that you pay into a pot, and the pot goes to the winners at the end of the game. Obviously we’re not talking about Werewolf anymore, this is a totally new game.

Here is my attempt to hash out the details of this new Werepoker.

Continue reading Werepoker

Life, One Step at a Time

Gamedev is having a board game contest next Tuesday. This had me excited enough to come up with a new board game, before the contest (so I can’t use it for the contest, because you’re supposed to come up with one on the spot!). The constraints for the contest are: has to be played on a Go board with Go stones, and cannot have more than 5 rules (which is tough to measure, but essentially it should be simple). It’s an exercise in emergent complexity.

When you think about a grid and emergent complexity, what comes to mind? That’s right, Conway’s Life. Here’s my board game based on it:

The initial board state is two π heptominos, facing each other and offset by one, like so:

----
 x x
 x x
 xxx

ooo
o o
o o
----

Don’t let the picture fool you, the board is bigger than that. I think 19 (standard Go board) is a good width. “o” can also go past the line at its back, but if “x” makes it there, then “x” wins (and vice versa, of couse).

On each player’s turn, he may add or remove a white or black piece (there is no restriction that the white player may only add or remove white pieces) according to the rules of Conway’s life:

  1. If an existing stone has fewer than two or more than three similarly colored neighbors, it may be removed.
  2. If an empty space has exactly three similarly-colored neighbors, then a stone of the same color may be added.
  3. If a piece has exactly three oppositely-colored neighbors, then it may be replaced by the opposite color, and it is considered to be “captured”. For example, if you had a board like this:
     xx
    ooo
    

    Then an “o” may be placed (by either player, but it’s obvious who would want to do it) and replace the left “x”, which gives the “o” player a capture. If this is done 5 times, then the “o” player wins.

Winning conditions are twofold: if you reach the opposite edge of the board (which we’ll say is the farthest point of the initial setup (the dashed lines in the first example)), then you win. Or if you succeed in capturing five pieces, you win.

And, the killer sixth rule which is a necessity: the ko rule. The board may never return to a previous state.

I was originally going to call it Conway’s God, because it’s life that you are “playing god” over. But Jude asked what we were playing, and Namaste said “Life, one step at a time”, so that is the official name now :-). It can be shortened to Losat if you wish.

Amazing Werewolf

Jude hosted a “game day” yesterday, and lots of people showed up. I think at peak we had sixteen people in our house. From about 8:00 until midnight, we played Werewolf, a variant of Mafia. They were all interesting, dynamic, well-balanced game s. Here are the role lineups for these games:

  • 2 Werewolves, 2 Villagers, Bodyguard, Witch, Seer, Romantic
  • 2 Werewolves, 2 Villagers, Bodyguard, Witch, Seer, Romantic, Werehamster
  • 3 Werewolves, 3 Villagers, Bodyguard, Witch, Seer, Romantic, Hunter

An explanation of our definitions of these roles will be given at the end of this post.

The last game we had was the best game of Werewolf I have ever played (the lineup was the third one here). I was given the Werewolf role, along with Jude and Travis. In the previous game, I had mentioned that when we were analyzing the game a while ago, we determined that if the seer sees a werewolf in the first round of the game, the seer should immediately speak up and say who it was (technically, that only applied to games with two werewolves, though). So Jude cunningly spoke up right as the game started and fingered Paul as a werewolf. Some discussion ensued about how to verify whether Jude was actually the seer, but nobody was contesting him, so many people trusted him. People still wanted some verification. We lynched paul on the first day.

That night, we werewolves chose Jude, one of our own, to be eaten. The witch finds out who is chosen to be eaten by the werewolves each night, so we figured that she would see Jude as the target and therefore not suspect him (it makes sense for the werewolves to eat the seer, no?). We knew he wouldn’t be eaten, because the bodyguard would be protecting him, and the witch would probably save him, too (so the witch used up her save on the first night!).

Day broke, and both Gabbie and Cami were dead. I was confused, and thought that our game master had screwed up. It was a wonderful turn of events, because when two people die in a night, nobody can be sure whether the Witch killed somebody extra or the wolves ate the romantic. We wolves (after coming to our senses) deduced that only one thing could have happened: Jude was saved by the witch (or bodyguard) and the witch targeted Gabbie or Cami, one of which was the romantic. I was already forming my plan: if I was put on trial, I would be the romantic, because the real romantic was dead and could not contest. Of course my lover would be Travis, who would support me. (As it turns out, my plan was flawed because the witch also knew what had happened the first night)

Jude said that he had seen the witch, but he didn’t want to reveal who the witch was. Putting myself in a skeptical villager’s shoes (as I did many times that game), I called bullshit on Jude. We were looking for verification, and he said something which provided no information at all. The others didn’t seem to care, though, nobody was on board with my theory. This is a good sign.

After a little argument, we did the first round of voting, and Hagan and I were up on trial. I could leverage my skepticism of Jude during this: I claimed that since no information was known about me yet, should I survive, Jude should identify me the next night. Therefore it is absolutely imperative that I not give away my role, so that Jude can be securely verified.

During the unusually long discussion period after we were nominated, Daniel claimed that he was the witch, and Jude confirmed, “yep, he was the one I saw”. Out of the blue, Sophia said “that’s not true, because I’m the witch”, and Daniel said, “that’s true, I was bluffing!”. Oh, shit! Jude’s been found out! Hagan came out while he was on trial and “claimed” to be the seer. The only information he had was that Cami was a villager and Gabbie was the romantic. Completely irrelavent, uninteresting, unverifiable information. This did not help his credibility. I don’t see how people could have trusted Jude after the witch event, so I’m guessing that people assumed the real seer was already dead. Jessa mentioned that she was the Hunter, and if she died, she would kill Daniel (probably for lying about being the witch). Hagan was put to death.

That night, we werewolves (after a long period of silent arguing) selected Jessa. I hadn’t remembered her comment, but in retrospect that was absolutely the right move. She was true to her word and selected Daniel to take with her. And the werewolves, all three intact, win after the second night!

The game took at least an hour. Many of our Werewolf games are not that interesting because people play straightforwardly: people simply choose when to reveal the true information that they know. Werewolves try to avoid being put on trial or executed, by claiming they are a villager or something. This game was totally different: people were claiming to be things that they weren’t—important things, not just nondescript villagers. When Jude pretended to be the seer, he had to come up with some information that he had found out. Basically, people were gutsy, and that made for an incredibly deep, twisty game. So there’s a lesson: be gutsy and tricksy in Werewolf games, it makes the game as a whole better.

Here are the roles we used:

  • Werewolves: must unanimously decide each night who to eat, which may be one of the werewolves. If the selected person is unselected, he dies that night.
  • Bodyguard: chooses one person each night to protect. If that person is selected by the werewolves, then they don’t die. The bodyguard is allowed to protect himself.
  • Witch: is told each night who is about to be eaten by the werewolves (regardless of whether they are under bodyguard protection). Once during the game, the witch may choose to save this person, in which case they do not die. Once during the game the witch may choose to kill someone, and that person dies, even if under protection by the bodyguard.
  • Seer: each night chooses one person, and the role of that person is revealed to him. The seer also acts on the night before the first day, and is the only role who does so.
  • Romantic: on the night before the first day, chooses another player, and those two players become “romantically entangled”. They may never vote for each other during the nominations, and if one dies, then the other does, too.
  • Werehamster: is a third faction, in a sense. The werehamster counts as a villager in most respects, but if the werehamster survives until the end of the game (either by the werewolves coming to equal numbers with the villagers (including the hamster), or by all werewolves being eliminated), then the werehamster wins instead. The werehamster cannot be eaten by werewolves (their selection simply has no effect), and if the seer ever chooses to look at the werehamster, then the werehamster immediately dies. The werehamster can be hanged, and can be killed by the witch and the hunter.
  • Hunter: when the hunter dies (regardless of how: lynching, werewolf, witch), he must select another player to take to the grave with him. We did this in a sortof half-information way: If the hunter dies during the day, he selects someone else in broad daylight and they both die, so everybody knows who he is. If the hunter dies at night, then the gamemaster adds a new phase that night: “hunter, select someone to kill”. Two people will die that night, but nobody is sure which is the hunter and which was his target.

We never reveal the role of dead players, never allow dead players to speak, and never reveal how someone was killed (i.e. whether it was by witch or werewolf (or in the hamster’s case, seer)).

MMORTS

I want to make a Massively Multiplayer Real Time Strategy Game. Well, not so much massively as highly. I’m thinking around 100 players. I’m particularly interested in command structure: you have an RTS where every soldier is controlled by a real person, and then formally there are units of soldiers with a Sergeant, and a Commander for the whole battle.

Traditionally, I think many game designers have hoped that at least the sergeant level would emerge if you gave teams free communication, but that rarely happens in practice. So what happens if you formalize it? Let’s go pie-in-the-sky for a moment and assume that we have a good traditional action game and a good traditional RTS game. How would the player flow go?

You can start a new game as a commander (against another commander), and as commander you can take control of one soldier. You have a one on one game. More people may join the game as sergeants, and once there are a certain number of those, as privates. It would have to allow joining mid-game, because organizing a game of this size would be impossible.

Given that I’m interested in fairly large-scale games with these dynamics, there would have to be some way to encourage people not to be commanders at first. As long as the action element is solid, and it would have to be, you could play one on one and small team games to build up your rank. At certain times you would be promoted and be able to join as a sergeant with, say, four privates at your disposal. Some time after that, you may start a game as a commander. Sadly, this would probably limit the “commander” gameplay to a small subset of people. But that kind of makes sense; if fifty people are going to trust their time to you, they have to think they can trust you. So only ladder leaders may be commanders (it would be amazing encouragement to “grind” through the lower levels—grind used loosely, it would still be damn fun).

The commander would have an RTS-like view of the map with very limited information about the opponent displayed. Soldiers don’t appear on radar; spotted units would probably appear as indiscriminate dots, relying on the soldiers themselves to verbally report to their commander identifications of the units. Of course, the commander would know all the positions of his troops. Essentially, I want to encourage communication—human interaction—to play well. The commander would know by the interface that he had to communicate, because it would be impossible to lead an army without doing so. Perhaps orders should be typed (or, heck, spoken) rather than click-actioned. Maybe click actions for the common ones.

Aaaanyway, back to reality. Soylent doesn’t have the resources to pull off a merger of those two traditional styles. What kind of game would capture the essence of this type of thing, but that I could write alone or with Namaste in a couple of weeks?

I keep thinking 2D, because 2D is so much easier to make look decent and way easier to code for. But there still needs to be a very long learning curve; there must be a distinction between good soldiers and great soldiers, else the idea would be lost. I think we need 3D. I want to use some existing FPS engine, but I don’t really want to mod an FPS, because (1) I want the gameplay to be unique, and (2) tweaking an FPS’s gameplay isn’t something that is interesting to me, because I’m not a huge fan of the FPS genre. The main reason I want the gameplay to be unique is because, again, I’m not a huge fan of FPS’s. It could also change the social mentality of the game, because so many people play FPS’s where they think and act for themselves, and now it’s best for them to follow orders and carry them out as best as possible. I guess it isn’t too different from single player FPS in that respect.

Maybe I could even take something like bzFlag and adapt it to suit this. bzFlag’s controls suck so much though. But it might be salvagable; it is a decent engine, already with networking support, and it’s open source. And it already has a decent community, which we could draw on. And it already has leaderboards (with well-known, respected leaders), where we could get commanders.

idea &

Real Time Strategy

With the release of Supreme Commander and Command & Conquer 3, I’m being reminded that real-time strategy is my favorite genre, by leaps and bounds. There have been many games which have caught my attention, which I have had some fun playing. But I’ve played at least an hour’s worth of Supreme Commander every day for the past week and a half, as well as spending considerable time researching the mod interface.

And I want to design a real time strategy game. Well, no, I want to design many real time strategy games, just to see how they play out. I don’t want to make the perfect game, I just want to explore the space. And it’s unfortunate, because RTS engines are bitches to write. You really wouldn’t think so, but there’s a lot of little things that get in the way. As one example (and there are several), pathfinding is one of those things where you know exactly what to expect, but is incredibly, incredibly hard to get right in code. It’s not that hard to write a pathfinding engine, but it is hard to write one that works like you’d expect. Supreme Commander, state-of-the-art, still doesn’t get it right.

SC has inspired me though. I realized that I don’t really like the action part of those games. I like the real-time nature, I like the pressure, but I don’t like playing individual units. I’m interested in terrain fortification, army composition, the information game, large-scale tactics, and economics. I’m not very good at any of that, but SC has got me learning.

SC is still broken. It quite successfully took the micromanagement out of battles, but unfortunately it forgot to take the micromanagement out of base-building. You can tell a 100 unit land army to attack, and your heavy tanks will automatically go out front, your artillery in back, and your anti-air supporting from various positions, but you still have to tell each of your construction units to build mass extractors on every deposit! Of course I want to build a mass extractor there, stupid! I want to see a game that focuses on eliminating the micro there, too. And I would see one if SC weren’t so hard to mod (the lua code is buggy, undocumented, and silently ignores every error, making it very very hard to debug and experiment).

Okay, enough ranting about SC. It’s a really great game, and I’m just ranting in an uncanny valley because I see so much potential. Its release has opened up a world of possibilities for RTSs that I hadn’t even noticed before.

How can I explore the RTS space without writing an RTS engine? Galactic Flotsam is one way, and there may be many similar approaches. I just watched an episode of Star Trek TNG called “Unnatural Selection”, which got me reading about viruses. I was thinking a game based around cells and reproduction could make an interesting RTS. You could, say, have twelve different players (3 human 9 AI) with your goal simply to maintain a large population. You could manually tweak your DNA, preferring different resources, becoming a parasite, becoming larger or smaller, in addition to being able to generally influence the travelling direction of your cells. It would be an easy engine to write, and would have RTS-like game dynamics (except with a prototype object model rather than a class object model—Javascript instead of Java).

Or I could pick up one of the partial RTS engines that I’ve written over the years. But those are small-scale, good for C&C work-alikes. If I want to make a “serious” (that is, copying the state-of-the-art) RTS, modding SC might be my best bet after all. Realistic, army-based games are interesting to me, but abstract strategy is interesting to me too. I’ve never cared much about context.

Sword Gestures

It has been two weeks since I have done the slightest amount of work on the sword game. Kudos to Ben for keeping it moving along. Anyway, it’s time for some brainstorming.

Our current idea (as of last week) for a control scheme for the sword game is (1) to have it in slow motion for strategic, rather than strictly action, play, and (2) to control the sword based on gestures, of sorts. Not pre-programmed gestures like (ugh) Black and White; more like drawings of what you want the sword to do. Draw a Z and you’ll get a Zorro motion. I like this idea a lot, and I think it has a lot of potential. So, I have to tackle the problem of, given a gesture, how do you figure out what to do with the sword.

Well, we want it to be sort of vague and interpretive. We also want it to be natural, the way a human would interpret when given that gesture. These two things point me straight toward setting up descriptive equations, filling in known information, and solving for the rest of the details. But what kind of information does the gesture specify?

We know it starts about where the sword currently is when you draw the gesture, and it ends in the same direction as the end of the gesture. We can intuit velocities, but I think it’s better to let the equations figure those out. We also know a few points on the curve (as many as we need, really). We’re trying to solve for the force to exert at every step. Oh, and we know we have a maximum force we are allowed to exert, which should play a role in the solving process (so the solution doesn’t try to do anything impossible).

A Bezier-like spline might suffice. We are given a curve, i.e. a bunch of points, and we’re trying to find a smooth interpolant. Let’s look at what information we have at each point:

  • A 2D position at each point.
  • A 3D position and velocity at the first point.
  • (perhaps) A time at the last point.

y much information. And the information we need:

  • A 3D force for the handle at each point.
  • A 3D force for the tip at each point.

I’m making the assumption that we linearly interpolate the forces between each point, so the force half-way between two points is the average of the forces at each of the two points. So we have 6 unknowns. We need 6 equations (for each point).

How do we interpret the 2D data? I’m going to say for simplicity’s sake that we put a plane in front of the fighter and require that the sword pass through the corresponding point. This may be the weakest assumption of the algorithm. And there’s another problem with this approach: in order to compute that, we need the position and orientation of the sword at each point, another five unknowns in exchange for only two equations!

Hmm, as I hash this approach out, it seems to be breaking down. Maybe I should scrap and come from a different angle.