Thursday, February 25, 2010

Programming Chess Wiki

I stumbled upon a very cool wiki that covers all aspects of chess AI programming. The alpha-beta webpage is better than Wikipedia's because it has actual pseudo-code that looks functional. It would be very cool to apply some of these ideas from chess to Magic.


Chess Programming Wiki
Alpha-Beta

Monday, February 22, 2010

New Version

Well thanks to Dennis, Rob, Chris (the guys from the forums) there is a new version of Forge that has about 100 new cards, which raises the grand total to an astonishing 2,756 cards.

Are you tired of those crappy card scans from wizards.com? Now you can download high-resolution scans. From the “New Game” screen, which is the screen when you first start Forge, click on the menu option, which is named “menu”. The “Download Card HQ Pictures” option will download the new high-res pictures, while the “Download Card LQ Pictures” option will get the smaller pictures from wizards.com. (HQ stands for high quality and LQ stands for low quality.) One warning though, the HQ cards will require an extra 250 MB of memory and if you don’t have it the program will crash with a “stack out of memory” error.

In the same menu, you can radically change the looks of the program by clicking on the “Display Options” which lists 32 skins. Make sure to check out the “napkin” skin.

OK, down to the cards. Forge has a number of Worldwake cards such as the rare lands: Raging Ravine, Creeping Tar Pit, Stirring Wildwood, and Celestial Colonnade. Worldwake vampires include: Ruthless Cullblade, Pulse Tracker, and the rare Anowon, the Ruin Sage (3BB, 4/3) “At the beginning of your upkeep, each player sacrifices a non-Vampire creature”. Forge now includes the powerful Strip Mine which lets you sacrifice it, to destroy one of your opponent’s lands.

Green mages will love Worldwake’s Harabaz Druid (1G, 0/1) “tap: Add X mana of any one color to your mana pool, where X is the number of Allies you control”. Other Worldwake cards include: Avenger of Zendikar (5GG, 5/5) with a number of abilities and the token making Bestial Menace (3GG, sorcery). Forge now has one of the most exciting green cards ever, Doubling Season which doubles the number of tokens or counters that you receive. (This card may be a little buggy since it is so complicated.)

Other great Worldwake rares include: Basilisk Collar (1, equipment) which gives deathtouch and lifelink, Goliath Sphinx (5UU, flying 8/7), Dragonmaster Outcast which creates 5/5 dragons if you control 6 or more lands. Forge also has a bunch of other common and uncommon cards from Worldwake.

I guess I’m a timmy (inside joke) but Death’s Shadow looks fun to use. A 13/13 creature that only costs B but gets -X/-X where X is your life total, talk about living dangerously, ha.

So in conclusion, enjoy life, play Magic, and don’t spend all of your money on penny candy.

Download Forge 02-21 - (8 MB 2,756 cards) This version fixes some bugs and should run better than the 02/09 version. This is the 02/21 version because that is when it was released on the forums.

