Automated Theorem Proving for General Game Playing

In the paper “Automated Theorem Proving for General Game Playing” by Stephan Schiffel and Michael Thielscher, the authors apply answer set programming (similar to Prolog) to improve performance in general game playing.  They point out that it is important for the AI to classify what type of game it is playing and to apply appropriate techniques for that class of game. For example null movesupper confidence treesalpha-beta searchBellman equations (dynamic programming), and temporal difference learning would all be appropriate for two-player, zero-sum, and turn-taking games.  Also it is important to recognize concepts “like boards, pieces, and mobility.” Apparently, van der Hoek pioneered using automated theorem proving to extract appropriate concepts from the game rules.  Shiffel and Thielscher extend the theorem proving to “automatically prove properties that hold across all legal positions.”

Advertisements

Leave a comment

August 1, 2012 · 3:18 pm

Quadratic Gardens

Quadratic Gardens

One interesting aspect of Dominion is that certain combinations of cards lead to widely varying growth rates: exponential, quadratic, linear, and “super” linear. Garden type strategies often lead to quadratic growth in the number of victory points.

If all you could buy was gardens and workshops, what would be the optimal percentage of gardens to obtain the fastest growth rate?

Answer: If the fraction cards that are gardens is G, then the total number of points after t turns would be about

pts = (# gardens) * (# points per garden)
= (G*number of cards)*( number of cards/10)
= G*t*(1-G^5)*(t*(1-G^5))/10
= t^2 G (1-G^5)^2/10.

Above, I am assuming the deck consists entirely of gardens and workshops and the number of cards is large. In that case the probability of not drawing a workshop in a five card hand is G^5.

Setting the derivative wrt G to 0 and solving gives Gopt = (1/11)^(1/5) = 61.9%Image

Leave a comment

Filed under Uncategorized

Thoughts on Card Combos

It is easy to see that if you’re action phase consists of laboratory followed by library, that the laboratory was useless.  This kind of reasoning is very easy for a human, but a bit harder for a computer.  The computer could apply statistics and some kind of online learning strategy to figure out that the laboratory-library combo is not very super, but it would have to run a rather large number of simulations to come to that conclusion and it still would not understand why that combo is not great.  Alternatively, we might be able to create a theorem prover that could prove that a laboratory-library action phase has the exact same effect as a single library.  It would be great if we could combine theorem proving, other types of plausible reasoning (Bayesian Networks?), and machine learning in an AI.  

Leave a comment

Filed under Uncategorized

Analyzing a random cardset

http://boardgamegeek.com/thread/354729/analyzing-a-random-cardset

I am wondering how many of these ideas can be put into an AI.  

Leave a comment

Filed under Uncategorized

First Thesis on Dominion AI !

http://gameprogrammer.dk/data/Developing_an_Agent_for_Dominion_using_modern_AI-approaches.pdf

 

Leave a comment

Filed under Uncategorized

PC Dominion Game

This PC Dominion game is fun.  The AI is not very strong, but it’s great for practice and most importantly allows you to replay the last set of kingdom cards.

http://www.slightlymagic.net/forum/viewtopic.php?f=61&t=2366&sid=896eaa920f47ce9290df1d7e2fa7f2d9

Leave a comment

Filed under Uncategorized

Hello world!

Welcome to WordPress.com! This is your very first post. Click the Edit link to modify or delete it, or start a new post. If you like, use this post to tell readers why you started this blog and what you plan to do with it.

Happy blogging!

1 Comment

Filed under Uncategorized