22 users logged in
Proud partner of GDC 2025
Before posting, review our community guidelines.
Support GameDev.net with a monthly GDNet+ subscription!
Infection AI
March 04, 2009 09:22 PM
Does anyone know if there's any such site that has the best move choices for the game infection. If you don't know what infection is, it's a 2 player game usually on a grid that's 7 by 7 and each player gets 2 pieces to start out with on opposite corners of the gird. The object of the game is to either eliminate all your players pieces or have the most squares at the end. The way you move each turn is either take one piece and move 1 space which duplicates your piece or jump 2 spaces and lose your current piece. The AI I'm trying to develop needs to be smart enough to never lose the game against it's opponent or atleast tie. I've looked all over but haven't been able to find anything on best moves :/
Unity3D Tutorials with free scripts! https://www.youtube.com/JesseEtzler0
21,610
March 04, 2009 10:31 PM
After looking around the web for a while, it looks like the game you are talking about is more commonly known as Attax. There is a Java implementation here.
What you are trying to do is weakly solving the game. The game seems a bit on the large side for this to be feasible.
I would start building a traditional alpha-beta program to play it. It you get it to be fast enough, you might be able to use it to solve the game.
What you are trying to do is weakly solving the game. The game seems a bit on the large side for this to be feasible.
I would start building a traditional alpha-beta program to play it. It you get it to be fast enough, you might be able to use it to solve the game.
March 05, 2009 11:08 AM
Well thanks for finding more information than I could. The game right now is a completed version written in c# and there are seperate .cs files for you to plug your ai into. Right now it's just a simple dummy AI but I need to tweak it to be a game winning AI. I guess I'll just keep searching a little bit more.
Unity3D Tutorials with free scripts! https://www.youtube.com/JesseEtzler0
122
March 05, 2009 01:56 PM
You could try using a minimax algorithm to estimate the best move to make. This is the way most chess AI systems work. It works by generating a tree of all possible moves, where each node on the tree has an estimated score of how well each player is doing. As the tree expands, moves alternate between players. You then pick the moves which ultimately maximize your score whilst minimizing your opponents. You could estimate how well a player is doing by the number of squares they have occupied.
The wikipedia page has a more detailed overview:
http://en.wikipedia.org/wiki/Minimax
and this page looks helpful too:
http://www.aihorizon.com/essays/basiccs/trees/minimax.htm
You may also wish to use alpha beta pruning which effectively prunes areas of the tree and makes your algorithm more efficient.
Hope that helps!
The wikipedia page has a more detailed overview:
http://en.wikipedia.org/wiki/Minimax
and this page looks helpful too:
http://www.aihorizon.com/essays/basiccs/trees/minimax.htm
You may also wish to use alpha beta pruning which effectively prunes areas of the tree and makes your algorithm more efficient.
Hope that helps!
---Current project: Warring States, an RTS gamehttp://warring-states.blogspot.com/
March 13, 2009 02:06 PM
I'm still having an issue with how the AI is working and am not sure what I'm doing wrong :/ I've tried countless times to try and come up with a way to set this up so it works right with no success. What I origonaly planned on doing was setting up another public static int which would go through the different moves and either add or subtract a number depending on how good it is at the time. In the end I don't really have a clue how to setup so my code will run through the array of possible moves and pick the best one. Could anyone show me how to setup the basic skeleton for finding and calculating a best move.
Here's my code so far.
Here's my code so far.
using System;using System.Collections;using System.Collections.Generic;using System.Linq;using System.Text;namespace InfectionGUIv2{ class ExampleAI { protected static void getLegalMoves(int[,] board, int playerToMove, int i, int j, ref ArrayList a) { GameBoard myB = new GameBoard(board); Dictionary<string, int> tempD; // test 24 possible moves, simulate move for each if legal, record info for (int c1 = i - 2; c1 <= i + 2; c1++) { for (int c2 = j - 2; c2 <= j + 2; c2++) { if (myB.isLegalMove(playerToMove, c1, c2, i, j)) { GameBoard tempB = new GameBoard(myB.getBoard()); tempB.makeMove(playerToMove, c1, c2, i, j); tempD = new Dictionary<string, int>(); tempD.Add("fromX", i); tempD.Add("fromY", j); tempD.Add("toX", c1); tempD.Add("toY", c2); tempD.Add("pieces1", tempB.getNumPieces(1)); tempD.Add("pieces2", tempB.getNumPieces(2)); a.Add(tempD); } } } } protected static ArrayList getMyPieceCoords(int playerToMove, int[,] board) { ArrayList a = new ArrayList(); for (int i = 0; i < 7; i++) { for (int j = 0; j < 7; j++) { if (board[i, j] == playerToMove) { getLegalMoves(board, playerToMove, i, j, ref a); } } } return a; } public static int calcMove(int[,] board, int playerToMove, out int fromY, out int toX, out int toY) { ArrayList myMoves = getMyPieceCoords(playerToMove, board); int bestMove = 100; int bestIndex = 0; if (myMoves.Count > 0) { Dictionary<string, int> myD; for (int i = 0; i < myMoves.Count; i++) { myD = (Dictionary<string, int>)myMoves; if (playerToMove == 1) { if (myD["pieces1"] > bestMove) { bestMove = myD["pieces1"]; bestIndex = i; } } } myD = (Dictionary<string, int>)myMoves[bestIndex]; fromY = myD["fromY"]; toX = myD["toX"]; toY = myD["toY"]; return myD["fromX"]; } else { fromY = -1; // values indicating you want to PASS toX = -1; toY = -1; return -1; } } public static int bestPossibleMove(int[,] board, int playerToMove, out int fromY, out int toX, out int toY) { } }}Unity3D Tutorials with free scripts! https://www.youtube.com/JesseEtzler0
179
March 16, 2009 09:40 PM
Quote:
Original post by JesseEtzlerCould anyone show me how to setup the basic skeleton for finding and calculating a best move.
Did you look at those algorithms you were recommended? Your answer lies therein.
All you really need to figure out is how to score a position in this game. The rest is just implementation and, given the popularity of minmax algorithms, you should be able to get tons of code samples.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
Recommended Tutorials
Advertisement