|
| Programme d'échecs C++ par Ka***st****11047 le
[Aller à la fin] |
| Informatique | |
Je recherche un programme d'échecs en C++ mais non compilé.
En effet, je souhaiterais analyser son code source et me donner de bonnes premières idées pour me lancer, éventuellement, sur un développement personalisé.
J'ai tout à fait conscience du volume de travail à mettre en oeuvre pour se lancer dans un tel projet.
D'ailleurs, j'ai déjà un peu d'expérience en matière de programmation de jeu. En 1982, j'ai développé un programme de reversi sur une HP41-CV qui avait fait une performance honorable dans un tournoi organisé par l'Ordinateur Individuel au SICOB (3/60).
Par avance merci à tous ceux qui pourront me donner une piste intéressante surt ce sujet.
|
|
|
en bas de ma page de liens
|
|
|
ref Katasstrov Si tu te sens capable de développer un programme d'echecs en c++ ou autre alors tu m'impressionne !
Je programme moi même en amateur et rien que de penser à la complexité algorythmique d'un tel programme:
Nombre de combinaisons et de dispositions possibles des pièces, calcul des positions sur plusieurs coups, évaluations de ses positions, choix de la meilleur option, mise en place d'une stratégie
etc.. tout cela donne le tourni !
ça doit vraiement être destiné à des
cracks, qu'en dis-tu ?
|
|
|
le nombre de combinaisons et de disposition des pièces n'a rien à voir avec la complexité de la programmation du jeu. En effet il existe un algorihtme generique (alpha-béta) pour explorer toutes les variantes possibles, dans la limite du temps et de la mémoire disponible bien sûr.
Bien sûr ce simple algo ne donnera pas un programme très fort à lui tout seul mais c'est la base.
|
|
|
Si tu veux des sources en C ou C++ Le mieux est de consulter les liens du fameux Winboard Forum :
http://f11.parsimony.net/forum16635/
(Tout en bas de la page..)
|
|
|
Liste de sources dispo.
Faile est très bien conçu & documenté. Gerbil également..
|
|
|
ref kolvir en fait d'après ce que tu dis, l'algorythme d'explorations et d'evaluations des variantes et des positions existe déja sous la forme d'un algorythme générique: Le programmeur qui souhaite développer un logiciel d'echecs n'a qu'a intégrer à son programme cet algorythme et y ajouter sa touche personnel.
Ok dans ce cas les choses sont beaucoup plus simple.Cependant on est en droit de se demander ce qui fait la différence entre Fritz et un logiciel ordinaire.Il doit certainement exister d'autre algorythme stratégique ou autre permettant d'améliorer le niveau et les performances de la machine.
|
|
|
Ref à tous Merci au fouduroi et à titus_inside pour vos liens.
Il y a effectivement beaucoup d'informations à exploiter même si les plus intéressantes semblent en anglais.
Pour répondre à Chesbord ...
J'ai sérieusement limité mes ambitions à tenter de déveloper un programme qui puisse déplacer ses pièces avec une analyse de profondeur exhaustive de 1 coup (je joue et il joue).Il faut procéder par étape.
Enfin, je pense qu'il est toujours possible d'apporter une touche personnel à l'algorythme d'analyse.
Lorsque j'avais développé mon programme de réversi, je m'étais apperçu que les coups qui réduisaient les possibilités de réponses adverses étaient généralement très forts. La pratique semblait mettre en évidence qu'ils primaient sur les coups ramassant plus de pions (début et millieu de parties). Je n'ai jamais pu démontrer théoriquement l'efficacité de ce système mais ca marchait.
|
|
|
ref kata bien vu pour ton programme de reversi en 82 car en effet l'heuristique qui consiste à resteindre la mobilité de l'adversaire à reversi est connue comme forte ! C'est pas mal du tout je trouve de l'avoir trouvé toi même même si je suis pas assez fort à othello pour juger.
ref chessbord
Il y a beaucoup de choses qui font la différence et notamment la qualité de la fonction d'évaluation d'une position.
|
|
|
ref Katasstrov Tu as raison en programmation comme dans d'autre domaines il faut procéder par étape, surtout pour un tel projet.
D'abord faire une maquette avec l'algorythme générique et quelques fonctionnalités de base.
Puis étudier en détail ce qui se fait à l'heure actuelle, essayer si possible d'y ajouter des solutions personnels.
(Ton critère d'évaluation de la force des coups semble intéressant.)
Passer de la phase d'analyse/conception à la phase de programmation
(+ biblio pour les ouvertures.)
Entammer après une longue phase de test
(Nombreuses parties de test dans différentes configurations, contre différents types de joueurs)
Bon courage
|
|
|
Une indication Je la tiens d'Amir Ban (le père des Junior ); il me dit dans un e-mail que depuis Junior5 l'algorithme de recherche n'a pas changé , et que toute la différence des versions ultérieures tient à la fonction d'évaluation , y compris le "génie" de Junior7
|
|
|
intéressant photophore je ne pensais pas que c'était à ce point ! Même pas de petites ruses du genre l'heuristique du coup meurtrier ou autre ! Bon ben ça veut dire que toutes ces "ruses " étaient dans junior 5 alors et que personne n'a trouvé utile d'améliorer l'ordre des noeuds examinés par exemple. Bon tu me diras si tu changes la fonction d'évaluation tu changes aussi cet ordre mais bon c'est intéressant comme info en tout cas.
|
|
|
precision pour chessbord l'algo de base est on ne peut plus bete du moins la version la plus simple : minimax. Tu explores tous les coups d'un noeud et tous les coups ici des ces coups etc. Ca te donne un arbre. Il faut se fixer une limite à la profondeur sinon aux echecs l'arbre est trop grand.
Sur les feuilles tu appliques la focntion d'évalution. Enuite tu remonte la note aux noeuds du haut : pour un noeud de profondeur paire (me premier est de profondeur 0) tu prends le max de la note des fils et pour un noeud impait le min. Arrivé au noeud du haut de l'arbre tu as donc non seulement une evalution de la position mais aussi le meilleur coup (le max).
Note : on prend le min au noeuds de profondeur impaire parce que l'adversaire cherche évidemment à faire baisser la note quand c'est lui qui joue ;o)
Alpha béta est une opitmisation de l'ago qui permet de ne pas tout explorer tout en obtenant le meme resultat.
|
|
|
merci pour la precision Une structure arborescente pour explorer les différentes variantes, la fonction d'évaluation pour évaluer la meilleure position.
Puis choix du premier coup qui donne le meilleur résultat en fin de variante (après exploration), variante contenant en plus les meilleurs coups joués de part et d'autre (ordi et adversaire).
C'est vrai que le gros du travail est déja fait, maintenant il faut trouver les bons critères d'evaluation pour la fonction.
|
|
|
autre C++ for Game Programmers
Author: Noel Llopis
Publisher: Charles River Media
ISBN: 1584502274
|
|
|
idée.. root = Tk()
#f=Frame() # dummy
photoimagenames = (
(free, "empty.gif"),
(pawn, "pawnw.gif"),
(knight, "knightw.gif"),
(bishop, "bishopw.gif"),
(rook, "rookw.gif"),
(queen, "queenw.gif"),
(king, "kingw.gif"),
(-pawn, "pawnb.gif"),
(-knight, "knightb.gif"),
(-bishop, "bishopb.gif"),
(-rook, "rookb.gif"),
(-queen, "queenb.gif"),
(-king, "kingb.gif")
)
photoimages = {}
for (piece, piecephotoname) in photoimagenames:
photoimages[piece] = PhotoImage(file=piecephotoname)
def formatTime(s):
minutes = int(s / 60.0)
sec = int(s - 60 * minutes)
return "%02d:%02d" % (minutes, sec)
def floatrange(start, end, step):
a = []
for i in range(int(((end - start) / step) + 1.5)):
a.append(start + i * step)
return a
class BoardUI:
def build(m):
global root
m.root = root
m.root.wm_title("pythonchess");
m.root.wm_iconname("chess");
m.mouseDownItem = None
m.mouseDownIndex = None
# m.time = [None, 300.0, 300.0]
m.timeItems = [None, None, None]
m.analysisItem = None
m.gameNameItem = "Initial board setup"
m.lastAnalysisTime = None
m.lastMoveTime = None
m.replayboard = None
m.searchDepth = 2
m.defaultPromotion = StringVar()
m.defaultPromotion.set('Q')
m.playboard = None
m.progressItem = None
m.progressRange = [0.0, 1.0]
m.progressVar = IntVar()
m.progressVar.set(1)
m.progressValue = 1
m.analysisVar = IntVar()
m.analysisVar.set(1)
m.analysisValue = 1
m.lastUserMove = 0
m.insidePonderingLoop = 0
m.boardOrientation = StringVar()
m.boardOrientation.set('white')
m.whiteDown = 1
m.slowmoveobject = None
m.slowmovetoix = None
m.automove = 1
m.stopRequest = 0
m.timeLeftBeforeLastMove = 0
m.realTurn = 1
m.moveNow = 0
m.userside = 1
m.controlDown = 0
m.filename = None
m.menu_main = Menu()
m.menu_file = Menu()
m.menu_edit = Menu()
m.menu_view = Menu()
m.menu_opponent = Menu()
m.menu_game = Menu()
m.menu_help = Menu()
m.menu_edit_promote = Menu()
m.menu_file.add_command(label="New", command=m.filenew, underline=0);
m.menu_file.add_command(label="Open...", command=m.fileopen, underline=0);
m.menu_file.add_command(label="Save", command=m.filesave);
m.menu_file.add_command(label="Save as...", command=m.filesaveas);
m.menu_file.add_separator();
m.menu_file.add_command(label="Exit", command=m.fileexit, underline=1);
m.menu_edit.add_command(label="Undo",
command=m.replayprevious, underline=0)
m.menu_edit.add_command(label="Replay", command=m.replaynext, underline=0)
m.menu_edit.add_command(label="Rewind", command=m.replaystart, underline=2)
m.menu_edit.add_separator();
m.menu_edit_promote.add_radiobutton(label="Queen", value='Q', variable=m.defaultPromotion)
m.menu_edit_promote.add_radiobutton(label="Rook", value='R', variable=m.defaultPromotion)
m.menu_edit_promote.add_radiobutton(label="Bishop", value='B', variable=m.defaultPromotion)
m.menu_edit_promote.add_radiobutton(label="Knight", value='N', variable=m.defaultPromotion)
m.menu_edit.add_cascade(label="Promotion", menu=m.menu_edit_promote, underline=0)
m.menu_view.add_checkbutton(label="Show Analysis", command=m.showAnalysis, variable=m.analysisVar);
m.menu_view.add_checkbutton(label="Show Progress", command=m.showProgress, variable=m.progressVar);
m.menu_view.add_separator()
m.menu_view.add_radiobutton(label="Normal Board - White Down", command=m.boardDir, value="white", variable=m.boardOrientation);
m.menu_view.add_radiobutton(label="Rotated Board - White Up", command=m.boardDir, value="black", variable=m.boardOrientation);
m.menu_main.add_cascade(label="File", menu=m.menu_file, underline=0)
m.menu_main.add_cascade(label="Edit", menu=m.menu_edit, underline=0)
m.menu_main.add_cascade(label="View", menu=m.menu_view, underline=0)
m.menu_main.add_cascade(label="Opponent", menu=m.menu_opponent, underline=0)
# m.menu_main.add_cascade(label="Game", menu=m.menu_game, underline=0)
# m.menu_main.add_cascade(label="Help", menu=m.menu_help, underline=0)
from chesspersonalities import persons
m.personName = StringVar()
for level in range(10):
for person in persons.keys():
if (persons[person].plys == level):
m.menu_opponent.add_radiobutton(label=person,
value=person, variable=m.personName,
command=(lambda x=person: m.SetOpponentName(x)))
m.personName.set("Guido")
m.root.configure(menu=m.menu_main);
m.canvas = Canvas()
m.canvas.after(1000, m.after1000)
m.canvasInfo = Canvas()
m.piecesOnCanvas = []
m.BuildCanvasGraphics()
m.infoMarginX = 0
m.infoMarginY = 10
m.infoCursorInc = 16
m.board = Board()
m.board.Setup()
m.canvasInfo["width"] = 160
m.canvasInfo["height"] = 480
m.canvasInfo["background"] = "white"
m.canvasInfo["highlightcolor"] = "white"
m.canvasInfo["highlightbackground"] = "white"
m.canvasInfo.pack(side=LEFT,expand=YES,fill=BOTH)
# GenerateAllLegalMoves(m.board)
m.SetOpponentName("Guido")
# m.CopyBoardToWindowGraphic()
m.UpdateInfo()
m.hashTable = HashTable()
m.hashTable.Init()
# m.PrepareForNextMoveWhenOpponentThinks()
m.replaystart()
def SlowMoveStart(m, fromix, toix):
m.UpdateProgress(1.0)
if m.slowmoveobject: # previous slow move is still going on, stop it
m.canvas.delete(m.slowmoveobject)
(m.slowmovestartx, m.slowmovestarty) = m.IndexToGraphicsPosition(fromix)
(m.slowmoveendx, m.slowmoveendy) = m.IndexToGraphicsPosition(toix)
m.slowmoveobject = m.piecesOnCanvas[fromix][0]
m.slowmovetoix = toix
m.slowmovefraction = 0.0
length = ((m.slowmovestartx - m.slowmoveendx) ** 2 +
(m.slowmovestarty - m.slowmoveendy) ** 2) ** 0.5
m.slowmovefractionincr = 0.02 + 0.1 ** (length / 150.0)
m.canvas.after(50, m.AfterSlowMoveStart)
m.canvas.tkraise(m.slowmoveobject)
if m.mouseDownItem == m.slowmoveobject:
m.mouseDownItem = None
m.mouseDownIndex = None
def AfterSlowMoveStart(m):
dx = m.slowmoveendx - m.slowmovestartx
dy = m.slowmoveendy - m.slowmovestarty
incr = m.slowmovefractionincr
if not m.insidePonderingLoop: # mate, move extra slow
incr = incr * 0.15
m.slowmovefraction = m.slowmovefraction + incr
if (m.slowmovefraction >= 1):
if (m.mouseDownIndex == m.slowmovetoix):
m.mouseDownIndex = None
m.mouseDownItem = None
m.canvas.delete(m.slowmoveobject)
m.slowmoveobject = None
m.slowmovetoix = None
m.CopyBoardToWindowGraphic()
m.UpdateProgress(None)
else:
m.canvas.tkraise(m.slowmoveobject)
from math import atan
scale = 6
a = 0.5 * atan((m.slowmovefraction - 0.5) * scale)/atan(scale*0.5) + 0.5
m.canvas.coords(m.slowmoveobject,
m.slowmovestartx + a * dx,
m.slowmovestarty + a * dy)
m.canvas.after(50, m.AfterSlowMoveStart)
def BuildCanvasGraphics(m):
m.canvas.delete("all")
m.xsize = 48
m.ysize = 48
m.canvas["width"] = 10 * m.xsize
m.canvas["height"] = 10 * m.ysize
m.canvas["background"] = "white"
m.canvas["highlightcolor"] = "white"
m.canvas["highlightbackground"] = "white"
m.canvas.create_rectangle(m.xsize-1, m.ysize-1, 9*m.xsize+1, 9*m.ysize+1,
fill="white", outline="black")
for i in range(m.xsize, 9 * m.xsize, 4):
m.canvas.create_line(i+1, m.ysize-1, m.xsize-1, i+1, fill="black")
m.canvas.create_line(9 * m.xsize+1, i-1, i-1, 9 * m.ysize+1, fill="black")
for column in range(1,9):
coltxt = repr(column)
if m.whiteDown:
coltxt = repr(9 - column)
m.canvas.create_text(m.xsize / 2, m.ysize * column + m.ysize / 2, text=coltxt)
for row in range(1,9):
rowtxt = " hgfedcba "[row]
if m.whiteDown:
rowtxt = " abcdefgh "[row]
m.canvas.create_text(m.xsize * row + m.xsize / 2, 9 * m.ysize + m.ysize / 2, text=rowtxt)
for column in range(10):
for row in range(10):
color = "white"
margin = None
if column == 0 or column == 9:
margin = "column"
margintext = " abcdefgh "[row]
if row == 0 or row == 9:
if margin == "column":
margin = "corner"
margintext = " "
else:
margin = "row"
margintext = repr(column)
if not margin and not (column + row) & 0x1:
rect = m.canvas.create_rectangle(
column * m.xsize, row * m.ysize,
column * m.xsize + m.xsize, row * m.ysize + m.xsize)
m.canvas.itemconfigure(rect, fill="white", outline="white")
if margin:
m.canvas.itemconfigure(rect, outline=color)
m.canvas.pack(side=LEFT,expand=YES,fill=BOTH)
m.canvas.bind('', m.mouseDown)
m.canvas.bind('', m.mouseMove)
m.canvas.bind('', m.mouseUp)
m.canvas.bind('', m.keyRelease)
m.canvas.bind('', m.keyPress)
m.canvas.focus_set()
def showAnalysis(m):
m.analysisValue = m.analysisVar.get
()
m.UpdateAnalysisString("")
def showProgress(m):
m.progressValue = m.progressVar.get()
|
|
|
Bon courage... C'est l'occasion pour relire "l'éloge de la fuite de Laborit".
|
|
|
source http://echecs-programmation.be/programmation.html
|
|
|
