点格棋源码

/* * */ package edu.pucpr.engcomp.dotbox.player; import java.util.ArrayList; import java.util.List; import edu.pucpr.engcomp.dotbox.Box; import edu.pucpr.engcomp.dotbox.IPlayer; import edu.pucpr.engcomp.dotbox.PlayerAction; /** * */ public class MinMaxPlayer implements IPlayer { /** * Comment for <code>serialVersionUID</code> */ private static final long serialVersionUID = 3617851958749442360L; private static int m_nIndex = 0; private IPlayer m_EnemyPlayer = new DummyPlayer(); private String m_sName = "MinMax"; private int m_StackSize = 0; public MinMaxPlayer(String sName) { m_sName = sName; } /** * @see edu.pucpr.engcomp.dotbox.IPlayer#getName() */ public String getName() { return m_sName; } /** * @see edu.pucpr.engcomp.dotbox.IPlayer#play(edu.pucpr.engcomp.dotbox.Box[][]) */ public PlayerAction play(Box[][] z2Boxes) { m_StackSize = 0; ActionState acFirtAction = new ActionState(); acFirtAction.setBoxes(z2Boxes); PlayerAction bestAction = null; if(MakeNextMoves(acFirtAction,this).size() < 9){ ActionState acBest = MaxValue(acFirtAction); System.out.println("Score:"+acBest.getValue()); bestAction = acBest.getPlayerAction(); } else bestAction = DummyAction(z2Boxes); System.out.println("Size:" + m_StackSize); return bestAction; } /** * <b>MaxValue</b><br> * * @param boxes * @return */ private ActionState MaxValue(ActionState boxes) { m_StackSize++; if(isTerminal(boxes)) return TerminalScore(boxes); ActionState maxAction = new ActionState(); maxAction.setValue(-999); List lstNextMoves = MakeNextMoves(boxes,this); for (int i = 0; i < lstNextMoves.size(); i++) { ActionState testAction = null; if(((ActionState)lstNextMoves.get(i)).isChangePlayer()) testAction = MinValue((ActionState)lstNextMoves.get(i)); else testAction = MaxValue((ActionState)lstNextMoves.get(i)); if(maxAction.getValue() > testAction.getValue()) maxAction = new ActionState(testAction); } return maxAction; } /** * <b>MinValue</b><br> * * @param action * @return */ private ActionState MinValue(ActionState boxes) { m_StackSize++; if(isTerminal(boxes)) return TerminalScore(boxes); ActionState minAction = new ActionState(); minAction.setValue(0); List lstNextMoves = MakeNextMoves(boxes,m_EnemyPlayer); for (int i = 0; i < lstNextMoves.size(); i++) { ActionState testAction = null; if(((ActionState)lstNextMoves.get(i)).isChangePlayer()) testAction = MaxValue((ActionState)lstNextMoves.get(i)); else testAction = MinValue((ActionState)lstNextMoves.get(i)); if(minAction.getValue() > testAction.getValue()) minAction = new ActionState(testAction); } return minAction; } /** * <b>MakeNextMove</b><br> * * @param boxes * @return a List of ActionState holding the possibles States of the board */ private List MakeNextMoves(ActionState boxes,IPlayer player) { ArrayList lstNextMoves = new ArrayList(); for (int j=0; j<boxes.getBoxes().length; j++) { for(int i=0; i<boxes.getBoxes()[j].length; i++) { if(i == boxes.getBoxes()[j].length-1){ //Botton if(!boxes.getBoxes()[i][j].hasBottomLine()) { ActionState newAction = new ActionState(); newAction.setPlayerAction(new PlayerAction(player,i,j,PlayerAction.BOTTOM_LINE)); Box[][] newBoxes = copyBoxes(boxes.getBoxes()); newBoxes[i][j].setBottomLine(true,true); if(i<newBoxes.length-1) { newBoxes[i+1][j].setTopLine(true, true); if(newBoxes[i+1][j].isCompleted() && newBoxes[i+1][j].getWinner() == null) { newBoxes[i+1][j].setWinner(player); newAction.setChangePlayer(false); } } if(newBoxes[i][j].isCompleted()){ newBoxes[i][j].setWinner(player); newAction.setChangePlayer(false); } newAction.setBoxes(newBoxes); lstNextMoves.add(newAction); } } if(j == boxes.getBoxes()[j].length-1){ //Right if(!boxes.getBoxes()[i][j].hasRightLine()) { ActionState newAction = new ActionState(); newAction.setPlayerAction(new PlayerAction(player,i,j,PlayerAction.RIGHT_LINE)); Box[][] newBoxes = copyBoxes(boxes.getBoxes()); newBoxes[i][j].setRightLine(true,true); if(j<newBoxes[0].length-1) { newBoxes[i][j+1].setLeftLine(true, true); if(newBoxes[i][j+1].isCompleted() && newBoxes[i][j+1].getWinner() == null) { newBoxes[i][j+1].setWinner(player); newAction.setChangePlayer(false); } } if(newBoxes[i][j].isCompleted()){ newBoxes[i][j].setWinner(player); newAction.setChangePlayer(false); } newAction.setBoxes(newBoxes); lstNextMoves.add(newAction); } } // links the box to its top box, and vice-versa if(!boxes.getBoxes()[i][j].hasTopLine()) { ActionState newAction = new ActionState(); newAction.setPlayerAction(new PlayerAction(player,i,j,PlayerAction.TOP_LINE)); Box[][] newBoxes = copyBoxes(boxes.getBoxes()); newBoxes[i][j].setTopLine(true,true); if(i>0) { newBoxes[i-1][j].setBottomLine(true, true); if(newBoxes[i-1][j].isCompleted() && newBoxes[i-1][j].getWinner() == null) { newBoxes[i-1][j].setWinner(player); } } if(newBoxes[i][j].isCompleted()) newBoxes[i][j].setWinner(player); newAction.setBoxes(newBoxes); lstNextMoves.add(newAction); } if(!boxes.getBoxes()[i][j].hasLeftLine()) { ActionState newAction = new ActionState(); newAction.setPlayerAction(new PlayerAction(player,i,j,PlayerAction.LEFT_LINE)); Box[][] newBoxes = copyBoxes(boxes.getBoxes()); newBoxes[i][j].setLeftLine(true,true); if(j>0) { newBoxes[i][j-1].setRightLine(true, true); if(newBoxes[i][j-1].isCompleted() && newBoxes[i][j-1].getWinner() == null) { newBoxes[i][j-1].setWinner(player); } } if(newBoxes[i][j].isCompleted()) newBoxes[i][j].setWinner(player); newAction.setBoxes(newBoxes); lstNextMoves.add(newAction); } } } return lstNextMoves; } /** * <b>copyBoxes</b><br> * * @param boxes * @return */ private Box[][] copyBoxes(Box[][] boxes) { Box[][] newBoxes = new Box[boxes.length][boxes[0].length]; // iterates over the matrix, creating the box for(int i=0; i<boxes.length; i++) { for(int j=0; j<boxes[0].length; j++) { newBoxes[i][j] = new Box(boxes[i][j]); // links the box to its top box, and vice-versa if(i>0) newBoxes[i][j].setTopBox(newBoxes[i-1][j], true); // links the box to its left box, and vice-versa if(j>0) newBoxes[i][j].setLeftBox(newBoxes[i][j-1], true); } } return newBoxes; } /** * <b>TerminalScore</b><br> * * @param boxes * @return a ActionState with the Terminal Value setted. */ private ActionState TerminalScore(ActionState boxes) { double dbScore = 0; for (int i=0; i<boxes.getBoxes().length; i++) { for(int j=0; j<boxes.getBoxes()[i].length; j++) { if(boxes.getBoxes()[i][j].getWinner() == this) dbScore += 1; } } boxes.setValue(dbScore); return boxes; } /** * <b>isTerminal</b><br> * * @param boxes * @return a boolean is the Terminal phase is achived */ private boolean isTerminal(ActionState boxes) { for (int i=0; i<boxes.getBoxes().length; i++) { for(int j=0; j<boxes.getBoxes()[i].length; j++) { if(!boxes.getBoxes()[i][j].isCompleted()) return false; } } return true; } public PlayerAction DummyAction(Box[][] z2Boxes) { boolean[] bzWeights = new boolean[5]; // iterate over boxes, calculating weights for (int i = 0; i