Solving a 121x121 matrix, does it take too much time?

[pX]

First of all I'm not a programming whiz at all.

I am writing a program that plays Hex, it's the game Nash came up with (of Beautiful Mind fame). Anyway, I am using a position evaluation function that treats the board as a big simultaneous equation. 121x121 to be exact. Most values are going to be the same, zero, but for about 10-12 of each the value will be different.

Anyway, the idea was to use some sort of library function to solve this 121x121 for one value in it.

I am afraid this will take too much time, as I'll need to solve around 121^5 (for 5 ply) of these 121x121 matrices in at most 30 seconds. I'm just looking for some sort of ballpark estimate, well not even that, just a "solving a matrix doens't take too long compared to most math functions" or a "that'll take forever" type idea...

I know this question is broad, probably too broad, but any help would be great! thanks....

 

[Armitage]

Yes, very broad ... but there is a whole field devoted to solving "sparse" matrices, and lots of software out there. Take a look at LinPack & BLAS. You should find some algorithms there to let you benchmark it pretty quickly. And my gut feel is that 121x121 is not that big, but 121^5 is about 26,000,000,000 so you could run into issues with solving 26 billion of them in 30 seconds ... but then hardware is cheap

Any links on Hex? Sounds interesting.

 

[glugglug]

Time to solve a square matrix using normal well known methods is proportional to the size cubed (i.e. 121^3 in this case), which means we're talking like an hour for 1.
There are much better unpublished algorithms out there, HP graphing calculators use them.

 

[Anubis]

type it all into Maple. Maple RULES at solving big matrices. might take a lil to type it all but itll solve it for you nice and fast

 

[Haircut]

I think that could take a hell of a long time, although certain matrices would be solvable pretty quickly

How exactly do you plan your program to work?

BTW, here is a page with lots of info on hex
Link

 

[Armitage]

Ok, I'm having some trouble getting from here...

Originally posted by: glugglug
Time to solve a square matrix using normal well known methods is proportional to the size cubed (i.e. 121^3 in this case),

to here???

which means we're talking like an hour for 1.

You've stated the algorithm for solving a matrix equation is O(n^3) ... I haven't bothered to confirm that.
But in any case, that gives you no basis for making an estimate of the absolute time required for a given size matrix, only an estimate for how fast the required time will grow as you increase the size of the matrix.

There are much better unpublished algorithms out there, HP graphing calculators use them.

FWIW (not much) I put together a quick test program with my own array class, which has a Guass-Jordan inverter with full pivoting This isn't optomized for large and/or sparse matrices. You'd probably be better off with an iterative solution in any case. I don't typically deal in matrices bigger then 9x9 myself

I generated a random array and scaled the diagonal to help make it a little better conditioned. Here's what I got on a 1GHz PIII, 512 MB, gcc 3.2

Size: 100
Inverse: 0.0955271 seconds

Size: 121
Inverse: 0.141566 seconds

Size: 200
Inverse: 0.83128 seconds

Size: 400
Inverse: 7.31028 seconds

Size: 800
Straight Inverse: 59.6293 seconds

I was still getting good answers here (ultiplied the original by the inverse and took the difference from the identity matrix).
It does appear to go up by about O(n^3)

You should be able to do better with an algorithm tuned more to your situation (very sparse), and a better implementation.

 

[Armitage]

Oh yeah ... if you really have to solve 121^5 of these, it will take on the order of 116 years with my algorithm on my computer. A very good algorithm and faster computer isn't likely to drop that more then an order of magnitude at best, which puts you at about 12 years.

So, you may want to rethink your approach!!

 

[glugglug]

Originally posted by: ergeorge
Ok, I'm having some trouble getting from here...

Originally posted by: glugglug
Time to solve a square matrix using normal well known methods is proportional to the size cubed (i.e. 121^3 in this case),

to here???

which means we're talking like an hour for 1.

I've had to write matrix-math programs before for a linear algebra class. This was back in high school and ran on old macs with 8MHz 68000 CPUs (no FPU, I had the program able to recognize fractions and keep them as such rather than use floating point as much as possible). I guestimated about a 300x difference between them and a modern PC in that estimate, but I must have underestimated the difference.

 

