Costumo utilizar outra tecnica para esse tipo de situacao: a ideia consistem em nao trabalhar diretamente com o Graphics do Componente, mas sim, ter uma copia , como um atributo de classe, de um outro Graphics, com as mesmas dimensoes/propriedades
Ai toda a alteracao eh feita nessa copia. O metodo paint, no caso, passa a ser uma simples copia do Graphics copia para o Graphis que vem pelo metodo paint.
Na pratica, deste modo, o metodo paint soh eh chamado quando ocorre eventos de minimizar/maximizar, ou se voce bota outra janela em cima do seu programa java e depois tira.
Ai quando voce muda a posicao de uma peca no tabuleiro, redesenhe o seu Graphics copia e copie ele para o graphics quente(usando o getGraphics). Voce podera entao arrancar todos os repaints do codigo. Alem disso, voce nao precisa copiar TODO o graphics copia para o graphics quente, voce pode monitorar somente as areas alteradas e copiar somente pedacos, o que economiza processamento.
Esse eh um motivo que eu acho que Applets nao deram certo. O pessoal programava muito mal com eles, nao otimizavam. Com esses tipos de otimizacao lerdiums 200, 300 podem rodar aplicacoes java e applets muito bem.