One optimization I think I see: You apply a heuristic by generating all replies for every single possible move. This is potentially a lot of wasted recursive effort, especially if the first solution we check is valid anyways. Just what I saw on sight read, I could very well be wrong. Otherwise it looks like a very clean recursive dfs implementation. Especially compared to my spaghetti-fied C-like abomination:
int checkBoard(const int current_player, const int player_count, int player_locations[], int board[16], int depth, Metric &metrics, bool outputResult = false)