[Armitage]

You know ... I wasn't thinking clearly on how sparse this really is. Do you mean 10 to 12 non-zero for the entire array, or for each row of the array? If it's the former, you've got alot empty rows in there that you can eliminate ... of course you may not end up with the proper number of equations for the number of variables...

 

[pX]

Wow, thanks for all the suggestions!

There will be 10-12 non-zero elements for each row.

Basically I was implementing the "electrical circuit" heuristic for describing a given Hex position. You model the edges between squares as resistors (but I am working with conductances in mine, make it mostly zeros, not mostly infinites in the matrix), anyway, the edge between two hexagons is a resistor. If both are your color the resistance is zero (conductance infinite) if it is the opponents color the resistance is infinite (zero conductance). OK, what I have did was model each hexagon as having a resistor to every other hexagon, I have a few reasons for doing that (including it makes it easy to model 'virtual connections', it makes generating the matrix simple, and it makes solving it a simple matter (although I see that it could take more time than I want)). So if node A has a virtual connection to node B(that means they 'can' be connected no matter what the opponents next move is) it has a certain resistance,,, if Node A is far from node B it has infinite resistance... OK, back up, modeling a Hex board like this you finally get a total "resistance" if you say you are, lets say, passing 1 Amp into the circuit. This resistance measures "how connected" you are. A resistance of zero means you win. The matrix represents the KCL (all current entering or leaving a node equals zero) of each node. I saw this idea for doing it, and since I'm an EE not CS guy, I thought I'd have a go at it.

I'm not sure how I could reduce this, not sure at all. Maybe I will have to abandon this idea all together.

Sounds like it is going to take way too long, that really is a shame. I'll have to perhaps think of another way to do it. Maybe I should rephrase my question: "Is there a better way to solve a 121 node circuit than 121 KCL equations?" I don't think there is. And this has been done by people, solving the electrical resistor modle of a Hex board, hmmm, gotta think some I guess.

OK, how about this. In Ax=b where A is 121x121 and x and b are 121x1 I only need one value of X, the voltage at the top edge of the board. Could I write some code to simply solve for that X easier?



Haircut> you don't happen to go to Univ Newcastle do you?

 

[pX]

Eek, I'm remember something from linear algebra from 4 years back,, if I just want let say X1 I need to add/sub rows until I get [1 0 0 ... 0] in the top row,,, right? I could get that, and quit.. How to do that, I have no clue, but I could try.

 

[Haircut]

Originally posted by: pX
Haircut> you don't happen to go to Univ Newcastle do you?

No, I didn't go to the University of Newcastle, that was just a page I found than had some info on hex.

 

[pX]

Originally posted by: Haircut

Originally posted by: pX
Haircut> you don't happen to go to Univ Newcastle do you?

No, I didn't go to the University of Newcastle, that was just a page I found than had some info on hex.

Because that is the exact school and project I am writing this program for! Weird coincidence!

 

[Armitage]

Interesting approach... not that I understand it completely
Why do you think you need to solve 121^5 of these matrix equations?
Since that number is obviously to big, I think you need to implement something to decide which ones are actually important ... probably there is a good chunk that can be trivially eliminated.

 

[pX]

121^5 is what I'm shooting for. Why? thats 5 ply for a Hex board. 3 ply would be fine, but if it takes ~.14 sec for each calculation I'm looking at 1ply, which may not fair too well against programs who are going to search a lot deeper, but use inferior heuristic functions.

I can trim that number with a good search algorithm of course, but not anywhere as much as I'd need to.


So you don't think it makes the problem easier that I only need one value of x? Now that I think about it, I don't think it does. I was thinking perhaps of writing some code to generate a huge equation that solves for x, but I don't know if that would necessarily make the computation faster.

 

[Armitage]

To just get a single, you still need to reduce the entire matrix ... think back you your linear algebra work where you solved matrix equations by reducing the array to an upper (or lower) triangular form. At that point, you've already done all the hard work, so I don't see it buying you much.