![[Jenkins]](/jenkins/static/67fda021/images/svgs/logo.svg){kind=logo}
Package: VierConnectsMinimaxStrategy
VierConnectsMinimaxStrategy
| name | instruction | branch | complexity | line | method | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| VierConnectsMinimaxStrategy(VierConnectsMoveFactory) |
|
|
|
|
|
||||||||||||||||||||
| computeNextMove(int, VierConnectsPlayer, VierConnectsState, long) |
|
|
|
|
|
||||||||||||||||||||
| evaluate(VierConnectsState, VierConnectsPlayer, int) |
|
|
|
|
|
||||||||||||||||||||
| evaluateDiagonals(VierConnectsBoard, VierConnectsFieldState, boolean) |
|
|
|
|
|
||||||||||||||||||||
| evaluateDirection(VierConnectsBoard, VierConnectsFieldState, boolean) |
|
|
|
|
|
||||||||||||||||||||
| evaluateWindow(VierConnectsFieldState[], VierConnectsFieldState) |
|
|
|
|
|
||||||||||||||||||||
| getOpponent(VierConnectsFieldState) |
|
|
|
|
|
||||||||||||||||||||
| getOpponent(VierConnectsState) |
|
|
|
|
|
||||||||||||||||||||
| getPossibleMoves(VierConnectsState) |
|
|
|
|
|
||||||||||||||||||||
| lambda$evaluateWindow$0(VierConnectsFieldState, VierConnectsFieldState) |
|
|
|
|
|
||||||||||||||||||||
| lambda$evaluateWindow$1(VierConnectsFieldState, VierConnectsFieldState) |
|
|
|
|
|
||||||||||||||||||||
| lambda$evaluateWindow$2(VierConnectsFieldState) |
|
|
|
|
|
||||||||||||||||||||
| orderMoves(List) |
|
|
|
|
|
||||||||||||||||||||
| toString() |
|
|
|
|
|
||||||||||||||||||||
Coverage
1: package de.fhdw.gaming.ipspiel24.VierConnects.strategy.minimax;
2:
3: import java.util.ArrayList;
4: import java.util.Arrays;
5: import java.util.List;
6: import java.util.Optional;
7:
8: import de.fhdw.gaming.core.domain.GameException;
9: import de.fhdw.gaming.ipspiel24.VierConnects.core.domain.VierConnectsBoard;
10: import de.fhdw.gaming.ipspiel24.VierConnects.core.domain.VierConnectsFieldState;
11: import de.fhdw.gaming.ipspiel24.VierConnects.core.domain.VierConnectsPlayer;
12: import de.fhdw.gaming.ipspiel24.VierConnects.core.domain.VierConnectsPosition;
13: import de.fhdw.gaming.ipspiel24.VierConnects.core.domain.VierConnectsState;
14: import de.fhdw.gaming.ipspiel24.VierConnects.core.domain.VierConnectsStrategy;
15: import de.fhdw.gaming.ipspiel24.VierConnects.core.moves.VierConnectsMove;
16: import de.fhdw.gaming.ipspiel24.VierConnects.core.moves.factory.VierConnectsMoveFactory;
17: import de.fhdw.gaming.ipspiel24.minimax.Minimax;
18: import de.fhdw.gaming.ipspiel24.minimax.MinimaxStrategy;
19:
20: /**
21: * Minimax Strategy for VierConnects.
22: */
23: public class VierConnectsMinimaxStrategy implements VierConnectsStrategy,
24: MinimaxStrategy<VierConnectsPlayer, VierConnectsState, VierConnectsMove> {
25:
26: /**
27: * the moveFactory.
28: */
29: private final VierConnectsMoveFactory moveFactory;
30:
31: /**
32: * maxDepth of Search Tree.
33: */
34: private final int maxDepth = 5;
35:
36: /**
37: * multiplier for centre positions.
38: */
39: private final int scoreCenterCountMultiplier = 2;
40:
41: /**
42: * score for player evaluation: win.
43: */
44: private final int scoreWin = 999999;
45:
46: /**
47: * score for player evaluation: 3 in a row and 1 empty.
48: */
49: private final int score3Row = 100;
50:
51: /**
52: * score for player evaluation: 2 in a row and 2 empty.
53: */
54: private final int score2Row = 50;
55:
56: // these need to be positive numbers, as they get subtracted from the score.
57: /**
58: * score for enemy evaluation: win.
59: */
60: private final int scoreLose = 99999;
61:
62: /**
63: * score for enemy evaluation: 3 in a row and 1 empty.
64: */
65: private final int score3RowEnemy = 100;
66:
67: /**
68: * constructor.
69: *
70: * @param moveFactory public moveFactory.
71: */
72: public VierConnectsMinimaxStrategy(VierConnectsMoveFactory moveFactory) {
73: this.moveFactory = moveFactory;
74: }
75:
76: @Override
77: public Optional<VierConnectsMove> computeNextMove(int gameId, VierConnectsPlayer player, VierConnectsState state,
78: long maxComputationTimePerMove) throws GameException, InterruptedException {
79: // long startTime = System.nanoTime(); //left these in case i want to measure time again for something
80: final VierConnectsPlayer opponent = this.getOpponent(state);
81: final Minimax<VierConnectsPlayer, VierConnectsState,
82: VierConnectsMove> minimax = new Minimax<VierConnectsPlayer, VierConnectsState, VierConnectsMove>(this,
83: this.maxDepth, opponent);
84: final VierConnectsMove bestMove = minimax.getBestMove(state, player);
85: // long endTime = System.nanoTime();
86: // System.out.print((endTime - startTime) + ";");
87: return Optional.of(bestMove);
88: }
89:
90: @Override
91: public List<VierConnectsMove> getPossibleMoves(VierConnectsState state) {
92:
93: final List<VierConnectsMove> possibleMoves = new ArrayList<>();
94: final VierConnectsBoard board = state.getBoard();
95:• for (int i = 0; i < board.getColumnSize(); i++) {
96: final VierConnectsPosition pos = VierConnectsPosition.of(0, i);
97:• if (board.getFieldAt(pos).getState() == VierConnectsFieldState.EMPTY) {
98: possibleMoves.add(moveFactory.createPlaceMarkMove(
99: state.getCurrentPlayer().isUsingCrosses(), i));
100: }
101: }
102:
103: return orderMoves(possibleMoves);
104: }
105:
106: /**
107: * takes possibleMoves in a List and orders it to start from the middle.
108: * e.g.: 0,1,2,3,4,5,6,7 -> 3,4,2,5,1,6,0,7
109: * (prioritise better Moves for more effective alpha- beta-pruning)
110: *
111: * @param possibleMoves list of ordered possibleMoves left to right
112: * @return new ordered list of possible Moves starting from the beginning.
113: */
114: private List<VierConnectsMove> orderMoves(List<VierConnectsMove> possibleMoves) {
115: final List<VierConnectsMove> orderedMoves = new ArrayList<>(possibleMoves.size());
116: final int middle = possibleMoves.size() / 2;
117:
118:• for (int i = 0; i < possibleMoves.size(); i++) {
119:• final int index = middle + (i % 2 == 0 ? i / 2 : -(i / 2 + 1));
120: orderedMoves.add(possibleMoves.get(index));
121: }
122:
123: return orderedMoves;
124: }
125:
126: /**
127: * evaluates window of four positions and gives score for 2,3,4 in a row.
128: * also gives bas score for good opponent position.
129: *
130: * @param window array of four fields (the state of the fields)
131: * @param playerState the state of the player that is using minimax
132: * @return score of window.
133: */
134: @SuppressWarnings("checkstyle:CyclomaticComplexity")
135: private int evaluateWindow(VierConnectsFieldState[] window, VierConnectsFieldState playerState) {
136: int score = 0;
137:
138: final VierConnectsFieldState opponent = this.getOpponent(playerState);
139:
140:• final long playerCount = Arrays.stream(window).filter(p -> p == playerState).count();
141:• final long opponentCount = Arrays.stream(window).filter(p -> p == opponent).count();
142:• final long emptyCount = Arrays.stream(window).filter(p -> p == VierConnectsFieldState.EMPTY).count();
143:
144:• if (playerCount == 4) {
145: score += this.scoreWin;
146:• } else if (playerCount == 3 && emptyCount == 1) {
147: score += this.score3Row;
148:• } else if (playerCount == 2 && emptyCount == 2) {
149: score += this.score2Row;
150: }
151:
152:• if (opponentCount == 4) {
153: score -= this.scoreLose;
154:• } else if (opponentCount == 3 && emptyCount == 1) {
155: score -= this.score3RowEnemy;
156: }
157:
158: return score;
159: }
160:
161: /**
162: * returns a score for all rows or columns.
163: *
164: * @param board board Board of the current State that gets evaluated.
165: * @param playerState State of the current Player
166: * @param isColumn boolean whether rows or columns get evaluated.
167: * @return score for all rows or columns
168: */
169: private int evaluateDirection(VierConnectsBoard board, VierConnectsFieldState playerState, boolean isColumn) {
170: int score = 0;
171:• final int primarySize = isColumn ? board.getColumnSize() : board.getRowSize();
172:• final int secondarySize = isColumn ? board.getRowSize() : board.getColumnSize();
173:
174:• for (int primary = 0; primary < primarySize; primary++) {
175: final VierConnectsFieldState[] array = new VierConnectsFieldState[secondarySize];
176:• for (int secondary = 0; secondary < secondarySize; secondary++) {
177:• final VierConnectsPosition position = isColumn ? VierConnectsPosition.of(secondary, primary)
178: : VierConnectsPosition.of(primary, secondary);
179: array[secondary] = board.getFieldAt(position).getState();
180: }
181:• for (int secondary = 0; secondary < secondarySize - 3; secondary++) {
182: final VierConnectsFieldState[] window = Arrays.copyOfRange(array, secondary, secondary + 4);
183: score += evaluateWindow(window, playerState);
184: }
185: }
186:
187: return score;
188: }
189:
190: /**
191: * returns a score for all (positive or negative) diagonal positions.
192: *
193: * @param board Board of the current State that gets evaluated.
194: * @param playerState State of the current Player
195: * @param isPositiveSlope boolean whether the negative or positive slopes get evaluated.
196: * @return score for positive or negative positions.
197: */
198: private int evaluateDiagonals(VierConnectsBoard board, VierConnectsFieldState playerState,
199: boolean isPositiveSlope) {
200: int score = 0;
201: final int rowSize = board.getRowSize();
202: final int columnSize = board.getColumnSize();
203:
204:• for (int r = 0; r < rowSize - 3; r++) {
205:• for (int c = 0; c < columnSize - 3; c++) {
206: final VierConnectsFieldState[] window = new VierConnectsFieldState[4];
207:• for (int i = 0; i < 4; i++) {
208:• if (isPositiveSlope) {
209: window[i] = board.getFieldAt(VierConnectsPosition.of(r + i, c + i)).getState();
210: } else {
211: window[i] = board.getFieldAt(VierConnectsPosition.of(r + 3 - i, c + i)).getState();
212: }
213: }
214: score += evaluateWindow(window, playerState);
215: }
216: }
217:
218: return score;
219: }
220:
221: @Override
222: public int evaluate(VierConnectsState state, VierConnectsPlayer player, int depth) {
223: int score = 0;
224:
225: final VierConnectsBoard board = state.getBoard();
226: final int columnSize = board.getColumnSize();
227: final int rowSize = board.getRowSize();
228:• final VierConnectsFieldState playerState = player.isUsingCrosses() ? VierConnectsFieldState.CROSS
229: : VierConnectsFieldState.NOUGHT;
230:
231: // score for middle position
232: int centerCount = 0;
233:• for (int r = 0; r < rowSize; r++) {
234:• if (board.getFieldAt(VierConnectsPosition.of(r, columnSize / 2)).getState() == playerState) {
235: centerCount++;
236: }
237: }
238: score += centerCount * this.scoreCenterCountMultiplier;
239: // score for depth
240: score += this.maxDepth - depth;
241:
242: // Evaluate columns
243: score += evaluateDirection(board, playerState, true);
244:
245: // Evaluate rows
246: score += evaluateDirection(board, playerState, false);
247:
248: // Evaluate positive sloped diagonals
249: score += evaluateDiagonals(board, playerState, true);
250:
251: // Evaluate negative sloped diagonals
252: score += evaluateDiagonals(board, playerState, false);
253:
254: return score;
255: }
256:
257: @Override
258: public VierConnectsPlayer getOpponent(VierConnectsState state) {
259:• return state.getCurrentPlayer() == state.getCrossesPlayer()
260: ? state.getNoughtsPlayer()
261: : state.getCrossesPlayer();
262: }
263:
264: /**
265: * returns the opponent FieldState for a given VierConnectsFieldState.
266: *
267: * @param state FieldState of the current Player.
268: * @return opposite State of the given fieldState.
269: */
270: public VierConnectsFieldState getOpponent(VierConnectsFieldState state) {
271:• return state.equals(VierConnectsFieldState.CROSS) ? VierConnectsFieldState.NOUGHT
272: : VierConnectsFieldState.CROSS;
273: }
274:
275: @Override
276: public String toString() {
277: return "Vier-Gewinnt Minimax Strategy";
278: }
279:
280: }