Existe-t-il un moteur d'échecs qui n'utilise PAS la recherche par force brute?

Chaque moteur d'échecs dont j'ai jamais entendu parler (y compris tout ce que j'ai trouvé sur Wikipédia) utilise la recherche par force brute avec une fonction d'évaluation (algorithme minmax) pour décider de son déplacement.

Ce n'est pas ainsi que la plupart des humains abordent le jeu, en utilisant plutôt la reconnaissance générale des formes, donc en principe, il serait possible pour les ordinateurs de faire de même.

Existe-t-il un moteur d'échecs qui ne repose pas sur l'approche par force brute pour trouver ses mouvements?

Il y a eu des tentatives dans les années 1980 d'écrire des moteurs d'échecs avec des bases de connaissances qui permettraient de sélectionner des mouvements candidats comme les humains, mais ils ont échoué. Le problème est que l'appariement des formes humaines est difficile à mettre en mots, il était donc extrêmement difficile de créer les règles de la base de connaissances.

La formation d'un réseau de neurones pour sélectionner les mouvements candidats semble être une piste de recherche prometteuse. Ici et ici, il pourrait y avoir deux articles pertinents. (FWIW, ce n'est pas mon domaine de Comp Sci)

Vous pourriez jeter un oeil à Giraffe qui était récemment dans les nouvelles:

https://thestack.com/iot/2015/09/14/neural-network-chess-computer-abandons-brute-force-for-selective-human-approach/

Le battage médiatique est qu'en 3 jours, il a appris le jeu lui-même et a atteint le niveau IM. D'un autre côté, la recherche est

http://arxiv.org/abs/1509.01549

Je voudrais ajouter des détails à la réponse de @ Ian_Bush sur Giraffe.

Dans la réponse de @ Ian_Bush, il est à noter que Giraffe n'utilise pas de calcul par force brute. Ce n'est pas vrai , car Giraffe est toujours un moteur alpha-bêta (nega-max). La seule différence avec un moteur standard est que la fonction d'évaluation est réglée automatiquement par apprentissage en profondeur. Par conséquent, le moteur apprend à jouer seul.

Traditionnellement, le programmeur de moteur règle automatiquement les paramètres d'un moteur. J'ai beaucoup fait moi-même. Par exemple, combien de poids devriez-vous donner à un évêque et à un chevalier? 3.0? 3.1? 3.2? C'est difficile à dire.

La girafe aborde le problème de manière beaucoup plus intelligente. Il commence par quelques valeurs initiales. Le moteur utilise l'algorithme de montée en gradient pour régler ces valeurs. Nous n'avons pas à coder explicitement le poids d'une reine dans le code. C'est ce que nous voulons dire "apprendre". Cela ne signifie pas que le moteur peut jouer aux échecs sans chercher.

EDIT : Giraffe modélise les nœuds des arbres comme probabilité qu'ils tombent dans la variation principale. Vérifiez le papier pour plus de détails. Personnellement, je ne crois pas cette approche, et le document montre peu de preuves de son utilité.

Son genre de discutable si vous pouvez appeler une recherche basée sur l'heuristique et évaluer l'approche comme force brute. La plupart des moteurs d'échecs de haut niveau suivent aujourd'hui une approche basée sur des règles pour évaluer une position et une fonction de recherche basée sur des règles pour élaguer les mouvements.

Ce n'est en fait pas garanti de choisir le mouvement "optimal global", mais ces mouvements sont assez bons pour le but. En ce sens, la plupart des moteurs d'échecs utilisent une approximation de l'optimum global et s'en tirent réellement.

À ce jour, nous n'avons pas beaucoup de moteurs d'échecs qui réussissent au plus haut niveau en utilisant une approche différente, du moins pas sur du matériel bon marché.

Claude Shannon a proposé deux types d'algorithmes pour créer des moteurs d'échecs. Un moteur de "type A" examine tous les mouvements possibles jusqu'à une profondeur finie, minimise l'arbre, puis joue le mouvement avec l'évaluation la plus élevée de l'arbre minimaxé (alias force brute). Les moteurs de type B limitent leur recherche à un sous-ensemble de mouvements possibles en fonction de certains critères. Je pensais qu'il préférait le type B comme plus prometteur.

Les moteurs qui ont été créés dans les années 1970 (par exemple, Hitech, Kaissa) avaient tendance à être de la force brute pure sans élagage ou simplement alpha-bêta, mais les gens ont rapidement vu la valeur de l'élagage de l'arbre des mouvements et des lignes qui ne se révélaient probablement pas solides . Presque tous les moteurs récents élaguent l'arbre des lignes qui sont clairement plus faibles (alpha-bêta), et la plupart des moteurs utilisent également divers types d'élagage vers l'avant (futilité, réduction des mouvements tardifs, mouvement nul, rasage). En ce sens, il n'y a plus beaucoup de moteurs qui utilisent la force brute pure.

Dans les années 1970, Botvinnik travaillait sur un moteur appelé Pioneer conçu autour de la notion de voies d'attaque qui aurait été guidée par l'évaluation. Il n'a jamais atteint le point où il pouvait jouer une partie complète d'échecs.

Dans les années 1990, Chris Wittington s'est prononcé en faveur de l'utilisation de plus de connaissances sur les échecs et a créé un programme appelé Chess System Tal qui était assez solide pour l'époque.

