generating game tree
I try to write a MinMax program in Java for connect-four game, but this program should also be applicable to other games. But, I encountered a problem, which I cannot pass for few days. The values for nodes are not set properly. I am sharing my piece of code which is responsible for generating a tree.
Maybe you will notice where I made a mistake.
If anyone could help me with this, I will be very happy.
public Node generateTree(Board board, int depth) {
Node rootNode = new Node(board);
generateSubtree(rootNode, depth);
minMax(rootNode, depth);
return rootNode;
}
private void generateSubtree(Node subRootNode, int depth) {
Board board = subRootNode.getBoard();
if (depth == 0) {
subRootNode.setValue(board.evaluateBoard());
return;
}
for (Move move : board.generateMoves()) {
Board tempBoard = board.makeMove(move);
Node tempNode = new Node(tempBoard);
subRootNode.addChild(tempNode);
generateSubtree(tempNode, depth - 1);
}
}
public void minMax(Node rootNode, int depth) {
maxMove(rootNode, depth);
}
public int maxMove(Node node, int depth) {
if (depth == 0) {
return node.getValue();
}
int bestValue = Integer.MIN_VALUE;
for (Node childNode : node.getChildren()) {
int tempValue = minMove(childNode, depth - 1);
childNode.setValue(tempValue);
if (tempValue > bestValue) {
bestValue = tempValue;
}
}
return bestValue;
}
public int minMove(Node node, int depth) {
if (depth == 0) {
return node.getValue();
}
int bestValue = Integer.MAX_VALUE;
for (Node childNode : node.getChildren()) {
int tempValue = maxMove(childNode, depth - 1);
childNode.setValue(tempValue);
if (tempValue < bestValue) {
bestValue = tempValue;
}
}
return bestValue;
}
Board class is the representation of the board state.
Move class hold the move to perform (integer [0-8] for tic-tac-toe, [0-6] for Connect Four).
Node class holds the Move and value how good given move is. Also, holds all its children.
In the code I use this method like this:
Node newNode = minmax.generateTree(board, depth, board.getPlayer());
Move newMove = new TicTacToeMove(board.getPlayer(), newNode.getBestMove().getMove(), depth);
board = board.makeMove(newMove);
And when it's obvious that given move is a losing move (or winning), I do not receive this move.
Alright, you did make a couple of mistakes. About 3-4, depending on how you count ;) Took me a bit of debugging to figure it all out, but I finally got an answer for you :D
Mistake #1: All your parents always get twins (that poor mother)
This is only the case with the code you uploaded, not the code in your question, so maybe we count it as half a mistake? Since your trees aren't that big yet and it won't destroy your algorithm, this was the least important one anyway. Still, it's something to watch out for. In your uploaded code, you do this in your generateSubtree method:
Node tempNode = new Node(tempBoard, move, subRootNode);
subRootNode.addChild(tempNode);
As that constructor already adds the child to the subRootNode, the second line always adds it a second time.
Mistake #2: That darn depth
If you haven't reached your desired depth yet, but the game is already decided, you completely ignore that. So in your provided example that won't work, if - for example - you look at making move 7 instead of 3 (which would be the 'right' move) and then the opponent does move 3, you don't count it as -10 points because you haven't reached your depth yet. It still won't get any children, so even in your minmax, it will never realize it's a screwed up way to go.
Which is why every move is 'possible' in this scenario and you just get the first one returned.
In the previous moves, there was luckily always a way to reach a losing move with your opponents third move (aka move #5), which is why those were called correctly.
Alright, so how do we fix it?
private void generateSubtree(Node subRootNode, int depth, int player) {
Board board = subRootNode.getBoard();
List<Move> moveList = board.generateMoves();
if (depth == 0 || moveList.isEmpty()) {
subRootNode.setValue(board.evaluateBoard(player));
return;
}
for (Move move : moveList) {
Board tempBoard = board.makeMove(move);
Node tempNode = new Node(tempBoard, move, subRootNode);
generateSubtree(tempNode, depth - 1, player);
}
}
Just get the move list beforehand and then look if it's empty (your generateMoves() method of the Board class (thank god you provided that by the way ;)) already checks if the game is over, so if it is, there won't be any moves generated. Perfect time to check the score).
Mistake #3: That darn depth again
Didn't we just go over this?
Sadly, your Min Max algorithm itself has the same problem. It will only even look at your values if you have reached the desired depth. You need to change that.
However, this is a bit more complicated, since you don't have a nice little method that already checks if the game is finished for you.
You could check to see if your value was set, but here's the problem: It might be set to 0 and you need to take that into account as well (so you can't just do if (node.getValue() != 0) ).
I just set the initial value of each node to -1 instead and did a check against -1 . It's not... you know... pretty. But it works.
public class Node {
private Board board;
private Move move;
private Node parent;
private List<Node> children = new ArrayList<Node>();;
private boolean isRootNode = false;
private int value = -1;
...
And this in the maxMove :
public int maxMove(Node node, int depth) {
if (depth == 0 || node.getValue() != -1) {
return node.getValue();
}
int bestValue = Integer.MIN_VALUE;
for (Node childNode : node.getChildren()) {
int tempValue = minMove(childNode, depth - 1);
childNode.setValue(tempValue);
if (tempValue > bestValue) {
bestValue = tempValue;
}
}
return bestValue;
}
It works the same for minMove of course.
Mistake #4: The player is screwing with you
Once I changed all that, it took me a moment with the debugger to realize why it still wouldn't work.
This last mistake was not in the code you provided in the question btw. Shame on you! ;)
Turns out it was this wonderful piece of code in your TicTacToeBoard class:
@Override
public int getPlayer() {
// TODO Auto-generated method stub
return 0;
}
And since you called
MinMax minmax = new MinMax();
Node newNode = minmax.generateTree(board, (Integer) spinner.getValue(), board.getPlayer());
in your makeMove method of TicTacToeMainWindow , you would always start out with the wrong player.
As you can probably guess yourself, you just need to change it to:
public int getPlayer() {
return this.player;
}
And it should do the trick.
Also:
Just a couple of things I'd like to remark at this point:
Clean up your imports! Your TicTacToe actually still imports your ConnectFour classes! And for no reason.
Your board is rotated and mirrored in your board array. WHY? You know how annoying that is to debug? I mean, I guess you probably do :D Also, if you're having problems with your code and you need to debug it's extremely helpful to overwrite your boards toString() method, because that will give you a very nice and easy way to look at your board in the debugger. You can even use it to rotate it again, so you see don't have to look at it lying on the side ;)
While we're at the subject of the board... this is just me but... I always tried clicking on the painted surface first and then had to remember: Oh yeah, there were buttons :DI mean... why not just put the images on the buttons or implement a MouseListener so you can actually just click on the painted surface?
When providing code and/or example images, please take out your test outputs. I'm talking about the Player 1 won! s of course ;)
Please learn what a complete, verifiable and minimal example is for the next time you ask a question on StackOverflow. The one in your question wasn't complete or verifiable and the one you provided on github was... well... not complete (the images were missing), but complete enough. It was also verifiable, but it was NOT minimal. You will get answers a LOT sooner if you follow the guidelines.
上一篇: Minimax算法井字中间状态
下一篇: 生成游戏树