Đấu giá mua đá quý - trò chơi trí tuệ

justhavelook
26-07-09, 11:02
Bọn trẻ con sẽ chơi một trò chơi mô phỏng việc đấu giá ở ngoài đời:

http://www.dstc.org.vn/?mod=home&sub=news&act=detail&newsid=149

Hai ngày nữa là 3 trận đấu giá đá quý sẽ diễn ra.

Có một đứa ở cạnh nhà hỏi mình mà mình thấy rất khó giúp bằng kiến thức chỉ ở cấp phổ thông.

Có 2 bài toán
- Bài toán xếp hình
- Bài toán đấu giá
+ Đánh giá kết quả sau một trận: số ô phủ được; số tiền tiêu; số viên đá thừa
+ Phương án đấu giá mới

Dưới đây mình sẽ đưa ra một gợi ý, ai biết gì thì bổ sung, gợi ý thêm để giúp thằng bé này nhé:
justhavelook
26-07-09, 11:09
PHÂN TÍCH CHIẾN LƯỢC ĐẤU GIÁ

- Ta gọi các viên đá thỏa mãn xếp được vào vùng diện tích bảng chưa xếp là các viên đá đúng, ngược lại là viên đá sai.

- Ta gọi viên đá đúng có diện tích lớn nhất là viên đá kỳ vọng bậc nhất. Diện tích lớn thứ nhì là kỳ vọng bậc 2, v.v.

- Gọi viên đá mà số lượng còn lại không ít hơn số đội chơi mà nó đúng là viên đá không cần cạnh tranh (hoặc chắc chắn.) Vì chắc chắn mua được với mọi giá rẻ.

- Gọi viên đá mà có số lượng còn lại ít hơn số đội chơi mà nó đúng là viên đá cạnh tranh (hoặc không chắc chắn). Vì chưa chắc đã mua được bằng giá rẻ.

Yếu tố Tiền

- Giả sử có còn lại k viên đá cạnh tranh và giả sử có m đội chơi nhiều tiền hơn ta.

+ Nếu k <= m thì viên đá không chắc chắn được gọi là viên đá cạnh tranh cao. (Vì nguy cơ cao là ta không mua được viên đá đúng này).

+ Nếu k > m thì ta nói rằng đó là viên đá cạnh tranh thấp.

+ Nếu m = 0, tức là không có đội nào nhiều tiền hơn ta thì viên đá đó gọi là viên đá cạnh tranh có thể thắng lợi.

Giả sử bảng có diện tích STable (không kể các ô không lát được do hình dạng bảng). Stable = m * n – count(cell=-1)

Xét đội i:

Gọi số tiền trung bình lý tưởng trên một đơn vị diện tích bảng là một số nguyên G bằng phần nguyên của phép chia tổng số tiền có ban đầu của đội i cho tổng diện tích bảng, tức là G = [Mi / STable]. Một cách lý thưởng, nếu đội i mua gần hết số tiền mà mình có: Mi = G*STable thì sẽ lát được tất cả bảng. Vậy G là tiêu chuẩn lý tưởng về sự cân bằng khi đắn đo tăng giảm tiền lúc đấu giá.

Ta đưa ra quy định việc thưởng phạt điểm cho đội i khi mua được một viên đá đúng hoặc sai như sau: Giả sử viên đá Br mua được có diện tích là SBr, mua được với giá tiền (quy nguyên) là MBr.

Nếu Br là viên đá đúng thì đội i được cộng thêm số điểm là SBr * HBr (trong đó HBr là một hằng số heristic dương nào đó và phụ thuộc vào tính chất của viên đá Br), đồng thời cũng được thưởng phạt số điểm delta = |MBr – G*Sbr| như sau:

- Nếu Mbr ≤ G*SBr thì được thưởng thêm delta điểm

- Nếu Mbr > G*SBr thì bị phạt số điểm là delta điểm.

Tóm lại đội i sẽ được thưởng số điểm là, chú ý hệ số HBr được điều chỉnh tổng thể để award không âm với mọi viên đá mua được với bất kỳ số tiền nào.
award = SBr * HBr ± delta

