← Back to branch summary

~ubuntu-branches/ubuntu/precise/triplea/precise

« back to all changes in this revision

Viewing changes to src/games/strategy/common/player/ai/AIAlgorithm.java

  • Committer: Package Import Robot
  • Author(s): Scott Howard
  • Date: 2011-11-11 21:40:11 UTC
  • Revision ID: package-import@ubuntu.com-20111111214011-sehf2rwat36o2xqf
Tags: upstream-1.3.2.2
Import upstream version 1.3.2.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/games/strategy/common/player/ai/AIAlgorithm.java
 
1
/*
 
2
 * This program is free software; you can redistribute it and/or modify
 
3
 * it under the terms of the GNU General Public License as published by
 
4
 * the Free Software Foundation; either version 2 of the License, or
 
5
 * (at your option) any later version.
 
6
 * This program is distributed in the hope that it will be useful,
 
7
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
8
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
9
 * GNU General Public License for more details.
 
10
 * You should have received a copy of the GNU General Public License
 
11
 * along with this program; if not, write to the Free Software
 
12
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
13
 */
 
14
 
 
15
package games.strategy.common.player.ai;
 
16
 
 
17
import java.util.HashSet;
 
18
import java.util.Set;
 
19
import java.util.Stack;
 
20
 
 
21
/**
 
22
 * Utility class implementing AI game algorithms.
 
23
 *
 
24
 * Currently, minimax and alpha-beta algorithms are implemented.
 
25
 * 
 
26
 * @author Lane Schwartz
 
27
 * @version $LastChangedDate: 2008-01-05 06:33:48 +0800 (Sat, 05 Jan 2008) $
 
28
 * @see "Chapter 6 of Artificial Intelligence, 2nd ed. by Stuart Russell & Peter Norvig"
 
29
 */
 
30
public class AIAlgorithm
 
