Boardgame AI
by Alkor · in Game Design and Creative Issues · 10/19/2011 (4:45 am) · 6 replies
Hello
I've created my "shell" for the game. Placeholder graphics, board-game and play pieces.
The main problem is implementing an AI system for a 3d boardgame.
I can do this in my brain, however I cannot translate in code. In a 2D game is much easier since in iT2D you have the default tilemap system. But what about T3D?
I've created my "shell" for the game. Placeholder graphics, board-game and play pieces.
The main problem is implementing an AI system for a 3d boardgame.
I can do this in my brain, however I cannot translate in code. In a 2D game is much easier since in iT2D you have the default tilemap system. But what about T3D?
#2
What you need to do is first is play the board game about 100 times with different human opponents, with the thought... How do I make this game into a database table(no don't put a sql server in your game just yet). Once you have it in a database table format for example... Lets look at Monopoly.... Because Monopoly is actually a very straight forward strategy...
1 - Go
2 - mediterranean avenue
3 - community chest
...
on on and on until you get to
... Boardwalk
Monopoly is simple here because you really only have once choice. Either buy the property if is available or not. Otherwise the game of monopoly is just following the instructions on spot you land. In any case we have reduced the complexity of the game down a single choice. Now it is a simple matter to make a state machine that looks at a bunch of different factors like... How much money do I have? How much money do I need? Is there an advantage to buying this property? The state machine can look at factors like, Is this the beginning middle or end of the game? It can even predict with a degree of certainty where it will land next, because rolling 2d6 rolls 7 about half the time and factor that into the decision.
So you end up with rule tree's like...
If we are in the first 5 rounds of the game
If I have enough money
If I am on Boardwalk ave
Always buy.
That kind of state machine will work amazing for a game with a limited number of possibilities like Monopoly. However you might also want to use fuzzy calculations to make the ai opponent seem more human.
buy = 0
If rounds < 5
buy+= 0.5
if money > $1000
buy+= .2
if I own Parkplace and I have option to buy Boardwalk
buy+= .9
buy += fuzzyrandomnumber from -.2 to +.2
if buy > 1 then
buy
This is the exact technique that IBM used to make Watson only they used crazy over my pay grade lexical analysis. But it came down to a fuzzy calculation like that.
The downside of this technique is that sometimes you will get answers like... Toronto is in the United States...
But still you completely obliterated the human opponents. But only because they lack perfect memory and discipline.
Oh on edit... way back in school I knew a guy who made an AI for the game of Sorry that was soul crushing, a game that I thought was random...
10/20/2011 (7:41 am)
Ive made Euchre players, Rummy players, Solitare players, and BlackJack players, that are as at least as good as me at these games, if not a little better because they have perfect perception and discipline. The BlackJack player could break the bank using really simple card counting techniques, even with arbtrairly large decks, because it had perfect memory. Man if they would just let me use my phone at the blackjack table in the Casino. But I digress.What you need to do is first is play the board game about 100 times with different human opponents, with the thought... How do I make this game into a database table(no don't put a sql server in your game just yet). Once you have it in a database table format for example... Lets look at Monopoly.... Because Monopoly is actually a very straight forward strategy...
1 - Go
2 - mediterranean avenue
3 - community chest
...
on on and on until you get to
... Boardwalk
Monopoly is simple here because you really only have once choice. Either buy the property if is available or not. Otherwise the game of monopoly is just following the instructions on spot you land. In any case we have reduced the complexity of the game down a single choice. Now it is a simple matter to make a state machine that looks at a bunch of different factors like... How much money do I have? How much money do I need? Is there an advantage to buying this property? The state machine can look at factors like, Is this the beginning middle or end of the game? It can even predict with a degree of certainty where it will land next, because rolling 2d6 rolls 7 about half the time and factor that into the decision.
So you end up with rule tree's like...
If we are in the first 5 rounds of the game
If I have enough money
If I am on Boardwalk ave
Always buy.
That kind of state machine will work amazing for a game with a limited number of possibilities like Monopoly. However you might also want to use fuzzy calculations to make the ai opponent seem more human.
buy = 0
If rounds < 5
buy+= 0.5
if money > $1000
buy+= .2
if I own Parkplace and I have option to buy Boardwalk
buy+= .9
buy += fuzzyrandomnumber from -.2 to +.2
if buy > 1 then
buy
This is the exact technique that IBM used to make Watson only they used crazy over my pay grade lexical analysis. But it came down to a fuzzy calculation like that.
The downside of this technique is that sometimes you will get answers like... Toronto is in the United States...
But still you completely obliterated the human opponents. But only because they lack perfect memory and discipline.
Oh on edit... way back in school I knew a guy who made an AI for the game of Sorry that was soul crushing, a game that I thought was random...
#3
I am stuck a little on the ideea of building a table of my game.
My game of choice is Senet. It's not very complicated, it just involves deciding what piece to move based on the dice throw. That's basicly it.
You said a table format. By that I understand columns and rows.
So I sort of build a decision tree/table on paper of what the player is going to do when he lands on a marked spot?
10/20/2011 (12:58 pm)
That was a very informative post Greg.I am stuck a little on the ideea of building a table of my game.
My game of choice is Senet. It's not very complicated, it just involves deciding what piece to move based on the dice throw. That's basicly it.
You said a table format. By that I understand columns and rows.
So I sort of build a decision tree/table on paper of what the player is going to do when he lands on a marked spot?
#4
I said table because I was going through the process of breaking down the game. If you look at monopoly, without reducing it, it looks much more complex than it is. the monopoly board is just a table.
But scanning the rules..
With Senet the board doesn't matter. Breaking it down, we are concerned with potential moves. In this case you put every potential move into your table. Then come up with a mechanism to rank each potential move.
Use the fuzzy form, rather than the procedural.
Does this move increase my standing - add to the rank of move
Does this move wind up blocked? Subtract from rank of move
Does this move reduce my opponents standing add..
Does this move remove a piece from the board add..
and whatever else you come up with... then perform the move with the best score. If there are a bunch of moves that are tied, just pick one randomly.
That will make an AI that can beat a person who is not familiar with the rules of the game... If you start recursively doing strategy like this, like not just this turn, but several turns out, you can make an expert game ai.
Chess Master 2000 was doing this way way way back in the day and utterly crushing me at Chess, don't worry about the cpu load here, because it looks like a lot from this side, but it is trivial... You are using more cpu load to render one of your game pieces...
The point is you want a stateless function, that returns the best/good enough move, no matter the state of the game board.
Also, remember for simple board games like this, you don't want an expert game system. You just want good enough. I quit playing Chess against computers BECAUSE I COULD NEVER EVER WIN NO MATTER HOW MUCH I TRIED!!!!! Your computer game is designed to entertain. Always losing is not entertaining. Buts thats me, thats why I don't like Casinos, I am smart enough to realize all the games are rigged against me.
Edit: sorta worked out some extra crappy grammar
10/20/2011 (2:05 pm)
Oh man, you picked a game I have never played...I said table because I was going through the process of breaking down the game. If you look at monopoly, without reducing it, it looks much more complex than it is. the monopoly board is just a table.
But scanning the rules..
With Senet the board doesn't matter. Breaking it down, we are concerned with potential moves. In this case you put every potential move into your table. Then come up with a mechanism to rank each potential move.
Use the fuzzy form, rather than the procedural.
Does this move increase my standing - add to the rank of move
Does this move wind up blocked? Subtract from rank of move
Does this move reduce my opponents standing add..
Does this move remove a piece from the board add..
and whatever else you come up with... then perform the move with the best score. If there are a bunch of moves that are tied, just pick one randomly.
That will make an AI that can beat a person who is not familiar with the rules of the game... If you start recursively doing strategy like this, like not just this turn, but several turns out, you can make an expert game ai.
Chess Master 2000 was doing this way way way back in the day and utterly crushing me at Chess, don't worry about the cpu load here, because it looks like a lot from this side, but it is trivial... You are using more cpu load to render one of your game pieces...
The point is you want a stateless function, that returns the best/good enough move, no matter the state of the game board.
Also, remember for simple board games like this, you don't want an expert game system. You just want good enough. I quit playing Chess against computers BECAUSE I COULD NEVER EVER WIN NO MATTER HOW MUCH I TRIED!!!!! Your computer game is designed to entertain. Always losing is not entertaining. Buts thats me, thats why I don't like Casinos, I am smart enough to realize all the games are rigged against me.
Edit: sorta worked out some extra crappy grammar
#5
10/20/2011 (2:24 pm)
You know, I am looking for extra money right now... But I always feel craven asking for money. If you are doing a commercial game, and you want me to write you a solver for Senet, I will do it for like $100... Just the solver though.
#6
Well, it's not a commercial project. It's just a hobby. It's sort of my break into the Torque3D stuff. And looks good on a CV too. Who knows, with much polish maybe it can become comercial. My problem is lack of time and lack of T3D documentation in this area.
If it becomes something i'll give you a buzz, you seem very good at AI stuff.
It was a very good answer though. I'll do a little more research on client-server T3D architecture and will try to implement this in TorqueScript, although looks quite complex to be done in TorqueScript.
10/20/2011 (3:24 pm)
Thank you very much for the clarification.Well, it's not a commercial project. It's just a hobby. It's sort of my break into the Torque3D stuff. And looks good on a CV too. Who knows, with much polish maybe it can become comercial. My problem is lack of time and lack of T3D documentation in this area.
If it becomes something i'll give you a buzz, you seem very good at AI stuff.
It was a very good answer though. I'll do a little more research on client-server T3D architecture and will try to implement this in TorqueScript, although looks quite complex to be done in TorqueScript.
Associate Scott Burns
GG Alumni
All you need to do is create paths in your level and use each node as the space on the board. Use an AIPlayer for your game piece, spawn it on the path, and then use moveToNode() passing in the node (or "space") you want to move to.