Take the 2-minute tour ×

I am designing a SDL game where the player(human) can place nets on a N*M grid such that each net covers a single element of the grid only (There are N*M elements/cells on the grid). Now in each round of the game (the game currently has 10 rounds ),the player can place nets on the grid by purchasing nets with each net costing NetCost (which is subtracted from the player's score) in order to catch balls falling. Also the player can move move the nets at start of any round to a cell/element sharing an edge (ie up,down,left,right). Now balls fall in each round (each round is instantaneous theoritically although in the visuals of the game it lastss 2 seconds) The players's nets catch these balls such that a net placed at a cell catches all balls that fell at that particular cell. For each ball missed there is a penalty on the score B. The player starts with a fixed score. The computer player and human player play the same round separately such that choices made by human player don't affect computer player and vice versa.
Now I have to design an efficient computer player for single player mode .The computer player will also start from the same score as the human player. The purpose of the computer player is to get maximum score possible on the same grid using the same nets available to the user. These inputs to the computer player will be the balls falling in each round R at the starting of the round R along with their grid location. How can I design an efficient computer player for this game?

Note the grid size is constant for each round and is 30x30. The starting score is fixed at 100,000 for both players.However net cost and the ball drop penalty maybe chosen by the user at the start of the game ie before round 1 .These costs remain constant for all the rounds The number of nets may be limited to lets say 200 for each round. I am not sure what algorithm I can apply here. Can someone please guide me in the right direction?

share|improve this question
could you clarfify where do the balls drop? Can a player predict where the balls will be? –  Bartlomiej Lewandowski Mar 27 '13 at 22:06
The balls would drop on the cells of the grid.For purpose of the game,the cells are point sized objects (that is ball may drop anywhere inside the cell ,result is same if a net is there on the cell ,the net will catch it else the player's score will be penalized).The computer player would know where the balls would drop as I mentioned in the question . But the human player won't know . –  user1907531 Mar 27 '13 at 22:10
If the computer knows where all the balls will drop, it can just put its nets there, right? That would give it the "maximum score possible" although it wouldn't be much fun to play against... –  Thomas Mar 27 '13 at 22:11
@Thomas:There is a cost for placing the net which can lower the score of the computer player.So in some cases it will be better to let the balls drop –  user1907531 Mar 27 '13 at 22:13
Then we need to know the way the score and cost are computed in order to say anything about this. –  Thomas Mar 27 '13 at 22:14
show 5 more comments

2 Answers

It sounds like this is a turn-based game. If so, you'll want to look into minimax search possibly with alpha-beta pruning (which is a search space-optimization that doesn't change the outcome of minimax but only speeds it up - in some cases significantly).

This needs to be paired with an evaluation function that determines how good or bad a given position is for a player. This part sounds like it would be fairly easy for a game like this.

share|improve this answer
Sir have you noted the fact that computer player knows the ball locations for the immediately next round only? –  user1907531 Mar 27 '13 at 22:16
Actually, I missed that but I think you may still be able to utilize minimax to have your AI play strategically well by using a probability (rather than certainty) that a ball will fall at a particular spot now or later. –  500 - Internal Server Error Mar 27 '13 at 22:21
Sir ,I am not sure how I can apply minimax here.Can you give a small example how to take the probability of the ball falling over a particular element/cell and how to decide when to buy the nets and whether or not they should be moved? –  user1907531 Mar 27 '13 at 22:23
I would have to study your pre-reqs in more detail to give more precise guidance. –  500 - Internal Server Error Mar 28 '13 at 0:52
add comment

Sounds like you need a course in A.I. Check out this game to help you figure out advanced A.I. responses: http://www.transience.com.au/pearl.html

Incorporate a randomness and degree of difficulty to the computer player. Have him respond under ideal circumstances.

share|improve this answer
add comment

Your Answer


