Nesse desafio, você recebe uma quantidade limitada de informações sobre um determinado jogo de xadrez e precisa prever quem ganhou o jogo .
Você recebe dois conjuntos de dados:
- Contagem de peças (que peças ainda estão vivas)
- Cores do quadro (a cor das peças no quadro)
Mais importante, você não sabe onde as peças estão localizadas . Você precisa determinar quem você acha que vai ganhar.
Os jogos são selecionados de todos os eventos listados no PGNMentor de 2010 até agora. Selecionei 10% de todas as posições do tabuleiro de cada jogo que termina em uma vitória ou uma derrota. As posições no tabuleiro sempre terão pelo menos 30 jogadas no jogo. Os casos de teste podem ser encontrados aqui . (Vitórias brancas são listadas primeiro, seguidas por vitórias pretas)
Entrada
A contagem de peças será uma sequência de caracteres para cada peça: k
ing, q
ueen r
, ok n
, b
kight, ishop ou p
awn. Minúsculas significa preto, maiúsculas é branco. O quadro terá uma sequência de 64 caracteres (8 linhas por 8 colunas). B
representa uma peça preta, W
representa uma peça branca e .
representa um ponto vazio. Amostra:
W..WB......W.BB....W..B..W.WWBBB..W...B....W..BBWWW...BB.W....B.,BBKPPPPPPPQRRbbkpppppppqrr
representaria o seguinte quadro
...B.BB.
.BBBBBBB
.B.B....
B..W....
WWWW.W..
....W.W.
...W..WW
W.....W.
e onde ambas as cores têm 2 Bispos, 1 Rei, 7 Peões, 1 Rainha, 2 Torres
Resultado
Você precisa retornar um número de ponto flutuante entre 0 e 1 (inclusive) para determinar a probabilidade de vitória das brancas. Amostra:
0.3 (30% chance that white wins)
Mais detalhes:
- Cada caso de teste vale 1 ponto. Sua pontuação será
1 - (1-Output)^2
se o branco vencer ou1 - (Output)^2
se o preto vencer. - Sua pontuação final será a soma de todos os casos de teste.
- Se sinto que os envios estão codificando a entrada, reservo-me o direito de alterar os casos de teste. (Se eu alterá-los, eles terão o hash SHA-256
893be4425529f40bb9a0a7632f7a268a087ea00b0eb68293d6c599c6c671cdee
) - Seu programa deve executar casos de teste de forma independente. Nenhuma informação de salvamento de um caso de teste para o próximo.
- Se você estiver usando aprendizado de máquina, recomendo o treinamento nos primeiros 80% dos dados e o teste nos 20% restantes . (Ou qualquer porcentagem usada). Uso os jogos várias vezes nos dados, mas montei os mesmos jogos sequencialmente.
- ATUALIZAÇÃO: adicionei mais de um milhão de casos de teste para fins de teste e aprendizado. Eles são divididos em partes em preto e branco devido aos limites de tamanho de repositório do github.
Boa sorte e divirta-se!
fonte
Respostas:
Java 8 + Weka, 6413 pontos, 94,5%
Esta resposta usa uma abordagem de aprendizado de máquina. Você precisa recuperar a biblioteca Weka , principalmente
weka.jar
ePackageManager.jar
.Aqui, eu uso um perceptron multicamada como classificador; você pode substituir
mlp
por qualquerClassifier
classe de Weka para comparar resultados.Não brinquei muito com os parâmetros do MLP e simplesmente olhei para eles (uma camada oculta de 50 neurônios, 100 épocas, 0,2 taxa de aprendizado, 0,1 momento).
Eu limito o valor de saída do MLP, para que a saída seja realmente 1 ou 0, conforme definido no desafio. Dessa forma, o número de instâncias classificadas corretamente, impressas por Weka, é diretamente nossa pontuação.
Construção de vetor de recurso
Viro cada instância de uma string para um vetor de 76 elementos, em que:
1
é uma peça branca,-1
é uma peça preta e0
é uma célula vazia.0
sendo "nenhuma peça desse tipo"). Pode-se aplicar a normalização para reajustar esses valores entre -1 e 1, mas isso provavelmente não é muito útil aqui.Número de instâncias de treinamento
Se eu usar todos os casos de teste fornecidos para treinar meu classificador, consegui obter 6694 (ou seja, 98,6588%) instâncias classificadas corretamente . Obviamente, isso não é surpreendente, porque testar um modelo com os mesmos dados que você usou para treiná-lo é muito fácil (porque, nesse caso, é realmente bom que o modelo se ajuste demais).
Usando um subconjunto aleatório de 80% das instâncias como dados de treinamento, obtemos a figura de 6413 (ou seja, 94,5173%) instâncias classificadas corretamente relatadas no cabeçalho (é claro que, como o subconjunto é aleatório, você pode obter resultados ligeiramente diferentes). Estou confiante de que o modelo funcionaria decentemente bem em novos dados, porque o teste nos 20% restantes das instâncias (que não foram usadas para treinamento) fornece 77,0818% de classificação correta, o que mostra que os modelos generalizam decentemente bem (assumindo a os casos que recebemos aqui são representativos dos novos casos de teste que receberíamos).
Usando metade das instâncias para treinamento e a outra metade para teste, obtemos 86,7502% nos dados de treinamento e teste e 74,4988% apenas nos dados de teste.
Implementação
Como eu disse, esse código requer
weka.jar
ePackageManager.jar
da Weka.Pode-se controlar a porcentagem de dados usados no conjunto de treinamento
TRAIN_PERCENTAGE
.Os parâmetros do MLP podem ser alterados logo abaixo
TRAIN_PERCENTAGE
. Pode-se tentar outros classificadores de Weka (por exemplo,SMO
para SVMs) simplesmente substituindomlp
por outro classificador.Esse programa imprime em conjuntos de resultados, sendo o primeiro em todo o conjunto (incluindo os dados usados para treinamento), que é a pontuação definida neste desafio, e o segundo sendo apenas nos dados que não foram usados para treinamento.
Um insere os dados passando o caminho do arquivo que os contém como argumento para o programa.
fonte
GNU sed + bc,
43365074,5 pontos,6475%Atualização: o OP forneceu uma nova maneira de calcular a pontuação da previsão para um caso de teste individual. Usando Wolfram Alpha , plotei os dois conjuntos de fórmulas para ver as diferenças.
A maneira atual traz um forte incentivo para gerar probabilidades reais, e não apenas os extremos 0 e 1, para os quais as novas fórmulas dão a mesma pontuação máxima de antes. É por isso que o algoritmo inalterado abaixo agora tem uma melhor taxa de previsão, de fato uma grande taxa, dada sua simplicidade.
No entanto, também há uma desvantagem associada às novas fórmulas, conforme explicado em 'Editar 1'.
Essa é uma estimativa simples baseada apenas na vantagem / desvantagem do material, ignorando a colocação real das peças. Fiquei curioso para saber como isso funcionaria. A razão pela qual uso sed, e não uma linguagem que possa fazer isso em uma linha, é porque é a minha linguagem esotérica favorita.
Valores padrão da peça usados:
Calculo o material dos dois lados e subtraio o material preto do branco. A saída para cada caso de teste é baseada nessa diferença da seguinte maneira:
Esta é a minha única saída fracionada, daí o motivo da melhoria, conforme explicado acima.
A taxa de previsão para este método foi de 64%. Agora são 75% com as novas fórmulas.
Editar 1: a desvantagem
A solução trivial é produzir 0,5 para cada caso de teste, pois dessa forma você pontuou meio ponto, independentemente de quem ganhou. Para nossos casos de teste, isso significou uma pontuação total de 3392,5 pontos (50%).
Mas com as novas fórmulas, 0,5 (que é um resultado que você daria se não souber quem vence) é convertido em 0,75 pontos. Lembre-se de que a pontuação máxima que você pode receber para um caso de teste é 1, para 100% de confiança no vencedor. Assim, a nova pontuação total para uma saída constante de 0,5 é 5088,75 pontos, ou 75%! Na minha opinião, o incentivo é muito forte para este caso.
Essa pontuação é melhor, embora marginalmente, do que o meu algoritmo baseado em vantagens materiais. A razão para isso é porque o algoritmo fornece uma probabilidade de 1 ou 0 (sem incentivo), vitórias ou perdas presumidas, mais vezes (3831) do que 0,5 (incentivo), empates assumidos (2954). O método é simples no final e, como tal, não possui uma alta porcentagem de respostas corretas. O aumento da nova fórmula para constante 0,5 consegue atingir artificialmente essa porcentagem.
Edição 2:
É um fato conhecido, mencionado nos livros de xadrez, que geralmente é melhor ter um par de bispos do que um par de cavaleiros. Isso é especialmente verdadeiro no estágio intermediário ao final do jogo, onde estão os casos de teste, pois é mais provável que haja uma posição aberta onde o alcance de um bispo é aumentado.
Por isso, fiz um segundo teste, mas desta vez substituí o valor dos bispos de 3 para 3,5. O valor do cavaleiro permaneceu 3. Essa é uma preferência pessoal, por isso não fiz a minha submissão padrão. A pontuação total neste caso foi de 4411 pontos (65%). Apenas um aumento de 1 ponto percentual foi observado.
Com as novas fórmulas, a pontuação total é de 4835 pontos (71%). Agora, o bispo ponderado tem um desempenho inferior. Mas, o efeito é explicado porque o método ponderado agora oferece ainda mais vezes ganhos ou perdas presumidos (5089) do que empates assumidos (1696).
fonte
Python 3 - 84,6%, 5275 pontos em um conjunto de validação
Se enganarmos e usarmos todos os dados, podemos alcançar uma precisão de 99,3% e uma pontuação de 6408
Apenas um MLP grande e simples com desistência usando Keras
fonte
Python 3 - precisão de 94,3%, 6447 pontos em um conjunto de validação de 20% dos dados
Usa 3 redes neurais, um regressor de vizinhos mais próximos, uma floresta aleatória e aumento de gradiente. Essas previsões são combinadas com uma floresta aleatória que também tem acesso aos dados.
fonte
Python 3 - 4353,25 / 6785 pontos - 64%
Então, eu trabalhei nisso principalmente ontem. Meu primeiro post de golfe, e só uso python há uma semana, então me perdoe se nem tudo estiver otimizado.
Acabei no mesmo caminho que a resposta de seshoumara para começar. Mas o grande número de casos de teste que tinham contagens de peças me deixou insatisfeito.
Por isso, pesquisei no Google traços que determinam quem está ganhando no xadrez (eu não jogo) e notei que a posição do tabuleiro, especificamente o controle central, é grande. É aí que entra essa parte.
As duas metades combinadas são usadas para encontrar a pontuação (0,0, 0,25, 0,50, 0,75, 1,0)
Muito interessante que essa posição extra no tabuleiro não pareça aumentar a chance de adivinhar o vencedor.
Se você soltar os casos de teste em alguns arquivos, aqui está o teste.
Sei que este não é um desafio de golfe, mas qualquer dica ou conselho a esse respeito é apreciado!
fonte