@Override
    public int move(Board b) {
        double startTime = System.currentTimeMillis();

        int[] scores = new int[b.countCols()];
        Map<String, Integer> cache = new HashMap<String, Integer>(10000);

        try {
            // find all valid moves
            int best = -1;
            for (int col = 0; col < b.countCols(); ++col) {
                scores[col] = -999;
                if (b.nextRow(col)>=0) {
                    // take the winning move
                    if(b.willWin(col, 4, 1)) {
                        // System.out.println("Found a winning move at column " + col);
                        return col;
                    }

                    // minimax search
                    scores[col] = -search(b.withMove(col).invert(), mDepth*2-1, cache);
                    if (best<0 || scores[col]>scores[best]) {
                        best = col;
                    }
                }
            }

            // System.out.println(Arrays.toString(scores));
            // double finishTime = System.currentTimeMillis();
            // System.out.println("took " + (finishTime-startTime));

            ArrayList<Integer> moves = new ArrayList<Integer>();
            if (best>=0) {
                for (int col = 0; col < b.countCols(); ++col) {
                    if (scores[col]==scores[best]) {
                        moves.add(col);
                    }
                }

                return moves.get(mRandom.nextInt(moves.size()));
            }
        } catch (Exception e) {
            System.out.println("Exception!");
        }

        return mIdiot.move(b);
    }