(Originally I posted the 02/09 version but then I posted an updated version since it seems to run better. Hopefully that isn't too confusing.)

All Card Pictures (70 MB) - Put these in the pics directory

p.s.
Blue mages can now enjoy the bluest Magic card ever: Stifle, which can counter activated or triggered abilities.

p.p.s.
On a side note, I didn't realize that I have been posting the Forge program without any decks included. I've included 171 decks in the current version and made the decks available as a separate download on the Google Project.

Friday, February 19, 2010

Learning as Prediction

This isn't a whole fleshed-out idea, just a snippet. Learning can be viewed as prediction. If I can predict the outcome by looking at the current situation, that is the same as learning. If I see the symbols
4 x 8 =
and I predict that the answer is 32, thus I've "learned" something by using prediction.

Learning is a huge field that is hard to precisely pin down. But if you view learning as a form of prediction things become much clearer.

Just my 2 cents, have a great weekend.

Monday, February 15, 2010

Hypnotic Specter

Hypnotic Specter (HP) is one of my favorite cards in Magic and one of the cards that make Magic so interesting. Part of me dislikes “interesting cards” because they tend to be very hard to program. I’m glad to say that Forge allows you to use (and feel the power of) HP without paying $2 per card (starcitygames.com cheapest price). I’m sure other cards have triggered abilities like HP, but HP was one of the first cards to be truly feared. Flip HP onto the battlefield with a first turn Dark Ritual to incite pure terror.

I would like to say that Forge easily handles HP and other cards like it but it doesn’t. Like so many things it is hardcoded, the combat code specifically checks for HP. (To programmers, hardcoding something is akin to using duck tape. It works, but it is messy.) While this isn’t very elegant, it works. (“It works” is probably my favorite excuse.)

A better solution would be to have a battle damage hook or event like
combatDamage(int nDamage, Card damageTo, Card damageFrom)
This would keep the card code together, instead of sticking some of the card code with the combat code. Currently Forge only has a few very basic events like when a card is added or removed from a zone or when a player’s life points changes. Adding a combat damage event to Forge doesn’t seem too difficult and maybe I could work on that.

And to be thorough it would be good to add abilities that trigger when they deal damage to a player or just deal damage (whether during or outside of combat).
combatDamage(int nDamage, String player, Card damageFrom)

damage(int nDamage, String player, Card damageFrom)
damage(int nDamage, Card damageTo, Card damageFrom)
p.s.
I would like to say that I programmed HP but I didn’t. It was probably one of the forums guys like Dennis or Rob. Thanks.

Wednesday, February 10, 2010

More Scripted Cards

To begin with you should know that scripting is great, chocolate tastes good, and never combine Cherry Coke and Mountain Dew because it just tastes bad. Here are a few other examples of scripted cards.

Arnjlot's Ascent
1 U U
Enchantment
no text
Cumulative upkeep:U
abPumpTgt 1:Flying:Target creature gains flying until end of turn.

This is one of the weirdest card names ever and it combines cumulative upkeep and "1: Target creature gains flying until end of turn." The "flying" keyword can be substituted with any other keyword that Forge understands like lifelink, deathtouch, trample, haste, shroud, etc...

The reason that Arnjlot's Ascent and other cards have the line "no text" is because that line of text is used for static abilities and sorceries/instants.

Flamecore Elemental
2 R R
Creature Elemental
no text
5/4
Echo:2 R R

Echo is also supported.

Illusionary Wall
4 U
Creature Illusion Wall
no text
7/4
Defender
Flying
First Strike
Cumulative upkeep:U

Scripting easily allows cards to have multiple abilities.

Drifting Djinn
4 U U
Creature Djinn
no text
5/5
Flying
Cycling:2
At the beginning of your upkeep, sacrifice Drifting Djinn unless you pay:1 U

This is another fairly complicated card that has flying, cycling, and an upkeep cost.

Furnace Whelp
2 R R
Creature Dragon
no text
2/2
Flying
PTPump R:+1/+0

The PTPump keyword implements abilities like "R: Furnace Whelp gets +1/0 until end of turn." PTPump implements a wide range of abilities that change the power or toughness of a creature that requires a mana cost. This is a very common ability that many creatures have.

Traumatic Visions
3 U U
Instant
no text
TypeCycling:Basic:1 U

Traumatic Visions says "Counter target spell" and scripting adds basic landcycling, "1 U, Discard this card: Search your library for a basic land card, reveal it, and put it into your hand. Then shuffle your library."

Valley Rannet
4 R G
Creature Beast
no text
6/3
TypeCycling:Forest:2
TypeCycling:Mountain:2

The TypeCycling keyword also understands cycling for a specific land type. This is sneaky because this lets you fetch non-basic lands that have the correct land sub-type like Watery Grave (Ravnica) or Volcanic Island (Beta). Here is a little trivia, Volcanic Island was the only dual land not printed in Alpha.

Tolaria West
no cost
Land
no text
Comes into play tapped.
tap: add U
Transmute:1 U U

Tolaria West is completely scripted because "Comes into play tapped" is recognized as a special phase, "tap.add U" is recognized because all mana abilities in Forge are just strings, and transmute is also recognized. And in case you don't know, transmute lets you search for another card with the same converted mana cost.

Akroma, Angel of Fury
5 R R R
Legendary Creature Angel
no text
6/6
Flying
Trample
Protection from white
Protection from blue
PTPump R:+1/+0
Morph:3 R R R
This card can't be countered.

Akroma, Angel of Wrath
5 W W W
Legendary Creature Angel
no text
6/6
Flying
Vigilance
First Strike
Trample
Haste
Protection from red
Protection from black

And I'll end with these two lovely ladies who are both entirely scripted. Each card has seven different abilities.

You should thank your lucky stars that Forge has Akroma, Angel of Wrath. She is one of Magic's best cards although Baneslayer Angel is a very close 2nd. Forge also has Baneslayer Angel in case you want to give her a spin.

Thanks for taking this tour through Forge's scripting. :=)

p.s.

Baneslayer Angel
3 W W
Creature Angel
no text
5/5
Flying
First Strike
Lifelink
Protection from Demons
Protection from Dragons

p.p.s.

This is a complete list of all of the keywords that cards.txt recognizes. For more specifics you need to poke around and ask a few questions in the forums.

{cardName} is {color}
{cost}, Sacrifice {card name}: Draw a card.
{cost},{tap}: add {mana}
abPump[Tgt]
abDamageCP
At the beginning of your upkeep, {card name} deals {num} damage to you unless you pay:{cost}
At the beginning of your upkeep, destroy {card name} unless you pay:{cost}
At the beginning of your upkeep, sacrifice {card name} unless you pay:{cost}
Cascade
Changeling
Comes into play tapped.
Cumulative upkeep:{cost}
Cycling:{cost}
Deathtouch
Defender
Devour:{magnitude}
Double Strike
Draw a card.
Echo:{cost}
Enchant creature
Enchant land
Enchant land you control
Exalted
Fear
First Strike
Flanking
Flash
Flying
Forestwalk
Haste
Horsemanship
Indestructible
Intimidate
Islandwalk
Landfall
Legendary landwalk
Lifelink
Modular
Morph:{cost}
Mountainwalk
Nonbasic landwalk
Persist
Plainswalk
Protection from {color}
Protection from artifacts
Protection from creatures
Protection from Demons
Protection from Dragons
Protection from enchantments
Protection from Goblins
Reach
RegenerateMe:{cost}
Remove three spore counters from this card: Put a 1/1 green Saproling creature token into play.
Scry
SearchMerc:{cost}
SearchRebel:{cost}
Shadow
Shroud
Soulshift
spDamageTgt
spDestroyTgt
spDrawCards and spDrawCards v2
spLoseLifeGainLife
spPumpTgt
spRaiseDead
Swampwalk
tap: add 1
tap: add B
tap: add G
tap: add R
tap: add U
tap: add W
This card attacks each turn if able.
This card can't be countered.
This card can't be the target of Aura spells.
This card can't be the target of spells or abilities your opponents control.
This card doesn't untap during your untap step.
This creature can block as though it had flying.
This creature can block creatures with shadow as though they didn't have shadow.
This creature can block only creatures with flying.
This creature can't attack
This creature can't attack or block
This creature can't attack unless defending player controls an Island
This creature can't be blocked except by creatures with flying
This creature cannot block
Trample
Transmute
TypeCycling
Unblockable
Untap:{cost}
Upkeep:{cost}
VanillaEquipment
Vanishing
Vigilance
When this card comes into play, draw a card.
When this card is put into a graveyard from anywhere, reveal this card and shuffle it into its owner's library instead.
When this card is put into a graveyard from the battlefield, return this card to its owner's hand
When you control no Islands, sacrifice this creature
Whenever a creature dealt damage by this card this turn is put into a graveyard, put a +1/+1 counter on this card.
Wither

Monday, February 8, 2010

Scripted Cards

There are two ways to add to implement a card in Forge. One, you code it in Java. Two, you encode it using regular text, these types of cards are referred to as "scripted cards". Forge uses the file "cards.txt" to hold most of the card text, the text for most activated abilities is hardcoded elsewhere in Java.

OK, enough boring explanation, let me show you some examples from "cards.txt".

Eyeblight's Ending
2 B
Tribal Instant Elf
Destroy target non-Elf creature.
spDestroyTgt:Creature.nonElf

The card Eyeblight's Ending was implemented in Forge by only the above text, no other programming was necessary. In case you can't figure out what spDestroyTgt, it means "spell destroy target".

Miscalculation
1 U
Instant
Counter target spell unless its controller pays 2.
Cycling:2

This card is implemented by both scripting and Java. The scripting adds the cycling ability and elsewhere in the program Java is used to implement the counter spell.

Burning Fields
4 R
Sorcery
no text
spDamageTgtOpp:5:Burning Fields deals 5 damage to target opponent.:Burning Fields - deals 5 damage

Searing Flesh
6 R
Sorcery
no text
spDamageTgtOpp:7:Searing Flesh deals 7 damage to target opponent.:Searing Flesh - deals 7 damage

Scripting makes it easy to add multiple cards that do the same thing, like the two cards above.

The reason that these cards have the line "no text" is because that line of text is used for static abilities and sorceries/instants.


Kiss of Death
4 B B
Sorcery
no text
spDamageTgtOpp:4:Drawback$YouGainLife/4:Kiss of Death deals 4 damage to target opponent. You gain 4 life.:Kiss of Death - deals 4 damage; you gain 4 life.

Scripting can become complicated.

Eternal Flame
2 R R
Sorcery
no text
spDamageTgtOpp:Count$NumTypeYouCtrl.Mountain:Drawback$DamageYou/X.HalfUp:Eternal Flame deals X damage to target opponent where X is the number of mountains you control. It deals half X damage, rounded up, to you.:Eternal Flame - deals X damage and half X damage to you.

And scripting can become very complicated. I'm very impressed that such a complex card can be added so easily. (Easier than coding it in Java and easy only if you know how the spDamageTgtOpp keyword works.)

Scripting is very powerful and useful because it can be used to add many similar types of spells. Scripting is much shorter than using Java itself. Scripting is sort of "condensed Java" and is an example of a domain specific language, commonly referred as DSL.

Since scripting is such a fun topic, I'll be talking more about it on Wednesday. (Yes, I said that I wasn't going to post two times a week and I may not post next Wednesday but this Wednesday I’m going to post something.)

