search

utdrobotchess / chess-game

Chess game application
www.utdallas.edu/robotchess
Apache License 2.0
6 stars 1 forks source link

Paths should be optimized to reduce number of turns #8

Open ryanjmarcotte opened 9 years ago

ryanjmarcotte commented 9 years ago

Perhaps an additional optimization would be to prefer the piece-specific motion (i.e. knights move in L-shapes, bishops move diagonally, etc.)

ryanjmarcotte commented 9 years ago

As far as the piece-specific motion, perhaps would could try dynamic weighting of the graph depending on which piece is being moved. In other words, if we are considering moving a bishop, set the diagonal weights to be much lower than the lateral ones. I don't necessarily see how this would work for knight L-shape movements. Perhaps for knights, we could first probe the L-shaped movements manually (there would only be two right?). If they were obstructed, then proceed with Dijkstra as usual to find a re-routing.

As far as the turn optimization, we are basically trying to compute the "best" path given multiple paths that are the same length. This could be done through a modification to our Dijkstra implementation. See http://coddicted.com/dijkstras-algorithm-finding-all-possible-shortest-paths-between-two-vertices-in-a-graph/ for reference.