I just had to tell everybody about a new Magic program that I found. It is called Magarena. It has 900 cards and a very good AI. The computer can (and will) play instants and abilities during combat and at end of turn. I "researched" the program very thoroughly and I had a good time playing against such a smart opponent. Some of the games lasted 20 or 25 turns because the game AI was so good. In those close games I had no idea if I would win or lose.
Magarena has a very nice user interface and looks likes a real videogame. The user interface is much more graphical than Forge and has an elegant wood background. Magarena also has "undo" which lets you fix a mistake or try to sneak something else past the intelligent AI. Undo is a great feature because it is universally used and understood.
Magarena uses min-max for the AI and is written in Java. Feel free to post your comments about Magarena to the forum thread here.
Download - Magarena's Google Project page, runs on Windows, Mac, Linux