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

        // if((mDepth*2-depth)<=cacheDepth) {
        //     String boardKey = b.toString();
        //     String otherKey = b.invert().toString();

        //     Integer cachedScore = null;
        //     if((cachedScore=cache.get(boardKey))!=null) {
        //         return  cachedScore;
        //     } else if((cachedScore=cache.get(otherKey))!=null) {
        //         return -cachedScore;
        //     }
        // }

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

        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) {
            // if((mDepth*2-depth)<=cacheDepth) {
            //     if(!cache.containsKey(b.toString()) && !cache.containsKey(b.invert().toString())) {
            //         cache.put(b.toString(), scores[best]);
            //     }
            // }

            return scores[best];
        }

        return 0;
    }