Nếu Br là viên đá sai phải mua thì đội i sẽ bị trừ số điểm (tức là cộng với điểm âm) là: punish = - (SBr * HBr + delta). Để không bị trừ, do ta biết trước một viên đá đến một lúc nào đó trở thành sai, ta sẽ mua viên đá đó lớn hơn số tiền mà mình có.

Ta thấy tổng số điểm đạt được khi xem xét tất cả các viên đá sau một trận đấu phản ánh được việc đánh giá kết quả sau trận đó: số ô phủ được; số tiền tiêu; số viên đá thừa.

Từ việc định nghĩa điểm thưởng, phạt, ta thấy chiến lược chơi ở đây là nhằm mục đích tăng diện tích lát bảng (được thưởng) và chi tiêu số tiền hợp lý (bị phạt nếu tiêu nhiều, được thưởng nếu tiêu ít). Từ đây ta phải tìm các quy luật đấu giá để sao cho sau mỗi đợt đấu giá (cụ thể là khi mua một viên đá) thì điểm thưởng càng lớn càng tốt.

PLAY FOR MYSELF

Ta đưa ra 4 nhóm quy luật đấu giá chỉ xét cho chính đội mình như sau:

1. Đấu giá chắc chắn

Q1) Chọn viên đá kỳ vọng bậc cao nhất có thể được mà không có cạnh tranh để gán độ ưu tiên cao nhất và mua với giá rẻ nhất. Lưu ý ở đây, độ ưu tiên cao nhất hiểu theo nghĩa giá trị của nó nhỏ nhất.

Q2) Chọn viên đá kỳ vọng bậc cao thứ nhì có thể được mà không có cạnh tranh để gán độ ưu tiên cao thứ nhì và mua với giá rẻ nhất. Cứ tiếp tục như thế cho đến chọn được 10 viên đá.

Số tiền mua các viên đá rơi vào các trường hợp Q1 và Q2 là
MQ1 = MQ2 = 1 (nghìn đồng)

Chú ý rằng các viên đá chọn sau có thể trùng với viên đá chọn trước (do đó cùng bậc kỳ vọng), nhưng có thể sau đó nó trở thành viên đá có cạnh tranh, vì số lượng viên đá ít đi.
Việc đấu giá chắc chắn tuy có lợi cả về diện tích lát và về tiền nhưng lại có ít cơ hội. Bởi vì, nguy cơ của việc đấu giá chắc chắn là các viên đá cần mua mau chóng trở thành viên đá có cạnh tranh (cẩn thận nếu nó bị ngộ nhận nó không có cạnh tranh). Do đó, khi viên đá chuyển sang có cạnh tranh thì phải tìm quy luật mới.

2. Đấu giá thận trọng

Q3) Chọn viên đá kỳ vọng có bậc cao nhất có thể được nhưng có cạnh tranh thấp. Vấn đề là mua bao nhiêu tiền để có thể có nhiều hy vọng mua được nhất?.
Ta sẽ mua viên đá có diện tích SBr Snày với số tiền là:
MQ3 = G * SBr + MCompetitorLow

Trong đó MCompetitorLow là một số dương đủ nhỏ nhưng đủ biểu thị số tiền cạnh tranh cần thiết để mua được viên đá. Số tiền này cần được xem xét trên 3 phương diện:

MeWant: Nhu cầu cần của bản thân ta, diện tích đã lát, diện tích chưa lát, số tiền còn lại. (Điểm)

YouWant: Nhu cầu của đội mạnh thứ nhì (có điểm cao thứ nhì), cũng về các yếu tố diện tích đã lát, diện tích chưa lát, số tiền còn lại của họ. (Điểm)

Remain: Số lượng và các loại đá còn lại của nơi tổ chức bán đấu giá.

3. Đấu giá mạo hiểm

Q4) Chọn viên đá kỳ vọng có bậc cao nhất có thể được và chấp nhận cạnh tranh cao Số tiền cần mua là MQ4 cũng tương tự như trên nhưng giá trị của YouWant dựa trên nhu cầu của đội mạnh nhất (điểm cao nhất).

4. Đấu giá tình thế
Q5) Chọn viên đá nào đó với số tiền đấu giá nhiều hơn số tiền hiện có để cố tình không mua. MQ5 = Mi + 10, trong đó Mi là số tiền còn lại của đội mình.


---------------------