OctaPawn - Interim Report

You ppl can read my interim report in this link

http://bruneiopensource.bravehost.com/octapawn/interimreport.pdf

Ok.. cheers!!

OctaPawn

OctaPawn is my third year project. So this time, I’ll be more serious working on this project. I’ll post the design part later and try to update at least once a week.

You can read about HexaPawn to get the basic idea.

Trivia Game

The chess project is on the halt now. I need time to recheck again the code I wrote, but my interest on it is going down.

Anyway, I have new idea for a trivia game. Maybe I’ll put more effort on this new project, it will be mmorpg and I hope it will bring fun to everyone.

Below are the specification for the new trivia game

1. running on java applet and jframe
2. the questions will be put in mysql database
3. support multiple players
4. ...
   

Project Inactivity

This project will be inactive in one month time. Just wait for the next version release.

greedyEngine - The basic A.I

My first greedyEngine works just now, I got help from Dr Jaidi to debug few code lines. I call it greedyEngine because it only looks for material advantage. It’s more into tactical rather than thinking strategy.

After listing out all valid moves can be made by a player, then the computer has to check whether that every single move brings advantage to the player or his opponent.

Let say, initially the following pieces setup on board

[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [b] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [q] [ ] [Q] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [n] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Refer to my type assignment in previous post. Type assignment is also used to indicate the strength of each piece.

In the above diagram, white total strength is 8 and black is 15. The question is, how to lower down the opponent strength? One of solutions is by capturing any opponent piece.

If Q x b, the strength of black pieces would become 12
If Q x q, the strength of black pieces would become 7
If there’s no capture, the strength will remain the same and so on.
Here, the best move the computer can do is by doing Q x q. Then it keeps thinking ahead to check whether that capture favor him or his opponent. All this process are repeated using recursive method in JAVA.

Deep Clone vs Shallow Clone

As we know JAVA is object oriented, the list of all “valid moves” is considered as one object. In that “valid moves”, a move can be get from the list. What if I perform any move and check the total strength of player pieces? Since I already move one piece, if I want to check another move line, I must undo any move I made before. Another question arise, how to undo my move?

The object “valid moves” is inside another big object called “all moves” (either valid or invalid). It is like set theory in maths, thing is not exist by itself. You have universal set, subset and so on. Here, “all moves” is our super class, or outermost set. “Valid moves” is the subset of “all moves” and a “move” is the subset “valid moves”. Is that clear enough?

JAVA provide method called “clone”, there’s no easy way to copy an object. It’s not primitive type like integer or String, object is unique where it has reference value to its contain.

Let say,

x = “all moves”, then
y = x.clone()
When compare x.equals(y), it is false. But when compare the contain of x and y, it is true. It the contains that are equal, not the super class object. Why there are equal? Because they refer (memory reference) to the same contain. It’s like two bodies share the same heart. When one body feel hurt.. it will affect the other body. The method of cloning is called “deep cloning”, when it creates a new object but shares to the same reference (dependant).
We don’t that because we want to undo move, to return back to its previous state. The state that the “valid moves” untouch by another clone object, independant of contain. How to make a new clone object unique and independant in contain? The solution is, instead clone just the super class, we need to clone the subclass as well.

Then,

x = “all moves”, then

y = x.clone()
y.”valid moves” = x.”valid moves”.clone()

x and y are unique now, having their own “valid moves” reference but have the same contain.

Ok, I try to upload my source code as soon as possible. I need to refine it first.

Special Move Rules

In Chess, few special moves can made like en passant, castling, pawn promotion, pawn initial move. You can read more on those rules in wiki.

Pawn usually can jump to its next square, eg. a2-a3 (refer algebraic notation ). For a special case, it can jump from a2-a4, provided that the pawn never been moved and its infront square (eg. a3) is empty. Pawn capture method is also different but that it not considered as special move case. I have done coding pawn rules, except pawn promotion when it reaches rank 8 and en passant.

Castling is king special move, I will write more on this when I finished pawn part.

One Dimensional Rule

After a few minutes of trying basic mathematical formula, I solved the nature of each piece move. Here I what I found out

//valid moves - linear type - applicable only for 12 x 12 dimension
king = -13, -12, -11, -1, 1, 11, 12, 13
queen = -13, -12, -11, -1, 1, 11, 12, 13
rook = -12, -1, 1, 12
bishop = -13, -11, 11, 13
knight = -25, -23, -14, -10, 10, 14, 23, 25

As an example, knight on square 27 (b1), it can move to

27-25 = 2 (x)
27-23 = 4 (x)
27-14 = 13 (x)
27-10 = 17 (x)
27+10 = 37 (x)
27+14 = 41 (d2)
27+23 = 50 (a3)
27+25 = 52 (c3)

I already coded the rules above, it works for white and black pieces. I haven’t coded the rules for pawn. Queen and king move rules are the same but actually queen can jump to further square. I inserted loop to check all valid squares repeatedly.

Up to now, I have completed listing out all valid moves made by white and black pieces separatedly. Those valid moves able to check

• extended square
• capture move
• blocked path because of capture move or own piece block the way

All those valid moves are stored in vector array for further process like prediciting the best move.. (it takes time to make the A.I part, be patient).

I haven’t implement rules for king castling, pawn rule like its move, en passant, capture, promotion, en passant.

Board Setup and Type Assigment

/** default board setup
*
* 132 [11][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
* 120 [10][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
* 108 [9][ ][ ][r][n][b][k][q][b][n][r][ ][ ]
* 96 [8][ ][ ][p][p][p][p][p][p][p][p][ ][ ]
* 84 [7][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
* 72 [6][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
* 60 [5][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
* 48 [4][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
* 36 [3][ ][ ][p][p][p][p][p][p][p][p][ ][ ]
* 24 [2][ ][ ][r][n][b][k][q][b][n][r][ ][ ]
* 12 [1][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
* 0 [0][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
* y,x[0][1][2][3][4][5][6][7][8][9][10][11]
*
*
* */

The above diagram shows how the board is setup.
I have decided to extend the standard 8×8 board dimension to 12×12. The total square would become 144 instead of 64. The game play would not be affected since extended squares are just part of programming side. The main purpose of the extended squares is as an indicator, to indicate that any pieces movement will not hit the borders.. (i.e invalid move indicator).

The overall board setup would be

[x] [x] [x] [x] [x] [x] [x] [x] [x] [x] [x] [x]
[x] [x] [x] [x] [x] [x] [x] [x] [x] [x] [x] [x]
[x] [x] [r] [n] [b] [k] [q] [b] [n] [r] [x] [x]
[x] [x] [p] [p] [p] [p] [p] [p] [p] [p] [x] [x]
[x] [x] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [x] [x]
[x] [x] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [x] [x]
[x] [x] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [x] [x]
[x] [x] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [x] [x]
[x] [x] [p] [p] [p] [p] [p] [p] [p] [p] [x] [x]
[x] [x] [r] [n] [b] [k] [q] [b] [n] [r] [x] [x]
[x] [x] [x] [x] [x] [x] [x] [x] [x] [x] [x] [x]
[x] [x] [x] [x] [x] [x] [x] [x] [x] [x] [x] [x]

‘x’ is the extended square. p, n, b, r, k and q are pawn, knight, bishop, rook, king and queen respectively. The squares without label are empty squares. Whenever a move is made, a piece can fill the empty square but not onto the ‘x’ square.

One dimensional (linear) square notatation is used here, counted from bottom to top rows. By looking at the diagram, square 26 is A1 in algebraic notation.

I assign value type to each piece. Type assignment is to replace a long piece name into coded form

king = 10
queen = 8
rook = 5
bishop = 4
knight = 3
pawn = 1

Hello world!!! - A fast start

I’m duolulu, I will post my active project here. Recently, I’m creating a Chess Engine using JAVA. The project itself, inspired from A.I book, borrowed by Dr. Brown. On the 22nd-May-2006, I seek help from Dr. Jaidi to make a start. He explained to me the steps, and guide me what to do first.

Since JAVA is object oriented programming, I have decided to break Chess structure in heirical order.

Chess is consists of

• two players - white and black
• a board of 64 squares
• 16 chessmen - given to each player
• the pieces (aka chessman) are subdivided into five different types
• one king
• one queen
• two rooks
• two bishops
• two knights
• eigth pawn
• different type of pieces has different move rules
• chess also has game rules
• player of white pieces has to move first
• each player has to move one piece per turn

(I will write more on this part soon)