And I feel like I haven't injected enough humor into this article so I'll close by saying that scripting is better than chocolate covered bacon, hm....bacon. (I'm also a big Simpson fan.)

p.s.
I haven't done any of the real work when it comes to scripting. Yes, I did create very simple keywords like haste and trample but nothing complicated. All of the credit goes to Dennis, Rob, and the other guys at the forums.

For more info on Forge's scripting please consult the forums. (Thankfully we have a forum so you can ask questions.) Thanks to huggybaby for providing a forum for Forge and other Magic projects.

p.p.s.
And in case you are wondering, all mana costs in Forge have extra spaces in them, “3 W W ” versus “3WW” because it makes the coding easier. (The extra spaces makes the parsing very easy.)

Thursday, February 4, 2010

Worldwake

Worldwake is being released and the official Wizards spoiler is up.

Visual Spoiler

Try not to drool on the computer while feasting on all 145 cards.

(My secret ambition is to be able to quickly add new cards to Forge so that it would have the whole set before it officially went on sale. Of course my other secret ambition is to own a professional football team, so we'll see which one I fulfill first, ha.)

Monday, February 1, 2010

Alpha-Beta Weaknesses

The AI for two person games can be created using the alpha-beta (AB) algorithm. AB generates ALL possible moves in the future until the game has ended but usually that is impossible so you have to use an evaluation function which looks at the current game position and tries to calculate which player is winning and by how much. Obviously creating a good evaluation function can be very complicated. The "heart" of the AB algorithm is the evaluation function.

(Sorry for a little bit of review but I just wanted to make sure that everyone is on the same page.)

While AB has been very successful when applied to chess, AB is not without its weaknesses. AB does not have a "game plan", such as trying to maximize the value of Wrath of God. AB just looks ahead and picks a good move. The AB algorithm may appear to have a game plan which would give AB some "human characteristics". The best kind of AI is both challenging and realistically acts like a human opponent. (Depending on the specific game the AI may do something that a human player would never do which ruins the illusion of playing against another person. And yes I've had this happen to me while I was playing Forge.)

While AB does not do any planning, there are other algorithms that use goal-directed reasoning or planning. Unfortunately these types of algorithms seem 100 times more complicated than AB since they need more information. Reasoning and planning algorithms need to have knowledge about the game and the ability to generate or choose from a variety of plans.

Through trial and error, AB can be combined with planning algorithms which would allow the best of both worlds. Maybe AB could handle combat while the planning algorithm could choose an overall plan such as playing a creature every turn or effectively using Royal Assassin.

p.s.
If Forge 2 ever got AB working, it would be fun to let people tweak the evaluation function to see how it helps or hurts the AI's performance.