Kasparov, Anand et Tord Romstad ont tous noté que Hiarcs semble avoir une évaluation plus détaillée que la plupart des principaux moteurs dont la force provient d'une recherche rapide.

Fondamentalement, tous!

Les moteurs d'échecs n'utilisent vraiment la force brute que lorsque:

• a dit à
• analysent des positions (résolution de problèmes)
• À la recherche d'un échec et mat (résolution de problèmes, pas en jouant contre, comme des problèmes de type «trouver le partenaire en N»)

Sinon, ils ont une "recherche sélective", cela considérera tous les mouvements possibles pour une disposition de tableau donnée, mais n'en explorera qu'une poignée. Un moteur peut passer en force brute s'il évalue deux mouvements de manière très similaire (plus d'un coup fort) ou s'il ne trouve pas un coup qu'il aime (pas de coups forts).

Ils ont également tendance à utiliser la force brute comme dernière ligne de défense, si vous avez vu un échec et mat, il peut le voir arriver et il voudra vraiment essayer de dessiner, et ne peut pas trouver d'issue (l'effet "Horizon" "est un problème avec les moteurs, supposons qu'il va perdre sa reine, et qu'il a été limité à seulement 4 jeux de profondeur; s'il peut échanger des pions et reporter cette perte de la reine pour 4 mouvements, il pensera qu'il a sauvé la reine" , dans le processus, il perdra au moins 1 pion (car le prochain mouvement rapproche l'horizon d'avant) et le poids qu'il accorde au sauvetage de la reine peut signifier qu'il sacrifie une défense, pour rien si la mort passe à l'horizon) .

Il utilisera également la force brute lorsque la recherche sélective n'est pas très utile. C'est pourquoi les moteurs prennent plus de temps quand il leur reste 3 pièces. Ils doivent forcer la force parce que l'algorithme de sélection ne peut pas évaluer un mouvement. L'algorithme de sélection est excellent pendant le milieu de partie car il peut être comme "Oohh, faire cela avec le pion bloque son [quoi] et sauvegarde mes [quoi] et [quoi] que j'ai un nombre moindre à défendre qu'à attaquer" - par exemple .

Si vous avez un roi au milieu du plateau il y a 8 coups, la recherche sélective sera comme "Aucun de ceux-ci ne fait rien d'utile, je ne peux pas le dire".

Vous pouvez considérer la recherche sélective comme ayant deux parties, elle est tactique dans le sens où elle essaiera de repérer les mouvements tactiques, elle ignorera le poids des pièces impliquées généralement parce qu'une reine qui ne fait partie d'aucune stratégie ne vaut pas plus qu'un pion qui lui est vital. Il est également stratégique dans la mesure où il explorera les mouvements qui renforcent une défense et s'ouvrira plus tard à des attaques potentielles.

Le moteur fait alors la même chose de votre point de vue, et d'avant en arrière et d'avant en arrière.

Ce que l'on appelle un tableau de transposition est une grande liste de choses auxquelles il a pensé, de cette façon s'il finit par considérer quelque chose qu'il a déjà fait, il le sait et n'a pas à le réévaluer.

À MOINS (sélectif :)), il y arrive d'une manière différente, ou veut explorer davantage. Supposons par exemple qu'il découvre que votre ... tour est essentielle à une attaque imminente, le moteur peut réévaluer une ligne lorsqu'il le découvre. Le poids qu'il a accordé à cette tour (par exemple, 5 points, à quel point c'est important pour vous) pourrait être une sous-estimation.

La recherche sélective peut également revenir en arrière, comme par exemple en considérant un évêque se déplaçant directement en territoire ennemi, pour le sélecteur de mouvement, il n'est pas important qu'elle puisse être prise facilement. Disons qu'il découvre que stratégiquement c'est un superbe mouvement! Il peut ensuite revenir en arrière pour essayer de trouver un moyen de protéger cette place pour y amener cet évêque. Supposons que cela implique un pion.

La méthode de la force brute considérerait la ligne impliquant ce mouvement de pion, et (par force brute) l'évêque se déplace aussi, et le même truc qui évalue la position du plateau (la recherche sélective elle-même) dira "c'est bien" donc le plateau taux qui varient fortement, les deux le trouvent.

Il est très difficile d'évaluer une position en utilisant la méthode de la force brute, c'est pourquoi la recherche sélective fonctionne si bien.

La force brute de la position de départ pourrait trouver ce célèbre compagnon en 4 qui implique une reine f7 couverte par un évêque, et si elle devait donner une note aussi élevée (J'AI TROUVÉ UN CHECKMATE! JOB DONE! PLAY!) serait faux parce que le noir va évidemment contrer. La recherche sélective évalue un poste (pour une évaluation plus approfondie) car il semble être bon. Cela signifie que lorsqu'il examine votre réponse, il peut décider de ce qui serait bon pour vous ....

Donc, le truc que la recherche sélective utilise pour évaluer les choses est de toute façon utilisé par la force brute parce que "trouvé un échec et mat impliquant ce mouvement" ne suffit pas pour dire que le mouvement est bon.

Par conséquent Quels sont les premiers mouvements choisis (blanc), par les moteurs d'échecs de force brute?