
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
August 24th, 2013, 07:07 PM  #1 
Senior Member Joined: Jan 2013 Posts: 209 Thanks: 3  Many think Chess is NPComplete so is Deep Blue general AI
Many think Chess is NPComplete Does that mean Deep Blue is general intelligence http://cstheory.stackexchange.com/quest ... ngmachine http://en.wikipedia.org/wiki/Game_complexity says Chess and Go are "EXPTIME". http://en.wikipedia.org/wiki/Deep_Blue_ ... omputer%29 http://en.wikipedia.org/wiki/Strong_AI I can see why Go would be at least NPComplete, since its like pascal's triangle (all random paths like sum of coin flips) with loops as logic gates, plus a few exceptions to balance the strategy. Chess I'm less sure about, but probably. Turing Complete is the infinite version of NPComplete. Conway's Game Of Life in any finite game space is NPComplete since you can simulate it with clique on the possible states of each group of 10 cells (1 center, 8 around it, and 1 above as we build time steps like buildings) some of which can be adjacent to eachother and some not, in the 6 directions of a 3d grid of cells, representing all calculations only locally. But chess I'm less sure of. If Chess is NPComplete, we should be able to build a translation program to use any chess program to play any other game or goal based system. I imagine chess as a superfluid of 96^2 * 100 * atLeast7 cells (including a square for each piece to be captured, 32+64) with directed edges between them which specify true or false for each direction of fluid flow. A whiteQueenNotMoving may start moving forwardleft so flows fluid into the whiteQueenMovingForwardLeft cell for clock cycle 1 of this turn, which may flow into only a certain 1 of whiteQueenMovingForwardLeft cell at clock cycle 2, or at cycle 1 it may flow into a certain whiteQueenStopped cell at clock cycle 2 which flows into whiteQueenStopped cell at clock cycle 3, and so on forming a bell curve of paths (except its more like Edit Distance since it can't go backward because of the blocked directions) and resulting in a spread of whiteQueenStopped in up to 8 directions and all cells the queen could reach, at clock cycle atLeast7. I may need more than 7 clock cycles to represent thing like the end of turns, and these kind of complexities make it look maybe not solvable, but at least we would have an interactive model to see what is really so hard about quantum. The thing it wouldn't represent is that thing about the quantum phased glass (or whatever its called) which only let light through in 1 direction (like vertical but not horizontal) where 2 together at 1/4 turn are dark but put a third between them at 1/8 turn and they each block half of the light, so 1/2 + 1/2 = 1/4 is not the right calculation and its instead 1/2 + 1/2 * (1/2) = 1/4, since there are 3 of them. As a superfluid, the PageRanklike flow (as its defined that pages with no outgoing links do link to all pages at once so its always complete loops) would give all the fluid to only the cells where the kings (1 or both) are in the captured cells, and would link back around to a cell for newgame which links to the setup of a new game in those same cells at move 1, closing the manifold. It would let you do things like move a pawn forward 1 and 2 squares at a time and be captured by both of 2 pawns to its forward left, so maybe some parts of quantum are easier to simulate than the newtonian view since observing all the pieces into having 1.0 fluid at each clique of certain turns (only those the interval of atLeast7 clock cycles start/end on) turns it into a hard permutation problem, while as a fluid, the entire state space of chess, plus some quantum chess moves that are against the rules, are represented immediately when you start the game. The question is how hard it is to move them around. It is guaranteed that you can take any complete loop around all 100*atLeast7 turns and PBrane paint it across other parts of the state space (since they all loop on intervals of 100*atLeast7). Any ideas how to get such a quantumlike chess program to work and to make it fun to play, and what I'd really like is a multiverse of possible chess games many people could play in a clique democracy kind of game, maybe with voting or other fitting together of the pieces, and then maybe we could have thousands of people together challenge Deep Blue? Fluid computing is better for Go than Chess or Conway's Game Of LIfe or Rule 110 (and many other general computing models) because Go is about closing 1d manifolds in a 2d space where many parts of each player's manifold are spread in pieces, as they continue building on. It could be played with many colors instead of just a 2 player game. As a fluid sim, using the exact same algorithm as the chess sim and just different data, a closedByBlack kind of cell would prevent white from adding a whitePIece there. The whole system would be defined in terms of undirected graph/network, expanded to have 2 nodes for each direction so directed is a subset of undirected (time is a subset of timeless physics), The closedByBlack and closedByWhite would lack an edge to emptyCell which grows from the sides of the game board 1 cell at a time, like closedByBlack and closedByWhite grow from whitePiece and blackPiece, and somehow an adjacent emptyCell would have to kill either closed kind, so maybe it would have to be done in 3x3 grids like Conway's Game Of Life would use 10 colors instead of 2. Maybe instead of starting with a recursive system of the viscosity of brainwaves (defined by the time it takes to recognize a rotated image being linearly proportional to the angle), which would be done with the same core math, what I've discovered would be better explained with Chess, Go, Rule 110, Conway's Game Of Life, and a PageRanklike flow of Wikipedia pages linking to eachother, all in the same shared Internet space, since flows through networks with binary edges are really simple. For simulation of superfluidity like the youtube videos of Navier Stokes (when used with viscosity=0 or converging to it), I'd probably use an automata to spread the calculation nodes, as pascal's triangle (all paths like coin flips are 1 and +1) would generate bell curves from all points continuously, and through them we'd have to figure out what types (any node in the system with a name) would hold the average velocity vector from adjacent bell curves, what types would hold references to dimensions of space or clique constraints or whatever happens in the flow... Everything can be represented as an automata. The fourier of a bell curve being another bell curve happens for a reason. Its all circles. 
August 24th, 2013, 07:35 PM  #2  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Many think Chess is NPComplete so is Deep Blue is genera Quote:
 
August 24th, 2013, 08:10 PM  #3 
Senior Member Joined: Jan 2013 Posts: 209 Thanks: 3  Re: Many think Chess is NPComplete so is Deep Blue general A
I didn't say Deep Blue could reverse a Turing Machine from a chosen state you define as optimal.

August 25th, 2013, 07:07 AM  #4  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Many think Chess is NPComplete so is Deep Blue general A Quote:
 

Tags 
blue, chess, deep, general, npcomplete 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Unifying NPComplete read write locking superposition of bits  BenFRayfield  Number Theory  0  January 22nd, 2014 03:11 PM 
A box contains 3 white, 8 red, 9 blue  rsoy  Algebra  3  October 12th, 2013 01:54 PM 
NPComplete  Superfluidity and if accurate Navier Stokes  BenFRayfield  Applied Math  0  August 23rd, 2013 09:57 AM 
The probability that: two are white and one is blue.  Chikis  Advanced Statistics  13  August 21st, 2012 01:50 PM 
5 Blue, 10 Red, 15 green balls. Odds I will draw 5 blue 1st?  mimath123  Advanced Statistics  1  February 21st, 2010 03:24 PM 