31
{
 
32
    
 
33
    public static <Play> Stack<Play> depthFirstSearch(GameState<Play> state, int maxDepth)
 
34
    {
 
35
       Stack<Play> stack = new Stack<Play>();
 
36
       try {
 
37
           if (state.gameIsOver())
 
38
           {
 
39
               //System.out.println("The given state is a solution!");
 
40
               return stack;
 
41
           }
 
42
           else
 
43
           {
 
44
               //System.out.println("Starting with " + state);
 
45
               Set<GameState<Play>> visitedStates = new HashSet<GameState<Play>>();
 
46
               visitedStates.add(state);
 
47
               return dfs(state, visitedStates, stack, 0, maxDepth);
 
48
           }
 
49
       } catch (StackOverflowError e) {
 
50
           return null;
 
51
       }
 
52
    }
 
53
 
 
54
    private static <Play> Stack<Play> dfs(GameState<Play> state, Set<GameState<Play>> visitedStates, Stack<Play> plays, int depth, int maxDepth)
 
55
    {
 
56
        
 
57
        int playsSoFar = plays.size();
 
58
        
 
59
        if (depth < maxDepth)
 
60
        {
 
61
            int childCounter = -1;
 
62
            
 
63
            // Find all of the possible next states
 
64
            for (GameState<Play> child : state.successors())
 
65
            {
 
66
                childCounter++;
 
67
                
 
68
                // Have we seen this child state before?
 
69
                if (! visitedStates.contains(child))
 
70
                {
 
71
                    //System.out.println("Considering child " + child + " #"+childCounter + " at depth " + depth + " created by move " + child.getMove());
 
72
                    
 
73
                    // Mark that we've now seen this child state
 
74
                    //System.out.println("We have now seen " + child + " at depth " + depth + " created by move " + child.getMove());
 
75
                    visitedStates.add(child);
 
76
 
 
77
                    // Is the child state a win state?
 
78
                    if (child.gameIsOver()) 
 
79
                    {
 
80
                        //System.out.println("Success! at level " + depth + " " + child);
 
81
                        plays.push(child.getMove());
 
82
                        return plays;
 
83
                    }
 
84
                    else 
 
85
                    {
 
86
                        plays = dfs(child, visitedStates, plays, depth+1, maxDepth);
 
87
                        if (plays.size() > playsSoFar)
 
88
                        {
 
89
                            //System.out.println("Pushing play at " + depth + " " + child);
 
90
                            plays.push(child.getMove());
 
91
                            return plays;
 
92
                        }
 
93
                    }
 
94
                }
 
95
               // else System.out.println("HAVE already seen " + child + " #"+childCounter + " now at depth " + depth+ " created by move " + child.getMove());
 
96
               
 
97
            }
 
98
        }
 
99
        return plays;
 
100
    }
 
101
    
 
102
    /**
 
103
     * Find the optimal next play to perform from the given game state, 
 
104
     * using the alpha-beta algorithm.
 
105
     * 
 
106
     * @param <Play> class capable of representing a game play
 
107
     * @param state current game state
 
108
     * @return the optimal next play
 
109
     */
 
110
    public static <Play> Play alphaBetaSearch(GameState<Play> state)
 
111
    {
 
112
        Pair<Float,Play> m = maxValue(state, Float.NEGATIVE_INFINITY, Float.POSITIVE_INFINITY);
 
113
        return m.getSecond();
 
114
 
 
115
    }
 
116
    
 
117
    
 
118
 
 
119
    private static <Play> Pair<Float,Play> maxValue(GameState<Play> state, float alpha, float beta)
 
120
    {
 
121
        float value = Float.NEGATIVE_INFINITY;
 
122
        Play bestMove = null;
 
123
        
 
124
        for (GameState<Play> s : state.successors())
 
125
        {   Play a = s.getMove();
 
126
            float minValue;
 
127
            if (s.cutoffTest())
 
128
                minValue = s.getUtility();
 
129
            else
 
130
                minValue = minValue(s, alpha, beta).getFirst();
 
131
            if (minValue > value)
 
132
            {
 
133
                value = minValue;
 
134
                bestMove = a;
 
135
            }
 
136
            if (value >= beta)
 
137
                return new Pair<Float,Play>(value,bestMove);
 
138
            if (value > alpha)
 
139
                alpha = value;
 
140
        }
 
141
        
 
142
        return new Pair<Float,Play>(value,bestMove);
 
143
    }
 
144
    
 
145
    
 
146
    private static <Play> Pair<Float,Play> minValue(GameState<Play> state, float alpha, float beta)
 
147
    {
 
148
        float value = Float.POSITIVE_INFINITY;
 
149
        Play bestMove = null;
 
150
        
 
151
        for (GameState<Play> s : state.successors())
 
152
        {   Play a = s.getMove();
 
153
            float maxValue;
 
154
            if (s.cutoffTest())
 
155
                maxValue = s.getUtility();
 
156
            else
 
157
                maxValue = maxValue(s, alpha, beta).getFirst();
 
158
            if (maxValue < value)
 
159
            {   
 
160
                value = maxValue;
 
161
                bestMove = a;
 
162
            }
 
163
            if (value <= alpha)
 
164
                return new Pair<Float,Play>(value,bestMove);
 
165
            if (value < beta)
 
166
                beta = value;
 
167
        }
 
168
        
 
169
        return new Pair<Float,Play>(value,bestMove);
 
170
    }
 
171
    
 
172
    
 
173
    
 
174
    
 
175
    /**
 
176
     * Find the optimal next play to perform from the given game state, 
 
177
     * using the minimax algorithm.
 
178
     * 
 
179
     * @param <Play> class capable of representing a game play
 
180
     * @param state current game state
 
181
     * @return the optimal next play
 
182
     */
 
183
    public static <Play> Play minimaxSearch(GameState<Play> state)
 
184
    {
 
185
        Pair<Float,Play> m = maxValue(state);
 
186
        return m.getSecond();
 
187
    }
 
188
    
 
189
    
 
190
    private static <Play> Pair<Float,Play> maxValue(GameState<Play> state)
 
191
    {
 
192
        float value = Float.NEGATIVE_INFINITY;
 
193
        Play bestMove = null;
 
194
 
 
195
        for (GameState<Play> s : state.successors())
 
196
        {   
 
197
            Play a = s.getMove();
 
198
            
 
199
            float minValue;
 
200
            if (s.gameIsOver())
 
201
                minValue = s.getUtility();
 
202
            else
 
203
                minValue = minValue(s).getFirst();
 
204
            
 
205
            
 
206
            if (minValue > value)
 
207
            {
 
208
                value = minValue;
 
209
                bestMove = a;
 
210
            }
 
211
        }
 
212
        
 
213
        return new Pair<Float,Play>(value,bestMove);
 
214
    }
 
215
    
 
216
    
 
217
 
 
218
    private static <Play> Pair<Float,Play> minValue(GameState<Play> state)
 
219
    {
 
220
        float value = Float.POSITIVE_INFINITY;
 
221
        Play bestMove = null;
 
222
 
 
223
        for (GameState<Play> s : state.successors())
 
224
        {   
 
225
            Play a = s.getMove();
 
226
            
 
227
            float maxValue;
 
228
            if (s.gameIsOver())
 
229
                maxValue = s.getUtility();
 
230
            else
 
231
                maxValue = maxValue(s).getFirst();
 
232
            
 
233
            if (maxValue < value)
 
234
            {   
 
235
                value = maxValue;
 
236
                bestMove = a;
 
237
            }
 
238
            
 
239
        }
 
240
        
 
241
        return new Pair<Float,Play>(value,bestMove);
 
242
    }
 
243
    
 
244
    
 
245
    
 
246
    
 
247
 
 
248
    static class Pair<First,Second> {
 
249
        private First m_first;
 
250
        private Second m_second;
 
251
        
 
252
        Pair(First first, Second second)
 
253
        {
 
254
            m_first = first;
 
255
            m_second = second;
 
256
        }
 
257
        
 
258
        First getFirst() { return m_first; }
 
259
        Second getSecond() { return m_second; }
 
260
    }
 
261
}