int search(Board b, int depth, Map<String, Integer> cache) throws Exception {
        if(depth<=0) {
        	return getHeuristic(b);
        }

        for (int col = 0; col < b.countCols(); ++col) {
            if (b.nextRow(col)>=0) {
                if (b.willWin(col, 4, 1)) {
                    return 10000;
                }
            }
        }

        int best = -1;
        int[] scores = new int[b.countCols()];
        for (int col = 0; col < b.countCols(); ++col) {
            scores[col] = -999;
            if (b.nextRow(col)>=0) {
                scores[col] = -search(b.withMove(col).invert(), depth-1, cache);
                if (best<0 || scores[col]>scores[best]) {
                    best = col;
                }
            }
        }

        if (best>=0) {
            return scores[best];
        }

        return 0;
    }