Wednesday, November 26, 2014

New Moves

A new skill or tool is always best learned through its application. Practice, practice, practice! In the the past I tended to read about something of interest, but not actively apply it to demonstrate and solidify my knowledge. The recognition of that flaw was a hard-learned lesson that slowly, steadily reared its ugly head throughout college. And frankly, I'm sure I'm still guilty of it from time to time, but I'm certainly better at it now!

The Perfect Challenge

While watching a show on Netflix, I thought of trying to model a chess game programmatically. Then I realized that actually makes a perfect project for a whole host of reasons, hitting several challenges I've been wanting explore right on the nose! I want to expand my very limited hands-on experience with machine learning, and chess has a rich history and so tons of data to train on. I've also been looking to get more practice designing MapReduce functions, and chess presents a set of an inherently parallelizable calculation (i.e. simulating outcomes give particular moves). If I get stuck, confused, or otherwise need help, I'm sure there's a plethora of examples out there to work from. I'm in essence intentionally re-inventing a wheel (more like an engine!), so that I have the opportunity to seek guidance when the need arises. I'm sure there's a ton of different statistical tests and tools I can tinker with to take different approaches to assessing the state of a board and determining moves.

Furthermore, there's an incredible range of difficulty to attack: I can keep the task simple by specifying a very specific sequence of moves and/or circumstances (which pieces are where) and trying to determine the "best" move (of course "best" is itself up to me to determine in this case), or go as deep and advanced as I could wrap my head around by attempting to simulate entire games, or varying how many moves out to project, how complicated an algorithm to determine the "best" move(s) to make, and so on. I'd bet one could continue coming up with a plenty more reasons this is such a great challenge to work on.

Starting Positions, Please!

To begin, I laid out the elements I'll need to develop: a board, populated with squares which have given properties like whether or not its location is occupied by a piece; each piece itself having a set of possible moves, and so on. Naturally, I started to get ahead of myself and needed to move backward and start simpler. In the end I wound up setting tonight's goal as establishing a single piece in the center of a small (3 x 3) board and determining it possible moves. I chose the piece to be a King, to have multiple possible moves, but have all such moves be very straightforward to assess. 

I can already see a ton of attributes and functions and the like that I'll need to define in the end: 
  • given a possible move to a new square, is that square occupied? If so, is it a piece of mine (so I can't move there) or is it an opponent's (in which case I can attack). Is there piece "in the way" so I can't move in that direction (with the exception of the Knight, of course)?
  • Am I on/near a boundary? A King can move left, yes, but if he's all the way to the left of the board, then no he can't! 
  • How do I weight possible moves? What's more important, what's less important? And how do I even quantify factors like whether to attack, how to recognize when a piece is "at risk" and whether that risk is acceptable, how to determine a move's importance as a part of a large strategy, so each move is interdependent on other moves...
  • Oh so many more... 

The First Big "Aha" Moment

When trying to define a piece's allowed moves, I wondered how to distinguish between one (say white) pawn's allowed move "up" or "forward" versus the opposing pawn's allowed move "down/backward" -- especially if basing locations on a Cartesian coordinate system board. Then it clicked that a better approach might be to define the entire board, pieces, and match from the perspective of a single player; then a two-person game is really just two separate (but related) instantiations of that single-person game! Each player can see his/her moves as forward, facing opposition pieces which, for the time being, can be considered just stationary obstacles. Then once the basic "moving" functionality is operational, having worked in not only permissible moves but also having those moves dependent on whether squares have another piece on them, I can figure out how to make each player's board setup (and thus moves) interdependent on the opposing player's board. The complexity builds pretty damn quickly, but it was a good realization to have early, I figure. 

The current struggle is how to relate objects to one another. For example, rather than determining moves on/at the level of a particular piece, I'd rather define relative movements for the piece (x+1, y+2, etc) and then use those to determine the set of possible "next locations" at the level of the Square (location) or even Board itself. So piece know's where it is and how it can move, but not where it can move, instead allowing the Square/Location (referenced by the "where it is") to determine and inform the piece where it can move

This is how I'm voluntarily spending my evening. I'm such a nerd. :-) 

No comments:

Post a Comment