My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Closed Thread
 
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 ... ng-machine

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 PageRank-like 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 P-Brane 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 quantum-like 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 PageRank-like 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.
BenFRayfield is offline  
 
August 24th, 2013, 07:35 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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:
Originally Posted by BenFRayfield
Many think Chess is NPComplete Does that mean Deep Blue is general intelligence
No, because Deep Blue does not find optimal solutions, merely 'good' solutions.
CRGreathouse is offline  
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.
BenFRayfield is offline  
August 25th, 2013, 07:07 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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:
Originally Posted by BenFRayfield
I didn't say Deep Blue could reverse a Turing Machine from a chosen state
Nor did I.
CRGreathouse is offline  
Closed Thread

  My Math Forum > Science Forums > Computer Science

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 r-soy 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





Copyright © 2019 My Math Forum. All rights reserved.