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.