  In Markov games, playing against non-stationary opponents with learning
ability is still challenging for reinforcement learning (RL) agents, because
the opponents can evolve their policies concurrently. This increases the
complexity of the learning task and slows down the learning speed of the RL
agents. This paper proposes efficient use of rough heuristics to speed up
policy learning when playing against concurrent learners. Specifically, we
propose an algorithm that can efficiently learn explainable and generalized
action selection rules by taking advantages of the representation of
quantitative heuristics and an opponent model with an eXtended classifier
system (XCS) in zero-sum Markov games. A neural network is used to model the
opponent from their behaviors and the corresponding policy is inferred for
action selection and rule evolution. In cases of multiple heuristic policies,
we introduce the concept of Pareto optimality for action selection. Besides,
taking advantages of the condition representation and matching mechanism of
XCS, the heuristic policies and the opponent model can provide guidance for
situations with similar feature representation. Furthermore, we introduce an
accuracy-based eligibility trace mechanism to speed up rule evolution, i.e.,
classifiers that can match the historical traces are reinforced according to
their accuracy. We demonstrate the advantages of the proposed algorithm over
several benchmark algorithms in a soccer and a thief-and-hunter scenarios.
