Labreport
Maarten Leeuwrik
Roderik Lagerwey
Dit jaar zijn wij begonnen met de studie Kunstmatige Intelligentie. Hiervoor zijn wij momenteel bezig met een project waar we eerder opgestoken kennis in de praktijk oefenen. Deze periode begonnen met het schrijven van een chess-solver die de volgende schaaktoestand tot een situatie kon krijgen waarin zwart schaakmat stond:
Voor dit onderdeel hebben we gebruik gemaakt van Prolog. Vervolgens zijn we verder gegaan met Java om een robotarm te programmeren die schaakstukken kon verplaatsen. Hier kwamen onder andere simpele zoektechnieken bij kijken om de arm het juiste pad af te laten leggen.
Nu is het de bedoeling om vanuit deze situatie verder te werken. Hiervoor moeten we zelf verzinnen hoe wij deze situatie gaan uitbreiden. Als snel kwamen we op het idee om de computer in combinatie met de robotarm een ander spel te gaan laten spelen. Dammen leek ons hier een mooi spel voor.
Wij denken dat het mogelijk moet zijn de situatie zo aan te passen zodat de computer in combinatie met de robotarm moet kunnen dammen. We verwachten hier wel een goed plan voor nodig te hebben, aangezien er een hoop bij komt kijken naar ons idee:
Hetgeen waar we eerst rekening mee moeten houden is hoe onze opstelling gaat worden. Wat we hebben is een werkende situatie als schaakrobot, waar we aanpassingen aan moeten maken zodat deze ook kan dammen. Omdat we maar beperkte veranderingen aan het totale programma kunnen maken zullen we sommige dingen handig aan moeten pakken. Het voorstel is om alleen in PP.java veranderingen te maken, en gegevens die mee gegeven worden aan dit programma te negeren. Omdat we deze gegevens negeren zullen we zelf gegevens moeten opslaan in een bestand zodat deze niet verloren gaan. Het is onze eerst stap om te kijken hoe dit precies in zn werking gaat en om een programma te schrijven dat gegevens naar een bestand kan wegschrijven en vervolgens ook weer inlezen.
Het lijkt het gemakkelijkst om het dambord te representeren als een simpele integer array van 8 bij 8, waarin een 0 voor een leeg vakje staat, een 1 voor een witte steen en een 2 voor een zwarte steen. Verder is het belangrijk dat de gebruiker een zet kan invoeren.
Voor dit punten lijkt het ons makkelijk om een programma afzonderlijk van het PP.java bestand te maken, zodat we deze individuele stukken gemakkelijk kunnen testen.
Voor het bewegen van de stukken denken we de HighPath te kunnen gebruiken. LowPath laten we achterwege omdat deze compleet aangepast zou moeten worden om ook diagonaal te kunnen bewegen. Bovendien is uit eerdere experimenten gebleken dat de robotarm hier waarschijnlijk niet nauwkeurig genoeg voor is. We houden het dus op HighPath, en gebruiken deze functie ook voor MovetoGarbage. HighPath hebben we in eerdere opdrachten al werkend gekregen, dus we hoeven daar geen aanpassingen meer aan te maken. Wel moeten we opletten dat we een goede PieceHeight gebruiken. We denken gewoon een universele hoogte te nemen die op alle stukken toepasbaar is. Bovendien hebben we maar 2 * 12 = 24 stukken nodig (i.p.v. 2 * 16 = 32) waardoor we moeilijke stukken zoals koning en koningin weg kunnen laten.
Als laatste wat er bij komt kijken is een stuk kunstmatige intelligentie. Hiervoor zijn wij uiteindelijk met het volgende algoritme gekomen:
De software die we gebruiken om dit te kunnen programmeren is Java. Wij programmeren in een Linux omgeving met een simpele texteditor. Het implementeren van de code lijkt ons niet heel erg moeilijk, aangezien we beide wel wat eerdere ervaring hebben met programmeren in C/C++.
Omdat we maar beperkte mogelijkheden om ons programma te testen hebben we geen specifieke meetresultaten. Bijvoorbeeld omdat we geen toegang hebben tot de robotarm kunnen we ons programma niet in de praktijk proberen. In principe zou dit gewoon moeten werken, omdat we onze HighPath gebruiken die in vorige opdrachten het ook prima deed. Het zou echter kunnen dat onverwachte gebeurtenissen toch gaan plaatsvinden.
Appendix A
Zoals vermeld is onze code een uitbreiding op het PP.java bestand.Dit bestand hebben we hieronder geplaatst. Op verschillende plaatsen hebben we commentaar toegevoegd. Mochten er nog onduidelijkheden zijn zouden we dit op de presentatie toe kunnen lichten.
Sourcecode:
/*
* PP.java
* Assignment for the Path planning part of the ZSB lab course.
*
* This you will work on writing a function called highPath() to move a
* chesspiece across the board at a safe height. By raising the gripper 20 cm
* above the board before moving it over the board you don't risk hitting any
* other pieces on the board. This means you don't have to do any pathplanning
* yet.
*
* Input of this program are two commandline arguments, the first one
* describing the human (white) move and the second denoting the computer
* (black) move. The human has been executed by the human and can be ignored.
* Your job is to find the correct sequence of GripperPositions (stored in
* Vector p) to pick up the correct black piece and deposit it at its desired
* new location. Read file /opt/stud/robotics/hints/HIGHPATH_POSITIONS to see
* what intermediate positions you should calculate.
*
* To run your program, fire up playchess and the umirtxsimulator. In
* the simulator you can see the effect of your path planning although
* the board itself is not simulated. When you think you've solved
* this assignment ask one of the lab assistents to verify it and let
* it run on the real robot arm.
*
* Nikos Massios, Matthijs Spaan <mtjspaan@science.uva.nl>
* $Id: Week2.java,v 1.9 2004/05/31 19:49:35 mtjspaan Exp $
*/
import java.io.*;
import java.lang.*;
import java.util.Vector;
import tio.*;
public class PP {
public static void main(String[] args){
ChessBoard b = new ChessBoard();
DamBord d = new DamBord();
Vector p = new Vector();
/* Read the board state*/
b.read();
/* print the board state*/
// b.print();
System.out.println("\n\n====================");
System.out.println("Dammen:");
System.out.println("====================");
System.out.println("Huidig bord:");
d.Read();
d.Display();
String move;
boolean valid = false;
while (!valid)
{
System.out.println("Geef U move...");
move = Console.in.readWord();
valid = d.isLegal(move, "white");
if (!valid)
System.out.println("Invalid move!");
}
d.commit(move, "white", p, b);
d.generate(p, b);
System.out.println("**** The board after the move was:");
/* print the board state*/
d.Display();
d.Write();
System.out.println("\n\n====================");
System.out.println("Klaar met zetten; negeer schaken A.U.B. =P ");
System.out.println("====================");
/* after done write the gripper positions */
GripperPosition.write(p);
}
}
class DamBord {
private static double SAFE_HEIGHT=200;
private static double LOW_HEIGHT=40;
private static double OPEN_GRIP=30;
private static double CLOSED_GRIP=0;
private static double LOW_PATH_HEIGHT=20;
/** Creates a new instance of DamBord */
public DamBord() {
bord = new int[8][8];
for(int a = 0; a<8;a++)
for(int b = 0; b<8; b++)
bord[a][b] = 0;
}
public boolean isLegal(String move, String side)
{
int direction = 0;
if (side == "white") direction = 1; // Legal moves are up
else if (side == "black") direction = -1; // Legal moves are down
else return false; // No side; can't be legal
Vector moveList;
makeLoc(move, moveList); // moveList is all the moves, in BoardLocations
/* Check for each step, if it is legal. A step consists of two
* BoardLocations: To, and From. We start at index 0, and move
* to moveList.size() - 1, because we skip the last index. We
* check in pairs of two. */
BoardLocation2 from = (BoardLocation2) moveList.get(0);
BoardLocation2 to;
int tX; int tY; int status = 0;
// Check if start is legal. column + row must be an even number
if ((from.column + from.row) % 2 != 0)
return false;
// Check if we are moving a piece of our own
if (side == "black" && bord[from.column][from.row] != 2) return false;
if (side == "white" && bord[from.column][from.row] != 1) return false;
// Iterate through move list
for (int x = 0; x < moveList.size() - 1; x++)
{
from = (BoardLocation2) moveList.get(x);
to = (BoardLocation2) moveList.get(x+1);
// Are positions legal?
if ((to.column + to.row) %2 != 0) return false;
// Single steps
if (from.row - to.row == -1 || from.row - to.row == 1)
{
// Have we taken any step before? If yes; illegal
if (status != 0) return false;
// Do we move 1 step amongst X as well? If not; illegal
if (from.column - to.column != -1 && from.column - to.column != 1)
return false;
// Then... is it forward? If not; illegal
if (from.row - to.row != direction) return false;
// Otherwise, is target square empty? If not; illegal
if (bord[to.column][to.row] != 0) return false;
// Well, this step is legal. Continue =)
status = 1; // We have taken a single step
}
// Jumps
else if (from.row - to.row == -2 || from.row - to.row == 2)
{
// Have we taken a single step before? If yes; illegal
if (status == 1) return false;
// Do we move 2 steps amongst X as well? If not; illegal
if (from.column - to.column != -2 && from.column - to.column != 2)
return false;
// Forward is not an issue... but an opponent has to be in between
// So first, we need the 'in between' square
tX = (from.column - to.column) / 2;
tY = (from.row - to.row) / 2;
if (side == "white" && bord[tX][tY] != 2) return false;
if (side == "black" && bord[tX][tY] != 1) return false;
// Is target square empty?
if (bord[to.column][to.row] != 0) return false;
status = 2; // We have taken a double step
}
// Not a legal move... thus. Move is not allowed.
else return false;
}
// Every move has been deemed legal, thus, the entire set is legal
return true;
}
public void commit(String move, String side, Vector p, ChessBoard b)
{
// Turn the move list into a BoardLocation vector
Vector l;
makeLoc(move, l);
BoardLocation2 from;
BoardLocation2 to;
for (int a = 0; a < l.size() - 1; a++)
{
from = (BoardLocation2) l.get(a);
to = (BoardLocation2) l.get(a+1);
highPath(sPos(from, to, b, p));
if (from.row - to.row == 2 || from.row - to.row == -2)
{
// Something has to be thrown into garbage
from = new BoardLocation2(sPos(from.row-to.row, from.column-to.column));
toGarbage(from, b, p);
}
}
// We already know the move is legal; otherwise, it shouldn't be committed =P
}
private static String sPos(int row, int column)
{
char c = (char)(column + 97);
char r = (char)(row + 49);
String s = String.valueOf(c) + String.valueOf(r);
return s;
}
private void makeLoc(String move, Vector l)
{
String temp;
BoardLocation2 t;
for (int a = 0; a < move.length() - 2 ; a += 2)
{
temp = move.substring(a, a + 2); // Take an 'e4' pair
t = new BoardLocation2(temp); // Make it a BoardLocation '3,4'
l.add(t); // Stuff in Vector =P
}
}
public void Reset()
{
boolean even = true;
for(int a = 0; a<3; a++)
{
for(int b = 0; b<7; b = b + 2)
{
if(even) bord[a][b + 1] = 1;
else bord[a][b] = 1;
}
if(even) even = false;
else even = true;
}
for(int a = 5; a<8; a++)
{
for(int b = 0; b<7; b = b + 2)
{
if(even) bord[a][b + 1] = 2;
else bord[a][b] = 2;
}
if(even) even = false;
else even = true;
}
}
public void Write()
{
try
{
DataOutputStream out = new DataOutputStream(new FileOutputStream("board.dat"));
for(int a = 0; a<8; a++)
for(int b = 0; b<8; b++)
out.writeInt(bord[a][b]);
out.close();
}
catch ( IOException iox )
{
System.out.println("Problem writing");
}
}
public void Read()
{
try
{
DataInputStream in = new DataInputStream(new FileInputStream("board.dat"));
for(int a = 0; a<8; a++)
for(int b = 0; b<8; b++)
{
bord[a][b] = in.readInt();
//System.out.println(bord[a][b]);
}
in.close();
}
catch(IOException EOFException)
{
System.out.println("EOF Error!!!");
System.out.println("Nieuw bord wordt gemaakt...");
Reset();
System.out.println("Nieuw bord wordt naar bestand geschreven...");
Write();
}
}
public void Display()
{
System.out.println();
System.out.println();
for (int a = 0; a<8; a++)
{
for(int b = 0; b < 8; b++)
System.out.print(" " + bord[a][b]);
System.out.println();
}
}
public void generate(Vector p, ChessBoard b)
{
// The goal is to call GenMove for every square on the board.
// Each GenMove tree will return a score value for the best move,
// and a vector that has the steps of said move. Gen Move only
// looks for doublesteps.
Vector bestMoves;
Vector tL;
int bS = 0;
int tS;
BoardLocation2 current;
BoardLocation2 old;
BoardLocation2 best;
int a, b;
for (a = 0; a < 8; a++)
{
for (b = 0; b < 8; b++)
{
if (bord[a][b] == 2)
{
current = new BoardLocation2(a, b);
old = new BoardLocation2(-1, -1);
tS = GenMove(current, old, 0, tL);
if (tS > bS)
{
bS = tS;
bestMoves = tL;
best = new BoardLocation2(a, b);
}
}
}
}
boolean s = false;
if (bS == 0) // No pieces can be taken!
{
bestMoves = new Vector();
for (a = 0; a < 8 && !s ; a++)
{
for (b = 0; b < 8 && !s; b++)
{
if (bord[a][b] == 2)
{
if (bord[a-1][b-1] == 0)
{
s = true;
best = new BoardLocation2(a-1, b-1);
bestMoves = new Vector();
bestMoves.add(best);
}
else if (bord[a+1][b-1] == 0)
{
s = true;
best = new BoardLocation2(a+1, b-1);
bestMoves = new Vector();
bestMoves.add(best);
}
}
}
}
}
// Alright. We have a vector now, 'bestMoves', that consists of a
// list of BoardLocation2's that we want to visit. Now we just have
// to turn this into a string, and pass this string on to the
// commit function ^-^;;;
String compMove = makeMove(bestMoves);
commit(compMove, "black", p, b);
}
private String makeMove(Vector l)
{
if (l.size() == 0)
return(" ");
BoardLocation2 b;
String r;
// Moves are put in the list backwards! First move is at the end
for (int a = l.size(); a >= 0; a++)
{
b = (BoardLocation2) l.get(a);
r += sPos(b.row, b.column);
}
return r;
}
private int GenMove(BoardLocation2 current, BoardLocation2 old, int ply, Vector list)
{
BoardLocation2 next;
// 'Killswitch'
if (ply == 100) return 0;
int bD = 0;
int bS = 0;
Vector moveList;
Vector temp;
int tS;
for (int a = 1; a <= 4; a++)
{
next = new BoardLocation2(current.column, current.row);
GenNew(next, a);
if (next.column != current.column && next.row != current.row)
{
if (bord[next.column][next.row] == 1)
{
// Possible jump!
GenNew(next, a);
if (bord[next.column][next.row] == 0)
{
// Jump!
temp = new Vector();
tS = GenMove(next, current, ply+1, temp);
if (tS > bS)
{
bS = tS;
bD = a;
moveList = temp;
}
}
}
}
}
// bD is now the most successful direction. bS the highest score
// No move can be made
if (bD == 0)
{
list = new Vector();
return 0;
}
// A move can be made! The vector list will have all the moves.
// The return value is the score attached to this list
else
{
list = moveList;
next = new BoardLocation2(current.column, current.row);
GenNew(next, bD);
list.add(next);
return bS;
}
}
// Turn a location and a direction into a new location
private void GenNew(BoardLocation2 a, int d)
{
if (d == 1)
{
a.row++;
a.column++;
}
else if (d == 2)
{
a.row--;
a.column++;
}
else if (d == 3)
{
a.row--;
a.column--;
}
else if (d == 4)
{
a.row++;
a.column--;
}
}
private static void highPath(String from, String to,
ChessBoard b, Vector p){
System.out.println("**** In high path");
try {
BoardLocation2 f_pos = new BoardLocation2(from);
BoardLocation2 t_pos = new BoardLocation2(to);
Point tPoint;
double pHeight = 15;
double bH = b.board_thickness;
double bDX = -b.sur_x;
double bDY = b.sur_y;
GripperPosition tGripper;
// Step one
tPoint = b.toCartesian(f_pos.row, f_pos.column);
tPoint.x += bDX;
tPoint.y += bDY;
tPoint.z = SAFE_HEIGHT+bH;
tGripper = new GripperPosition(tPoint, 0, OPEN_GRIP);
p.add(tGripper);
// Step two
tPoint.z = LOW_HEIGHT+bH;
tGripper = new GripperPosition(tPoint, 0, OPEN_GRIP);
p.add(tGripper);
// Step three
tPoint.z = pHeight+bH;
tGripper = new GripperPosition(tPoint, 0, OPEN_GRIP);
p.add(tGripper);
// Step four
tGripper = new GripperPosition(tPoint, 0, CLOSED_GRIP);
p.add(tGripper);
// Step five
tPoint.z = SAFE_HEIGHT+bH;
tGripper = new GripperPosition(tPoint, 0, CLOSED_GRIP);
p.add(tGripper);
// Step six
tPoint = b.toCartesian(t_pos.row, t_pos.column);
tPoint.x += bDX;
tPoint.y += bDY;
tPoint.z = SAFE_HEIGHT+bH;
tGripper = new GripperPosition(tPoint, 0, CLOSED_GRIP);
p.add(tGripper);
// Step seven
tPoint.z = LOW_HEIGHT+bH;
tGripper = new GripperPosition(tPoint, 0, CLOSED_GRIP);
p.add(tGripper);
// Step eight
tPoint.z = pHeight+bH;
tGripper = new GripperPosition(tPoint, 0, CLOSED_GRIP);
p.add(tGripper);
// Step nine
tGripper = new GripperPosition(tPoint, 0, OPEN_GRIP);
p.add(tGripper);
// Step ten
tPoint.z = SAFE_HEIGHT+bH;
tGripper = new GripperPosition(tPoint, 0, OPEN_GRIP);
p.add(tGripper);
} catch (ChessBoard.NoPieceAtPositionException e) {
System.out.println(e);
System.exit(1);
}
// ???? Write this function
// Use the boardLocation and toCartesian methods you wrote last week.
/* Example of adding a gripperposition to Vector p.
* Point tempPoint;
* GripperPosition temp;
* tempPoint = new Point(x-coordinate, y-coordinate, z-coordinate);
* temp = new GripperPosition(tempPoint, angle, CLOSED_GRIP/OPEN_GRIP);
* Now you only have to add it at the end of Vector p.
*/
}
private static void moveToGarbage(String from, ChessBoard b, Vector g){
/* When you're done with highPath(), incorporate this function.
* It should remove a checked piece from the board.
* In main() you have to detect if the computer move checks a white
* piece, and if so call this function to remove the white piece from
* the board first.
*/
// Bit of additional code, to determine number of
// dead pieces. There should be 16 pieces on the board
// and any not on the board, are to the side.
int z = 0;
for (int x = 0; x < 8; x++)
{
for (int y = 0; y < 8; y++)
{
if (bord[x][y] > 0)
z++;
}
}
z = 16 - z;
System.out.println("**** In moveToGarbage");
int number = z;
int offset;
for (offset = 9; number > 7; number = number - 8)
{
offset++;
}
String to = sPos(number, offset);
highPath(from, to, b, g);
}
int[][] bord;
}
class BoardLocation2{
public int row;
public int column;
public BoardLocation2(int x, int y)
{
column = x;
row = y;
}
public BoardLocation2(String position)
{
// write this function
column = position.charAt(0) - 97;
row = position.charAt(1) - 49;
}
}
Appendix B
Dagboek
Vrijdag 18 juni
We willen bepalen in wat voor hoek we onze uitbreiding gaan zoeken voor deze opdracht. Het lijkt ons leuk om verder te werken met de robotarm, aangezien het al eerder een aantal leuke momenten heeft opgebracht. Het idee komt op om de computer een ander spel te laten spelen waar het schaakbord ook gebruikt voor kan worden. Idee zijn boter, kaas en eieren en dammen. We denken dat de uitdaging iets groter is als we dammen kiezen. Bovendien is dit spel goed speelbaar met de huidige bordopstelling.
Zaterdag 19 juni
We kiezen voor dammen. We maken een opzetje van een plan hoe we dingen gaan aanpakken. Ook een taakverdeling komt aan de orde. We moeten bekend raken met het schrijven naar en lezen van bestanden. We besluiten dat Roderik hier wat onderzoek naar gaat doen. Maarten gaat dan alvast beginnen met het bedenken van een plan hoe we de AI gaan programmeren.
Zondag 20 juni
We hebben een overleg over hoe we onze eigen code kunnen implementeren in de bestaande code. We hebben niet toegang tot alle bestanden en moeten daarom wat trucjes toepassen om het gewenste resultaat te krijgen. Verder bespreken we hoe het individueel gaat met het programmeren. Ook praten we alvast even over de AI. Tot dusver verwachten we dat dat niet een groot probleem gaat worden.
We gaan individueel verder met de taken die we eerder afgesproken hadden.
Maandag 21 juni
Roderik heeft een programma gemaakt waarin het schaakbord gepresenteerd is, de gebruiker zetten kan opgeven en gedaan kunnen worden. Samen besluiten hoe we wat verbeteringen eraan kunnen maken.
Ondertussen is Maarten ook bezig met programmeren van onder andere een check of zetten legaal zijn en of er iemand geslagen is. Ook andere onderdelen zoals stukken slaan worden geprogrammeerd.
Dinsdag 22 juni
Om te zorgen dat onze programma's goed op elkaar aansluiten spreken we af in de computerzaal van gebouw P. Hier bespreken we ook hoe we de rest gaan aanpakken en maken de afspraak om woensdag weer hier af te spreken. We realiseren ons dat het handig is om eens in de tijd samen af te spreken en in 'real life' te overleggen.
Woensdag 23 juni
We hebben onze programmas af en voegen deze beide toe in PP.java. Nu is het de taak om een AI te programmeren. Hier besteden we een groot deel van de dag aan. Eerst verzinnen we een algoritme op papier en vervolgens implementeren we deze in code.
Ook beginnen we met het opbouwen van het verslag.
Donderdag 24 juni
De laatste stukken moeten we nog programmeren. We testen de code zover we kunnen (we hebben geen toegang tot de robotarm). We moeten meerdere malen aanpassingen aan het programma omdat we onderdelen over het hoofd hadden gezien, maar al met al verloopt dit redelijk gemakkelijk.
Vervolgens gaan we verder met verslag. Ook bespreken we hoe en wat we precies gaan presenteren, en wie wat gaat vertellen.
Vrijdag 25 juni
Laatste afspraken maken met betrekking tot de presentatie. Vervolgens zelf presenteren.