Menu
This is a question I have been toying with for a week or so, proposed by a colleague:
Imagine a game played on a 36x36 grid. The goal of the game is to create four corners of a square of any size (eg., 2x2, 3x3, 4x4, and so on). The first player places a game-piece anywhere except the center four grid spaces. After the first move, players can place their game-piece anywhere on the grid. Game-pieces cannot be moved after they are placed. And that's it; The game is simple and fun.
I have been trying to come up with an algorithm to win, or at least do well at this game. Any suggestions?
886
Pathfinding and Movement are used to move an agent in a game world. Pathfinding algorithms are used for the high level planning; reactive movement algorithms are used between the waypoints marked by the pathfinding algorithm.
Pathfinding, another common use for AI, is widely seen in real-time strategy games. Pathfinding is the method for determining how to get a NPC from one point on a map to another, taking into consideration the terrain, obstacles and possibly "fog of war".
Every time a computer-controlled character moves, it does so in response to the instructions of a steering algorithm, a series of mathematical steps which reads the state of the game, calculates the position of each element, and translates that into an instruction to move in a particular direction.
The most common search technique in game playing is Minimax search procedure. It is depth-first depth-limited search procedure. It is used for games like chess and tic-tac-toe. Minimax algorithm uses two functions – MOVEGEN : It generates all the possible moves that can be generated from the current position.
This is a game of perfect information where players take turns, like chess, so the same approach used in chess engines applies here. Use a minimax (with alpha-beta pruning probably) algorithm to search the tree of valid moves. You can use some evaluation function to guide your search, favoring positions that have the most almost-completed squares.
97
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
