Advice needed - AI for a graph game

Duc Ngo Minh · 2011-02-15T20:47:32

Hi, I'm new to AI game programming. I'm current need to make an AI game algorithm and is getting stuck and I'm really appreciate for advice from the experts here! I'm trying to use a general approach, so basically my game can be modelled as a graph. There are two players, the human player and the AI. Each step, each player choose an action, and the game state is changed to new one. The job of the AI is to assist the human player to get to the goal state. I need to develop an algorithm for the AI player. My current algorithm is to do an offline search to construct the whole game graph, and precompute the shortest distance from each state to the goal state. After that, the AI load the precomputed shortest distance table into memory, and each step, the AI player simply choose the action that leads to a state closest to the goal state. This method seems to work well, but the problem is that the graph gets bigger - it takes an extremely long time to precompute the shortest distance, and the table may even not fit in memory. I notice that not all the states in the game are actually needed - the set of states visited during a real game play is smaller. But I don't know how exactly to prune the search yet. One approach I could think of is to only learn the neccesary part of the graph, say through several game play between two human players; but I'm not sure if this can work. I'm new to AI game programming so I'm really appreciate if there are some techniques you can suggest to me, Thanks!

Artificial Intelligence Programming

Started by walrusvn February 14, 2011 03:20 PM

9 comments, last by Emergent 13 years, 9 months ago

Emergent

982

February 15, 2011 08:47 PM

I don't understand this: He has a specific starting configuration and we are suggesting that he run A* once to reach a goal configuration. What's wrong with that?

Agreed; nothing's wrong with that. My comment was about computing an entire policy offline; for that, running a brushfire-type algorithm once beats running A* O(n^2) times (which would do a lot of redundant work). It's not a super-profound observation, but I thought it might be worth mentioning since A* tends to get treated as a black box.

Advice needed - AI for a graph game

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Advice needed - AI for a graph game

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines