• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
gpmelendez

AI for a simple shedding card game

12 posts in this topic

Hello,

We have this game with 4 players where each players take turns to discard cards that must be higher than the ones previously discarded. The last player with remaining cards loses. I have code on the gameplay, and the AI has code that can list valid combinations from the cards that it has.

I'm planning to use Monte Carlo playouts.

What do you think?

Edited by mudslinger
0

Share this post


Link to post
Share on other sites
Monte Carlo sounds an excellent approach here, but unlike in your pseudo, you need to be very smart about where you direct your playouts. Having a fixed "Do 10,000 times" loop in the code is very inefficient and wastes a lot of the playouts.

An important aspect of Monte Carlo is to construct/expand a game tree while the playouts are being played. You should never settle to just playing a fixed number of playouts at the root of the tree (or you can, but it won't be as effective). This is the machinery that causes the result to converge to the best play as you increase the number of playouts.

You'll also want to estimate the uncertainty of a certain branch. For a move M, if you play 1000 random samples and always lose, versus if you played 1000 random samples and win 50% of the time, you'll know statistically that you should probably invest more on the latter case, and never play the first move. This should guide the statistical playouts to balance the search towards uncertain branches. [url="http://web.engr.oregonstate.edu/~afern/classes/cs533/notes/uct.pdf"]UCT tree search[/url] is one of the recent key advances in the field. [url="http://pasky.or.cz/go/compgo-r3.pdf"]This is also an interesting read[/url], that gives some more references.
2

Share this post


Link to post
Share on other sites
I'm not that familiar with Monte Carlo, although I fully understand the pseudocode.

What do you mean by "construct/expand a game tree while the playouts are being played"? I'm thinking this means I should use a game tree then randomly playing out the leaves.

I'll be reading about UCT and Monte Carlo in general, I hope it will be fruitful. Edited by mudslinger
0

Share this post


Link to post
Share on other sites
Yeah, even with Monte Carlo, it's customary to maintain a game tree. Instead of exploring the tree fully like with traditional minimax, the tree is expanded only selectively to the areas based on the Monte Carlo simulation. When the tree search hits a leaf node (the moves after that node are not tracked by the tree), the game is continued with random play i.e. a random playout until the end is performed.
1

Share this post


Link to post
Share on other sites
As clb points out, there is a large improvement available over sampling every move the same number of times. There are good move and bad moves, and after sampling them a few thousand times, you should have a pretty good idea of which are which, and you can exploit this by sampling promising moves more often. This idea is formalized in the [url="http://en.wikipedia.org/wiki/Multi-armed_bandit"]multi-armed bandit problem[/url]. There is an algorithm called UCB1 that is a good starting point.

The idea of building a tree is important for full-information games, but I don't think it will get you very far in a card game of this type, since a node depends not only on what the previous moves have been, but also on the plausible scenario generated.
1

Share this post


Link to post
Share on other sites
This looks like a very good resource:
[url="http://www.personeel.unimaas.nl/g-chaslot/papers/progressiveMCTS.pdf"]http://www.personeel...ressiveMCTS.pdf[/url]

as Alvaro pointed, I believe building a deep tree will not be helpful, as uncertainties will compound. maybe trees aren't even helpful at all.

I'm doing reading on UCB1. Edited by mudslinger
0

Share this post


Link to post
Share on other sites
[quote name='alvaro' timestamp='1349986268' post='4989234']
UCB1 is basically formula (1.1) in that paper.
[/quote]

Yes, I just realized how simple UCB1 is. I'm reading another paper/presentation: [url="http://www.cs.bham.ac.uk/internal/courses/robotics/lectures/ucb1.pdf"]http://www.cs.bham.a...ctures/ucb1.pdf[/url]. I just made a simple C implementation of UCB1 with the rand() function. It does test more rewarding functions more.

This is making more sense to me. I'll start coding again tomorrow.

EDIT: I just realized that the tree in the progressiveMCTS paper is not the game tree I think it is. I thought it was something similar to a min-max tree, in which each layer is a turn of each player. It is not - all of it is the turn of the current player. Is this thinking correct? I'm confused as to how this would work though, all of the results are back propagated to the root, and the root is always visited, therefore the root will always be chosen as the move.

EDIT2: It does say the child that was visited the most [img]http://public.gamedev.net//public/style_emoticons/default/tongue.png[/img] again, more feelings of realization. Based on the simple rule, since a leaf will be expanded upon simulation, does this mean each leaf is simulated only once?

[s]Then again, trees might not be worth it, it's probably better to just list every possible move, then run UCB1 on them.[/s] Edited by mudslinger
0

Share this post


Link to post
Share on other sites
Where do you use rand() in UCB1? The original algorithm is deterministic (which is kind of strange for a Monte Carlo technique, but the randomness comes from the results of the playouts).

Start by implementing UCB1 at the root. It's basically the same as the pseudo-code at the beginning of the thread, but instead of sampling each move the same number of times, you always sample the move that has the highest UCB1 value:
[code]While there is time {
Select the move M that maximizes the UCB1 formula
Generate a plausible configuration for the cards of the opponents
Play M
Run the rest of the game randomly (room for improvement here)
Count how often you won
}
Pick the move that was picked most often[/code]

Don't worry about the tree part for now, but I'll be happy to explain it to you if after reading and thinking about it for a while it still doesn't make sense.

By the way, is this for some sort of simplified Tichu variant? I love Tichu!
0

Share this post


Link to post
Share on other sites
I think I understand the tree part now. The expanding part is not directly dependent on the number of simulations, for example, I can do 1000 simulations, then generate a branch. I can generate another 1000 simulations, then generate another branch. I think I can't apply this to my game since the game has a max 13 moves at the start and this drops quickly. I'd run out of moves for the tree. Your pseudocode is what I had in mind.

I'm not familiar with tichu.

here's my UCB1 code, it's a bit rough, I apologize.
[url="http://pastebin.com/rddWUSzF"]http://pastebin.com/rddWUSzF[/url] Edited by mudslinger
0

Share this post


Link to post
Share on other sites
The tree part of Monte Carlo Tree Search (or more precisely the UCT algorithm) is basically using the UCB1 mechanism not only at the root, but also at other nodes that you end up visiting many times.

The problem with this in the case of card games is that you will be dealing the cards you haven't seen randomly at each simulation, so there won't be many instances of visiting the same situation twice, because from the point of view of the next player, the situation is different after each plausible configuration is determined.
0

Share this post


Link to post
Share on other sites
[quote name='mudslinger' timestamp='1349877808' post='4988724']
Hello,

We have this game with 4 players where each players take turns to discard cards that must be higher than the ones previously discarded. The card combinations are based on poker. Discarded cards are visible to everyone. The last player with remaining cards loses. I have code on the gameplay, and the AI has code that can list valid combinations from the cards that it has.
[/quote]

i'd like to toss out an idea, but before i can(as it might be moot depending), i'd like a bit of clarification of the rules, if i understand them correctly:

you can discard any number of cards, so long as it's a valid poker combination, and it must be higher than the last card discarded?, exactly how is that value calculated?, as well, how many cards are players given at start? Edited by slicer4ever
0

Share this post


Link to post
Share on other sites

I have more or less finished the game, it can be played here: [url="#"][/url] . Java is needed.
I also put the rules here: [url="#"][/url]

Everything on the website is still beta, the game doesn't even have drag-and-drop. I was too lazy to write it tongue.png

Edited by mudslinger
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0