Ok, zoals de topic titel al aangeeft betreft het hier huiswerk, toch hoop ik dat mensen bereid zijn om te helpen.
[opdracht]
Het is de bedoeling om een 4opeenrij spel te maken met een computertegenstander die enige vorm van AI heeft. De zetten van de computer moeten dus niet compleet random zijn.
[status]
Als programmeertaal heb ik gekozen voor C++ en als programmeeromgeving Borland builder 5.
Ik zal eerst vertellen wat ik tot nu toe heb gedaan. Mijn idee was om bij de start van het programma een boom op te bouwen van TTreeNodes en hieraan een class te hangen die informatie bevat over een positie (x,y coordinaat, score) op het speelbord. Alle knopen op een bepaald niveau in de boom geven alle mogelijke zetten voor die beurt weer. Zowel zetten van de speler als van de computer worden in de boom opgeslagen.
Vervolgens is het de bedoeling om met minmax algoritme een soort score te berekenen voor elke tak van de boom en mede hiermee kan de computer bepalen wat de scoorkans is voor een bepaalde tak.
Even een korte uitleg van het minmax algoritme. Elk van de bladeren van de boom geeft een winst(10), verlies(-11) of gelijk(0) spel aan. Vervolgens kun je vanaf de bladeren van de boom alle waarden optellen (bladeren optellen en in bovenliggend element waarde neerzetten) tot aan de eerste laag takken na de wortel. Op deze manier kan je bepalen welke zet je het beste kunt doen als computer (door middel van de score).
[probleem]
Probleem bij deze opdracht is het grote aantal elementen in de boom. Om dit enigzins te beperken wordt de boom pas opgebouwd na de eerste zet van de speler. Op deze manier hoef je maar 1/7 van de boom op te bouwen en hoef je 6/7 niet te bouwen.
Ondanks dit neemt die 1/7 van de boom nog extreem veel geheugen in beslag. Ik heb nu werkende code in builder, maar bij 200MB ram valt het geheugengebruik terug naar 50 MB en dat blijft zo lopen. Denk dat dit heeft te maken met de stack of de heap size.
Het algoritme zal dus veel slimmer moeten. Ik heb al zitten kijken naar pruning. Zover ik heb begrepen kies je er bij pruning voor om voor bepaalde takken van de boom de score niet uit te rekenen, omdat die slechter zijn dan de reeds gevonden score. Ik snap alleen niet hoe ik dit precies zou kunnen implementeren, want volgens mij moet ik daarvoor dus eerst een complete boom hebben opgebouwd en zover ben ik nog niet.
Ik moet dus de grote van de boom bij het opbouwen al zien te beperken zonder dat ik alle zetten door reken tot winst, verlies of gelijk spel. Ik snap alleen niet hoe ik op een goede manier kan beslissen om delen van de boom niet op te bouwen en dus slechte zetten weg te gooien.
Onderstaande code is puur alleen het opbouwen van de boom. Uitrekenen volgens minmax of ander algoritme is nog niet geimplementeerd, omdat ik daarvoor eerst een goede boom moet hebben. Code is getest met kleinere boardsize en werkt goed. Op dit moment zijn er nog labels toegevoegd aan de TTreeNode elementen, zodat ze zichtbaar zijn in een TTreeview en gecontroleerd kan worden of het algorimte goed werkt. Ik hoop dat het enigzins duidelijk is uitgelegd en dat mensen ondanks de grote lap tekst bereid zijn om te helpen.
[opdracht]
Het is de bedoeling om een 4opeenrij spel te maken met een computertegenstander die enige vorm van AI heeft. De zetten van de computer moeten dus niet compleet random zijn.
[status]
Als programmeertaal heb ik gekozen voor C++ en als programmeeromgeving Borland builder 5.
Ik zal eerst vertellen wat ik tot nu toe heb gedaan. Mijn idee was om bij de start van het programma een boom op te bouwen van TTreeNodes en hieraan een class te hangen die informatie bevat over een positie (x,y coordinaat, score) op het speelbord. Alle knopen op een bepaald niveau in de boom geven alle mogelijke zetten voor die beurt weer. Zowel zetten van de speler als van de computer worden in de boom opgeslagen.
Vervolgens is het de bedoeling om met minmax algoritme een soort score te berekenen voor elke tak van de boom en mede hiermee kan de computer bepalen wat de scoorkans is voor een bepaalde tak.
Even een korte uitleg van het minmax algoritme. Elk van de bladeren van de boom geeft een winst(10), verlies(-11) of gelijk(0) spel aan. Vervolgens kun je vanaf de bladeren van de boom alle waarden optellen (bladeren optellen en in bovenliggend element waarde neerzetten) tot aan de eerste laag takken na de wortel. Op deze manier kan je bepalen welke zet je het beste kunt doen als computer (door middel van de score).
[probleem]
Probleem bij deze opdracht is het grote aantal elementen in de boom. Om dit enigzins te beperken wordt de boom pas opgebouwd na de eerste zet van de speler. Op deze manier hoef je maar 1/7 van de boom op te bouwen en hoef je 6/7 niet te bouwen.
Ondanks dit neemt die 1/7 van de boom nog extreem veel geheugen in beslag. Ik heb nu werkende code in builder, maar bij 200MB ram valt het geheugengebruik terug naar 50 MB en dat blijft zo lopen. Denk dat dit heeft te maken met de stack of de heap size.
Het algoritme zal dus veel slimmer moeten. Ik heb al zitten kijken naar pruning. Zover ik heb begrepen kies je er bij pruning voor om voor bepaalde takken van de boom de score niet uit te rekenen, omdat die slechter zijn dan de reeds gevonden score. Ik snap alleen niet hoe ik dit precies zou kunnen implementeren, want volgens mij moet ik daarvoor dus eerst een complete boom hebben opgebouwd en zover ben ik nog niet.
Ik moet dus de grote van de boom bij het opbouwen al zien te beperken zonder dat ik alle zetten door reken tot winst, verlies of gelijk spel. Ik snap alleen niet hoe ik op een goede manier kan beslissen om delen van de boom niet op te bouwen en dus slechte zetten weg te gooien.
Onderstaande code is puur alleen het opbouwen van de boom. Uitrekenen volgens minmax of ander algoritme is nog niet geimplementeerd, omdat ik daarvoor eerst een goede boom moet hebben. Code is getest met kleinere boardsize en werkt goed. Op dit moment zijn er nog labels toegevoegd aan de TTreeNode elementen, zodat ze zichtbaar zijn in een TTreeview en gecontroleerd kan worden of het algorimte goed werkt. Ik hoop dat het enigzins duidelijk is uitgelegd en dat mensen ondanks de grote lap tekst bereid zijn om te helpen.
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
| //---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "UnVieropeenrij.h"
#include "UnPositie.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
#define move 0
#define win 1
#define loss 2
#define draw 3
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
xcolumn = 3;
ycolumn = 5;
boardSize = xcolumn * ycolumn;
}
AnsiString __fastcall TForm1::createLabel(AnsiString x, AnsiString y)
{
AnsiString label;
AppendStr(label,"(");
AppendStr(label,x);
AppendStr(label, ",");
AppendStr(label, y);
AppendStr(label,")");
return label;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::createTree()
{
int ywaarde;
int tempX;
int tempY;
TTreeNode* root = NULL;
TTreeNode* tempNode = NULL;
TTreeNode* tempNode2 = NULL;
TTreeNode* startNode = NULL;
TTreeNode* firstChildNode = NULL;
AnsiString label;
root = new TTreeNode(TreeView1->Items);
// moet nog uitgelezen worden uit shape array
root->Data = new Positie(2,1,move,1);
TreeView1->Items->Add(root, "2, 1");
tempX = ((Positie*)(root->Data))->x;
ywaarde = ((Positie*)(root->Data))->y;
// add first row of possible moves
for(int x = 1; x <= xcolumn; x++)
{
if(x==tempX)
{
ywaarde++;
// label voor elementen in de boom
label = createLabel(x, ywaarde);
TreeView1->Items->AddChildObject(root->getFirstChild(), label, (new Positie(x,ywaarde,move,2)));
ywaarde--;
}
else
{
// label voor elementen in de boom
label = createLabel(x, ywaarde);
TreeView1->Items->AddChildObject(root->getFirstChild(), label, (new Positie(x,1,move,2)));
}
// label leegmaken voor nieuw element
label = "";
}
tempNode = root->getFirstChild();
tempNode = tempNode->getFirstChild();
while( tempNode != NULL)
{
createBranch(tempNode);
tempNode = tempNode->getNextSibling();
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::createBranch(TTreeNode * &root)
{
int tempX;
int tempY;
TTreeNode * startNode;
TTreeNode * tempNode;
int diepte;
AnsiString label;
diepte = ((Positie*)(root->Data))->diepte;
diepte++;
startNode = root->Parent;
startNode = startNode->getFirstChild();
while(startNode != NULL)
{
tempX = ((Positie*)(startNode->Data))->x;
tempY = ((Positie*)(startNode->Data))->y;
int copyTempY = tempY;
if(startNode == root)
copyTempY++;
label = createLabel(tempX, copyTempY);
if(copyTempY <= ycolumn)
{
tempNode = TreeView1->Items->AddChildObject(root, label, (new Positie(tempX,copyTempY,move,diepte)));
}
startNode = startNode->getNextSibling();
}
startNode = root->getFirstChild();
while(startNode != NULL && diepte <= boardSize)
{
createBranch(startNode);
startNode = startNode->getNextSibling();
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormCreate(TObject *Sender)
{
createTree();
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "UnPositie.h"
//---------------------------------------------------------------------------
Positie :: Positie(int xPos, int yPos, int posStat, int boomDiepte)
{
x = xPos;
y = yPos;
score = 0;
status = posStat;
diepte = boomDiepte;
}
//---------------------------------------------------------------------------
#pragma package(smart_init) |
:strip_icc():strip_exif()/u/26322/appje.jpg?f=community)
